MIP - Linear, Integer, and Constraint Programming

Project Description

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

the SCIP Optimization Suite

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.

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 (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