MIP - Linear, Integer, and Constraint Programming

Project Description

Many real world problems can be modeled as mixed integer programs (MIPs). This project aims at developing tools for modeling and solving general MIPs, which can be applied by users as stand alone products or as a library within other software applications. We develop, maintain, and provide

the ZIB Optimization Suite

which contains software for generating and solving linear programs (LPs), mixed integer programs (MIPs) and constraint integer programs.
The ZIB Optimization Suite includes:

the modeling language ZIMPL
the simplex LP-solver SoPlex
the branch-cut-and-price framework and MIP-solver SCIP, integrating constraint programming and MIP

Furthermore, the LP-basis verifier perPlex is hosted at ZIB.

Description

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 programs, and solve the resulting MIPs, 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
implementation of algorithms for solving mixed-integer non-linear programs, integration of non-linear relaxations by appropriate interfaces.
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.
integration of existing and development of new features to handle symmetries in integer programs. See Matheon-Project B12 Symmetries in Integer Programming.
development of a flexible, user definable modeling language for constraint integer programs