1052
eng
reportzib
0
2008-01-04
2008-01-04
--
Constraint Integer Programming: a New Approach to Integrate CP and MIP
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.
08-01
1438-0064
1081
urn:nbn:de:0297-zib-10520
Appeared in: Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems, 5th International Conference, CPAIOR 2008 (L. Perron und M. A. Trick, eds.), Lecture Notes in Computer Science, 5015, 2008, pp. 6–20
Tobias Achterberg
unknown unknown
Timo Berthold
Thorsten Koch
Kati Wolter
ZIB-Report
08-01
deu
uncontrolled
Constraint Programming
deu
uncontrolled
Ganzzahlige Programmierung
deu
uncontrolled
Branch-And-Cut
deu
uncontrolled
Optimierungssoftware
deu
uncontrolled
Chipverifikation
eng
uncontrolled
constraint programming
eng
uncontrolled
mixed integer programming
eng
uncontrolled
branch-and-cut
eng
uncontrolled
optimization software
eng
uncontrolled
chip verification
Mathematik
Mathematical programming methods [See also 90Cxx]
Mixed integer programming
Combinatorial optimization
Mathematical Optimization
Achterberg, Tobias
Berthold, Timo
Koch, Thorsten
Wolter, Kati
VeriCount
https://opus4.kobv.de/opus4-zib/files/1052/ZR_08_01.pdf
https://opus4.kobv.de/opus4-zib/files/1052/ZR_08_01.ps