Acceso al sitio web del Consejo de Políticas de Infraestructura
REVISTA
Algorithms

   
Inicio  /  Algorithms  /  Vol: 12 Par: 12 (2019)  /  Artículo
ARTÍCULO
TITULO

Solving Integer Linear Programs by Exploiting Variable-Constraint Interactions: A Survey

Robert Ganian and Sebastian Ordyniak    

Resumen

Integer Linear Programming (ILP) is among the most successful and general paradigms for solving computationally intractable optimization problems in computer science. ILP is NP-complete, and until recently we have lacked a systematic study of the complexity of ILP through the lens of variable-constraint interactions. This changed drastically in recent years thanks to a series of results that together lay out a detailed complexity landscape for the problem centered around the structure of graphical representations of instances. The aim of this survey is to summarize these recent developments, put them into context and a unified format, and make them more approachable for experts from many diverse backgrounds.

PÁGINAS
pp. 0 - 0

 Artículos similares

       
 
José Victor Sá Santos and Napoleão Nepomuceno    
The Cutting Stock Problem (CSP) is an optimisation problem that roughly consists of cutting large objects in order to produce small items. The computational effort for solving this problem is largely affected by the number of cutting patterns. In this ar... ver más
Revista: Algorithms

 
Milos Seda    
The assignment problem is a problem that takes many forms in optimization and graph theory, and by changing some of the constraints or interpreting them differently and adding other constraints, it can be converted to routing, distribution, and schedulin... ver más
Revista: Algorithms

 
Oscar Danilo Montoya, Luis Fernando Grisales-Noreña and Carlos Andres Ramos-Paja    
The problem of optimal siting and dimensioning of photovoltaic (PV) generators in medium-voltage distribution networks is addressed in this research from the perspective of combinatorial optimization. The exact mixed-integer programming (MINLP) model is ... ver más
Revista: Computers

 
Marina Dubravac, Kre?imir Fekete, Danijel Topic and Marinko Barukcic    
There is a rising trend to integrate different types of distributed generation (DG), especially photovoltaic (PV) systems, on the roofs of existing consumers, who then become prosumers. One of the prosumer impacts is voltage violations, which conventiona... ver más
Revista: Applied Sciences

 
Atabak Elmi, Dhananjay R. Thiruvady and Andreas T. Ernst    
Cyclic scheduling is of vital importance in a repetitive discrete manufacturing environment. We investigate scheduling in the context of general cyclic job shops with blocking where there are no intermediate buffers between the machines. We also consider... ver más
Revista: Algorithms