MIP - Linear, Integer, and Constraint Programming
Many real world problems can be modeled as mixed integer programs (MIPs) or mixed integer nonlinear programs (MINLPs). This project aims at developing tools for modeling and solving general MIPs and MINLPs, which can be applied by users as stand alone products or as a library within other software applications. We develop, maintain, and provide
which contains software for generating and solving linear programs (LPs), MIPs, MINLPs, and constraint integer programs.
The SCIP Optimization Suite includes:
- the modeling language ZIMPL
- the simplex LP-solver SoPlex
- the branch-cut-and-price framework, MIP- and MINLP-solver SCIP, integrating constraint programming and MIP
- the generic branch-and-price solver GCG
- the parallel framework UG for solving mixed integer linear and nonlinear programs
Furthermore, the LP-basis verifier perPlex is hosted at ZIB.
Todays most successful approach for solving general mixed integer programs (MIPs) is to use a so called branch-and-cut algorithm that operates on the underlying LP-relaxation of the MIP. In this algorithm, the integrality conditions are initially ignored, such that the MIP is simplified to a linear program. Afterwards, the integrality is restored by using (a) cutting planes and (b) an implicit enumeration through branch-and-bound.
Branch-and-bound (b) is also used in algorithms for solving Constraint Programs (CPs), to divide the problem instance successively into smaller subproblems. In contrast to MIP-solvers, CP-solvers usually do not incorporate LP-relaxations and cutting planes to limit the search space and to prevent the enumeration of all potential solutions. Instead, they rely on constraint and domain propagation (c) and conflict analysis (d). The former is an inference technique, which tightens the domains of the variables. The latter is used on infeasible subproblems to retrieve information about the reason of the infeasibility. This information can then be used to tighten further domains of variables at other subproblems in the search tree.
The integration of MIP and CP techniques combines the more flexible modeling capabilities of constraint programming and the highly efficient solution methods of mixed integer programming that are tailored to the specific structure of linear constraints. In particular, the treatment of numerically difficult constraints by constraint programming techniques instead of using their LP-relaxations directly can help to ensure the stability of the underlying linear programs.
The tools for modeling and solving general MIPs developed in this project can be applied by users
- as a stand alone product: to create models for their problem classes, convert these models together with input data into mixed integer (nonlinear) programs, and solve the resulting MIPs and MINLPs, or
- as a programming framework: to set up and manipulate MIPs with calls to the APIs, and solve them, while being able to control the search process with respect to their specific needs.
Ongoing Work: ZIMPL
- extension of language capabilities by providing automatic linearizations of non-linear constraints
- improvement of data structures to speed up compilation
- incorporation of new types of non-linear constraints
Ongoing Work: SoPlex
- improvement of numerical stability and speed
- improvement of interaction with MIP frameworks
Ongoing Work: SCIP
- implementation of specialized constraint handlers for specific constraints involved in real world problems in order to exploit the knowledge about the specific substructures
- improvement of algorithms for solving mixed-integer non-linear programs, integration of non-linear relaxations by appropriate interfaces. See Matheon-Project B20 Optimization of Gas Transport
- development of new linear and integer programming techniques to solve supply chain management problems. See SCM project
- further improvement in the development of primal heuristics and cutting plane algorithms
- incorporation of an exact solving mode in order to find provably optimal solutions. See DFG-Project Exact Integer Programming
Since 01/1994 until further notice