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)
We provide a computational study of the performance of a state-of-the-art solver for nonconvex mixed-integer quadratically constrained programs (MIQCPs). Since successful general-purpose solvers for large problem classes necessarily comprise a variety of algorithmic techniques, we focus especially on the impact of the individual solver components. The solver SCIP used for the experiments implements a branch-and-cut algorithm based on linear outer approximation to solve MIQCPs to global optimality. Our analysis is based on a set of 86 publicly available test instances.
MIPLIB 2010
(2012)
This paper reports on the fifth version of the Mixed Integer Programming Library. The MIPLIB 2010 is the first MIPLIB release that has been assembled by a large group from academia and from industry, all of whom work in integer programming. There was mutual consent that the concept of the library had to be expanded in order to fulfill the needs of the community. The new version comprises 361 instances sorted into several groups. This includes the main benchmark test set of 87 instances, which are all solvable by today's codes, and also the challenge test set with 164 instances, many of which are currently unsolved. For the first time, we include scripts to run automated tests in a predefined way. Further, there is a solution checker to test the accuracy of provided solutions using exact arithmetic.
Given a general mixed integer program (MIP), we automatically detect block structures in the constraint matrix together with the coupling by capacity constraints arising from multi-commodity flow formulations. We
identify the underlying graph and generate cutting planes based on cuts in the detected network. Our implementation adds a separator to the branch-and-cut libraries of SCIP and CPLEX. We make use of the complemented mixed integer rounding framework (cMIR) but provide a special purpose aggregation heuristic that exploits the network structure. Our separation scheme speeds-up the computation for a large set of MIPs coming from network design problems
by a factor of two on average.
In this paper we investigate the performance of several out-of-the box solvers for mixed-integer quadratically constrained programmes (MIQCPs) on an open pit mine production scheduling problem with mixing constraints. We compare the solvers BARON, Couenne, SBB, and SCIP to a problem-specific algorithm on two different MIQCP formulations. The computational results presented show that general-purpose solvers with no particular knowledge of problem structure are able to nearly match the performance of a hand-crafted algorithm.
This paper discusses how to build a solver for mixed integer quadratically constrained programs (MIQCPs) by extending a framework for constraint integer programming (CIP). The advantage of this approach is that we can utilize the full power of advanced MIP and CP technologies. In particular, this addresses the linear relaxation and the discrete components of the problem. For relaxation, we use an outer approximation generated by linearization of convex constraints and linear underestimation of nonconvex constraints. Further, we give an overview of the reformulation, separation, and propagation techniques that are used to handle the quadratic constraints efficiently.
We implemented these methods in the branch-cut-and-price framework SCIP. Computational experiments indicates the potential of the approach.
Pseudo-Boolean problems lie on the border between satisfiability problems, constraint programming, and integer programming. In particular, nonlinear constraints in pseudo-Boolean optimization can be handled by methods arising in these different fields: One can either linearize them and work on a linear programming relaxation or one can treat them directly by propagation. In this paper, we investigate the individual strengths of these approaches and compare their computational performance. Furthermore, we integrate these techniques into a branch-and-cut-and-propagate framework, resulting in an efficient nonlinear pseudo-Boolean solver.
Hybrid Branching
(2009)
State-of-the-art solvers for Constraint Satisfaction Problems (CSP), Mixed Integer Programs (MIP), and
satisfiability problems (SAT) are usually based on a branch-and-bound algorithm.
The question how to split a problem into subproblems (\emph{branching}) is in the core of any branch-and-bound algorithm.
Branching on individual variables is very common in CSP, MIP, and SAT. The rules, however, which variable to choose for
branching, differ significantly. In this paper, we present hybrid branching, which combines selection rules from all three fields.
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 for solving satisfiability problems. SCIP is available in source code and free for noncommercial use.
We demonstrate the usefulness of CIP on three 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 demonstrate how to use CIP techniques to compute the number of optimal solutions of integer programs. Third, we employ the CIP framework to solve chip design verification problems, which involve some highly nonlinear 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 nonlinear constraints by employing constraint programming techniques.
Pseudo-Boolean problems generalize SAT problems by allowing linear constraints and a linear objective function. Different solvers, mainly having their roots in the SAT domain, have been proposed and compared,for instance, in Pseudo-Boolean evaluations. One can also formulate Pseudo-Boolean models as integer programming models. That is,Pseudo-Boolean problems lie on the border between the SAT domain and the integer programming field.
In this paper, we approach Pseudo-Boolean problems from the integer programming side. We introduce the framework SCIP that implements constraint integer programming techniques. It integrates methods from constraint programming, integer programming, and SAT-solving: the solution of linear programming relaxations, propagation of linear as well as nonlinear constraints, and conflict analysis. We argue that this approach is suitable for Pseudo-Boolean instances containing general linear constraints, while it is less efficient for pure SAT problems. We present extensive computational experiments on the test set used for the Pseudo-Boolean evaluation 2007. We show that our approach is very efficient for optimization instances and competitive for feasibility problems. For the nonlinear parts, we also investigate the influence of linear programming relaxations and propagation methods on the performance. It turns out that both techniques are helpful for obtaining an efficient solution method.
In this paper we give an overview of the heuristics which are integrated into the open source branch-cut-and-price-framework SCIP.
We briefly describe the fundamental ideas of different categories of heuristics and present some computational results which demonstrate the impact of heuristics on the overall solving process of SCIP.
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.