90C11 Mixed integer programming
Refine
Language
- English (24)
- German (1)
- Multiple languages (1)
Keywords
- mixed integer programming (8)
- branch-and-cut (6)
- nonconvex (4)
- Large Neighborhood Search (3)
- Primal Heuristic (3)
- domain propagation (3)
- integer programming (3)
- optimization software (3)
- primal heuristic (3)
- primal heuristics (3)
Primalheuristiken spielen in modernen MIP-Lösern wie dem am ZIB
entwickelten SCIP eine Schlüsselrolle beim Auffinden und Verbessern
zulässiger Lösungen. Wir geben einen Überblick über die verschiedene
Kategorien von Primalheuristiken und deren Einfluss auf das
Lösungsverhalten von SCIP. Es zeigt sich, dass gerade das
Zusammenspiel unterschiedlicher heuristischer Ansätze im Mittel für
ein gutes Lösungsverhalten sorgt, wobei der Feinabstimmung zwischen
Methoden mit ähnlichen Ansätzen eine besondere Wichtigkeit zufällt.
In the recent years, a couple of quite successful large neighborhood search heuristics for mixed integer programs has been published.
Up to our knowledge, all of them are improvement heuristics.
We present a new start heuristic for general MIPs working in the spirit of large neighborhood search.
It constructs a sub-MIP which represents the space of all feasible roundings of some fractional point - normally the optimum of the LP-relaxation of the original MIP.
Thereby, one is able to determine whether a point can be rounded to a feasible solution and which is the best possible rounding.
Furthermore, a slightly modified version of RENS proves to be a well-performing heuristic inside the branch-cut-and-price-framework SCIP.
The Feasibility Pump of Fischetti, Glover, Lodi, and Bertacco has proved to be a very successful heuristic for finding feasible solutions of mixed integer programs. The quality of the solutions in terms of the objective value, however, tends to be poor.
This paper proposes a slight modification of the algorithm in order to find better solutions.
Extensive computational results show the success of this variant: in 89 out of 121 MIP instances the modified version produces improved solutions in comparison to the original Feasibility Pump.
This article introduces constraint integer programming (CIP), which is a novel way to combine constraint programming (CP) and mixed integer programming (MIP) methodologies.
CIP is a generalization of MIP that supports the notion of general constraints as in CP.
This approach is supported by the CIP framework SCIP, which also integrates techniques from SAT solving.
SCIP is available in source code and free for non-commercial use.
We demonstrate the usefulness of CIP on two tasks.
First, we apply the constraint integer programming approach to pure mixed integer programs.
Computational experiments show that SCIP is almost competitive to current state-of-the-art commercial MIP solvers.
Second, we employ the CIP framework to solve chip design verification problems, which involve some highly non-linear constraint types that are very hard to handle by pure MIP solvers.
The CIP approach is very effective here:
it can apply the full sophisticated MIP machinery to the linear part of the problem, while dealing with the non-linear constraints by employing constraint programming techniques.
In this article we study capacitated network design problems. We unify and extend polyhedral results for directed, bidirected and undirected link capacity models. Based on valid inequalities for a network cut we show that regardless of the link capacity model, facets of the polyhedra associated with such a cut translate to facets of the original network design polyhedra if the two subgraphs defined by the network cut are (strongly) connected. Our investigation of the facial structure of the cutset polyhedra allows to complement existing polyhedral results for the three variants by presenting facet-defining flow-cutset inequalities in a unifying way. In addition, we present a new class of facet-defining inequalities, showing as well that flow-cutset inequalities alone do not suffice to give a complete description for single-commodity, single-module cutset polyhedra in the bidirected and undirected case – in contrast to a known result for the directed case. The practical importance of the theoretical investigations is highlighted in an extensive computational study on 27 instances from the Survivable Network Design Library (SNDlib).
MIPLIB 2003
(2005)
This paper is about the fourth version of the Mixed Integer Programming Library (MIPLIB).
More than 7 years have been past since the last update. Since the focus of the MIPLIB is to provide a concise set of challenging problems, it became again necessary to purge the library from instances that have become too easy due to improvements in optimizers and computing machinery.
The free slots have been filled by 27 new challenging instances. We give an overview of the new problems and present statistical data for all 60 instances included in the MIPLIB 2003.