Eingang zum Volltext

Urheberrechtshinweis / Copyright notice

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

Berthold, Timo ; Heinz, Stefan ; Vigerske, Stefan

Extending a CIP framework to solve MIQCPs

pdf-Format:
Dokument 1.pdf (293 KB)
ps-Format:
Dokument 1.ps (495 KB)

Kurzfassung in Englisch

This paper discusses how to build a solver for mixed integer quadratically constrained programs (MIQCPs) by extending a framework for constraint integer programming (CIP). The advantage of this approach is that we can utilize the full power of advanced MIP and CP technologies. In particular, this addresses the linear relaxation and the discrete components of the problem. For relaxation, we use an outer approximation generated by linearization of convex constraints and linear underestimation of nonconvex constraints. Further, we give an overview of the reformulation, separation, and propagation techniques that are used to handle the quadratic constraints efficiently.

We implemented these methods in the branch-cut-and-price framework SCIP. Computational experiments indicates the potential of the approach.

Freie Schlagwörter (englisch): mixed integer quadratically constrained programming , constraint integer programming , convex relaxation , nonconvex
MSC - Klassifikation 90C57
MSC - Klassifikation 90C27
MSC - Klassifikation 90C26
MSC - Klassifikation 90C20
MSC - Klassifikation 90C11
Abteilung: Optimierung
DDC-Sachgruppe: Mathematik
Dokumentart: ZIB-Report
Schriftenreihe: ZIB-Report
Band Nummer: 09-23
ISBN: 1438-0064
Sprache: Englisch
Erstellungsjahr: 2009
Publikationsdatum: 09.07.2009

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