Eingang zum Volltext

Urheberrechtshinweis / Copyright notice

Bitte beziehen Sie sich beim Zitieren dieses Dokumentes immer auf folgende
URL: http://opus.kobv.de/zib/volltexte/2008/1081/

Achterberg, Tobias ; Berthold, Timo ; Koch, Thorsten ; Wolter, Kati

Constraint Integer Programming: a New Approach to Integrate CP and MIP

pdf-Format:
Dokument 1.pdf (242 KB)
ps-Format:
Dokument 1.ps (841 KB)

Kurzfassung in Englisch

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.

Freie Schlagwörter (deutsch): Constraint Programming , Ganzzahlige Programmierung , Branch-And-Cut , Optimierungssoftware , Chipverifikation
Freie Schlagwörter (englisch): constraint programming , mixed integer programming , branch-and-cut , optimization software, chip verification
MSC - Klassifikation 90C11
MSC - Klassifikation 90C27
MSC - Klassifikation 65K05
Abteilung: Optimierung
DDC-Sachgruppe: Mathematik
Dokumentart: ZIB-Report
Schriftenreihe: ZIB-Report
Band Nummer: 08-01
ISBN: 1438-0064
Quelle: 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
Sprache: Englisch
Erstellungsjahr: 2008
Publikationsdatum: 04.01.2008
Bemerkung: printed version not available / keine gedruckte Version verfügbar

Metadatensuche | Volltextsuche | Browsen | Die neuesten Publikationen | Veröffentlichen
Fragen und Anregungen an bibliothek@zib.de
Letzte Änderung: