Constraint Integer Programming: Techniques and Applications
Please always quote using this URN:urn:nbn:de:0296-matheon-6037
- 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.
Author: | Tobias Achterberg, Timo Berthold, Stefan Heinz, Thorsten Koch, Kati Wolter |
---|---|
URN: | urn:nbn:de:0296-matheon-6037 |
Referee: | Martin Grötschel |
Document Type: | Preprint, Research Center Matheon |
Language: | English |
Date of first Publication: | 2009/07/21 |
Release Date: | 2009/07/20 |
Tag: | |
Institute: | Humboldt-Universität zu Berlin |
Zuse Institute Berlin (ZIB) | |
MSC-Classification: | 65-XX NUMERICAL ANALYSIS / 65Kxx Mathematical programming, optimization and variational techniques / 65K05 Mathematical programming methods [See also 90Cxx] |
90-XX OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING / 90Cxx Mathematical programming [See also 49Mxx, 65Kxx] / 90C11 Mixed integer programming | |
90-XX OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING / 90Cxx Mathematical programming [See also 49Mxx, 65Kxx] / 90C27 Combinatorial optimization | |
Preprint Number: | 598 |