A basic toolbox for constrained quadratic 0/1 optimization

Beitrag in einem Sammelwerk

Details zur Publikation

Autorinnen und Autoren: Buchheim C, Liers F, Oswald M
Herausgeber: Catherine C. McGeoch
Titel Sammelwerk: Experimental Algorithms
Verlag: Springer
Verlagsort: Berlin Heidelberg
Jahr der Veröffentlichung: 2008
Titel der Reihe: Lecture Notes in Computer Science
Band: 5038
Seitenbereich: 249-262
ISBN: 9783540685487


In many practical applications, the task is to optimize a non-linear function over a well-studied polytope P as, e.g., the matching polytope or the travelling salesman polytope (TSP). In this paper, we focus on quadratic objective functions. Prominent examples are the quadratic assignment and the quadratic knapsack problem; further applications occur in various areas such as production planning or automatic graph drawing. In order to apply branch-and-cut methods for the exact solution of such problems, they have to be linearized. However, the standard linearization usually leads to very weak relaxations. On the other hand, problem-specific polyhedral studies are often time-consuming. Our goal is the design of general separation routines that can replace detailed polyhedral studies of the resulting polytope and that can be used as a black box. As unconstrained binary quadratic optimization is equivalent to the maximum cut problem, knowledge about cut polytopes can be used in our setting. Other separation routines are inspired by the local cuts that have been developed by Applegate, Bixby, Chvátal and Cook for faster solution of large-scale traveling salesman instances. By extensive experiments, we show that both methods can drastically accelerate the solution of constrained quadratic 0/1 problems. © 2008 Springer-Verlag Berlin Heidelberg.

FAU-Autorinnen und Autoren / FAU-Herausgeberinnen und Herausgeber

Liers-Bergmann, Frauke Prof. Dr.
Professur für Angewandte Mathematik (Ganzzahlige und robuste Optimierung)

Einrichtungen weiterer Autorinnen und Autoren

Ruprecht-Karls-Universität Heidelberg
Universität zu Köln


Buchheim, C., Liers, F., & Oswald, M. (2008). A basic toolbox for constrained quadratic 0/1 optimization. In Catherine C. McGeoch (Eds.), Experimental Algorithms. (pp. 249-262). Berlin Heidelberg: Springer.

Buchheim, Christoph, Frauke Liers, and Marcus Oswald. "A basic toolbox for constrained quadratic 0/1 optimization." Experimental Algorithms. Ed. Catherine C. McGeoch, Berlin Heidelberg: Springer, 2008. 249-262.


Zuletzt aktualisiert 2018-28-10 um 20:53