Overview Statistic: PDF-Downloads (blue) and Frontdoor-Views (gray)
  • Treffer 1 von 14
Zurück zur Trefferliste

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

Zitieren Sie bitte immer diese URN: urn:nbn:de:0297-zib-10520
  • 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.

Volltext Dateien herunterladen

Metadaten exportieren

Weitere Dienste

Teilen auf Twitter Suche bei Google Scholar Statistik - Anzahl der Zugriffe auf das Dokument
Metadaten
Verfasserangaben:Tobias AchterbergORCiD, Timo BertholdORCiD, Thorsten KochORCiD, Kati Wolter
Dokumentart:ZIB-Report
Freies Schlagwort / Tag:Branch-And-Cut; Chipverifikation; Constraint Programming; Ganzzahlige Programmierung; Optimierungssoftware
branch-and-cut; chip verification; constraint programming; mixed integer programming; optimization software
MSC-Klassifikation: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
Datum der Erstveröffentlichung:04.01.2008
Schriftenreihe (Bandnummer):ZIB-Report (08-01)
ISSN:1438-0064
ZIB-Reportnummer:08-01
Verlagspublikation: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
Accept ✔
Diese Webseite verwendet technisch erforderliche Session-Cookies. Durch die weitere Nutzung der Webseite stimmen Sie diesem zu. Unsere Datenschutzerklärung finden Sie hier.