Search results for "linear programming"
showing 10 items of 137 documents
Network-Assisted Resource Allocation with Quality and Conflict Constraints for V2V Communications
2018
The 3rd Generation Partnership Project (3GPP) has recently established in Rel. 14 a network-assisted resource allocation scheme for vehicular broadcast communications. Such novel paradigm is known as vehicle--to--vehicle (V2V) \textit{mode-3} and consists in eNodeBs engaging only in the distribution of sidelink subchannels among vehicles in coverage. Thereupon, without further intervention of the former, vehicles will broadcast their respective signals directly to their counterparts. Because the allotment of subchannels takes place intermittently to reduce signaling, it must primarily be conflict-free in order not to jeopardize the reception of signals. We have identified four pivotal types…
Solution isolation strategies for the Bernstein polytopes-based solver
2013
The Bernstein polytopes-based solver is a new method developed to solve systems of nonlinear equations, which often occur in Geometric Constraint Solving Problems. The principle of this solver is to linearize nonlinear monomials and then to solve the resulting linear programming problems, through linear programming. However, without any strategy for the isolation of the many solutions of multiple-solution systems, this solver is slow in practice. To overcome this problem, we propose in this work, a study of several strategies for solution isolation, through the split of solution boxes into several subboxes, according to three main steps answering the questions: when, where, and how to perfo…
Optimization of polygeneration plants and μ-grids for civil applications
2010
The problem of combined energy production and distribution of warm and cold fluids is very complex because it includes two possible configurations, the small single unit for individual buildings and the large plant integrated with district heating networks. Dealing with such a complex problem, involving a very large number of variables, requires efficient algorithms and resolution techniques. The present study illustrates a MILP approach to the optimization of synthesis, design and operation for CHCP-based μ-grids including thermal energy storages. The proposed approach develops a method for designing and optimizing district energy systems, starting with the information available for the di…
Algorithms for the Maximum Weight Connected $$k$$-Induced Subgraph Problem
2014
Finding differentially regulated subgraphs in a biochemical network is an important problem in bioinformatics. We present a new model for finding such subgraphs which takes the polarity of the edges (activating or inhibiting) into account, leading to the problem of finding a connected subgraph induced by \(k\) vertices with maximum weight. We present several algorithms for this problem, including dynamic programming on tree decompositions and integer linear programming. We compare the strength of our integer linear program to previous formulations of the \(k\)-cardinality tree problem. Finally, we compare the performance of the algorithms and the quality of the results to a previous approac…
Separating capacity constraints in the CVRP using tabu search
1998
Abstract Branch and Cut methods have shown to be very successful in the resolution of some hard combinatorial optimization problems. The success has been remarkable for the Symmetric Traveling Salesman Problem (TSP). The crucial part in the method is the cutting plane algorithm: the algorithm that looks for valid inequalities that cut off the current nonfeasible linear program (LP) solution. In turn this part relies on a good knowledge of the corresponding polyhedron and our ability to design algorithms that can identify violated valid inequalities. This paper deals with the separation of the capacity constraints for the Capacitated Vehicle Routing Problem (CVRP). Three algorithms are prese…
Branch-and-Cut
2010
This chapter focuses on the approach for solving the LOP to optimality which can currently be seen as the most successful one. It is a branch-and-bound algorithm, where the upper bounds are computed using linear programming relax- ations.
Connections of reference vectors and different types of preference information in interactive multiobjective evolutionary algorithms
2016
We study how different types of preference information coming from a human decision maker can be utilized in an interactive multiobjective evolutionary optimization algorithm (MOEA). The idea is to convert different types of preference information into a unified format which can then be utilized in an interactive MOEA to guide the search towards the most preferred solution(s). The format chosen here is a set of reference vectors which is used within the interactive version of the reference vector guided evolutionary algorithm (RVEA). The proposed interactive RVEA is then applied to the multiple-disk clutch brake design problem with five objectives to demonstrate the potential of the idea in…
A polynomial algorithm solving a special class of hybrid optimal control problems
2006
Hybrid optimal control problems are, in general, difficult to solve. A current research goal is to isolate those problems that lead to tractable solutions [5]. In this paper, we identify a special class of hybrid optimal control problems which are easy to solve. We do this by using a paradigm borrowed from the Operations Research field. As main result, we present a solution algorithm that converges to the exact solution in polynomial time. Our approach consists in approximating the hybrid optimal control problem via an integer-linear programming reformulation. The integer-linear programming problem is a Set-covering one with a totally unimodular constraint matrix and therefore solving the S…
Peak Power Demand and Energy Consumption Reduction Strategies for Trains under Moving Block Signalling System
2013
Published version of an article in the journal: Mathematical Problems in Engineering. Also available from the publisher at: http://dx.doi.org/10.1155/2013/940936 Open Access In the moving block signalling (MBS) system where the tracking target point of the following train is moving forward with its leading train, overload of the substations occurs when a dense queue of trains starts (or restarts) in very close distance interval. This is the peak power demand problem. Several methods have been attempted in the literature to deal with this problem through changing train's operation strategies. However, most existing approaches reduce the service quality. In this paper, two novel approaches - …
Characteristics of the polymer transport in ratchet systems
2010
Molecules with complex internal structure in time-dependent periodic potentials are studied by using short Rubinstein-Duke model polymers as an example. We extend our earlier work on transport in stochastically varying potentials to cover also deterministic potential switching mechanisms, energetic efficiency and non-uniform charge distributions. We also use currents in the non-equilibrium steady state to identify the dominating mechanisms that lead to polymer transportation and analyze the evolution of the macroscopic state (e.g., total and head-to-head lengths) of the polymers. Several numerical methods are used to solve the master equations and nonlinear optimization problems. The domina…