Speeding up IP-based algorithms for constrained quadratic 0-1 optimization
In many practical applications, the task is to optimize a non-linear objective function over the vertices of a well-studied polytope as, e.g., the matching polytope or the travelling salesman polytope (TSP). Prominent examples are the quadratic assignment problem and the quadratic knapsack problem;...
Gespeichert in:
| Hauptverfasser: | , , |
|---|---|
| Dokumenttyp: | Article (Journal) |
| Sprache: | Englisch |
| Veröffentlicht: |
08 May 2010
|
| In: |
Mathematical programming
Year: 2010, Jahrgang: 124, Pages: 513-535 |
| ISSN: | 1436-4646 |
| DOI: | 10.1007/s10107-010-0377-3 |
| Online-Zugang: | Verlag, lizenzpflichtig, Volltext: https://doi.org/10.1007/s10107-010-0377-3
|
| Verfasserangaben: | Christoph Buchheim, Frauke Liers, Marcus Oswald |
MARC
| LEADER | 00000caa a2200000 c 4500 | ||
|---|---|---|---|
| 001 | 1838735291 | ||
| 003 | DE-627 | ||
| 005 | 20230710152855.0 | ||
| 007 | cr uuu---uuuuu | ||
| 008 | 230309s2010 xx |||||o 00| ||eng c | ||
| 024 | 7 | |a 10.1007/s10107-010-0377-3 |2 doi | |
| 035 | |a (DE-627)1838735291 | ||
| 035 | |a (DE-599)KXP1838735291 | ||
| 035 | |a (OCoLC)1389821048 | ||
| 040 | |a DE-627 |b ger |c DE-627 |e rda | ||
| 041 | |a eng | ||
| 084 | |a 27 |2 sdnb | ||
| 100 | 1 | |a Buchheim, Christoph |e VerfasserIn |0 (DE-588)141261935 |0 (DE-627)62589586X |0 (DE-576)323042538 |4 aut | |
| 245 | 1 | 0 | |a Speeding up IP-based algorithms for constrained quadratic 0-1 optimization |c Christoph Buchheim, Frauke Liers, Marcus Oswald |
| 264 | 1 | |c 08 May 2010 | |
| 300 | |a 23 | ||
| 336 | |a Text |b txt |2 rdacontent | ||
| 337 | |a Computermedien |b c |2 rdamedia | ||
| 338 | |a Online-Ressource |b cr |2 rdacarrier | ||
| 500 | |a Gesehen am 09.03.2023 | ||
| 520 | |a In many practical applications, the task is to optimize a non-linear objective function over the vertices of a well-studied polytope as, e.g., the matching polytope or the travelling salesman polytope (TSP). Prominent examples are the quadratic assignment problem 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, the objective function has 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. Finally, we apply quadratic reformulations of the linear constraints as proposed by Helmberg, Rendl and Weismantel for the quadratic knapsack problem. By extensive experiments, we show that a suitable combination of these methods leads to a drastic speedup in the solution of constrained quadratic 0-1 problems. We also discuss possible generalizations of these methods to arbitrary non-linear objective functions. | ||
| 650 | 4 | |a 90C20 | |
| 650 | 4 | |a 90C27 | |
| 650 | 4 | |a 90C57 | |
| 650 | 4 | |a Crossing minimization | |
| 650 | 4 | |a Local cuts | |
| 650 | 4 | |a Maximum-cut problem | |
| 650 | 4 | |a Quadratic knapsack | |
| 650 | 4 | |a Quadratic programming | |
| 650 | 4 | |a Similar subgraphs | |
| 700 | 1 | |a Liers, Frauke |d 1973- |e VerfasserIn |0 (DE-588)1035378183 |0 (DE-627)747797749 |0 (DE-576)382952472 |4 aut | |
| 700 | 1 | |a Oswald, Marcus |d 1971- |e VerfasserIn |0 (DE-588)138688125 |0 (DE-627)604919719 |0 (DE-576)308608631 |4 aut | |
| 773 | 0 | 8 | |i Enthalten in |t Mathematical programming |d Berlin : Springer, 1971 |g 124(2010), Seite 513-535 |h Online-Ressource |w (DE-627)25491179X |w (DE-600)1463397-8 |w (DE-576)074754874 |x 1436-4646 |7 nnas |a Speeding up IP-based algorithms for constrained quadratic 0-1 optimization |
| 773 | 1 | 8 | |g volume:124 |g year:2010 |g pages:513-535 |g extent:23 |a Speeding up IP-based algorithms for constrained quadratic 0-1 optimization |
| 856 | 4 | 0 | |u https://doi.org/10.1007/s10107-010-0377-3 |x Verlag |x Resolving-System |z lizenzpflichtig |3 Volltext |
| 951 | |a AR | ||
| 992 | |a 20230309 | ||
| 993 | |a Article | ||
| 994 | |a 2010 | ||
| 998 | |g 138688125 |a Oswald, Marcus |m 138688125:Oswald, Marcus |d 110000 |d 110300 |e 110000PO138688125 |e 110300PO138688125 |k 0/110000/ |k 1/110000/110300/ |p 3 |y j | ||
| 999 | |a KXP-PPN1838735291 |e 4285782677 | ||
| BIB | |a Y | ||
| SER | |a journal | ||
| JSO | |a {"language":["eng"],"recId":"1838735291","type":{"media":"Online-Ressource","bibl":"article-journal"},"note":["Gesehen am 09.03.2023"],"person":[{"role":"aut","roleDisplay":"VerfasserIn","display":"Buchheim, Christoph","given":"Christoph","family":"Buchheim"},{"given":"Frauke","family":"Liers","role":"aut","display":"Liers, Frauke","roleDisplay":"VerfasserIn"},{"given":"Marcus","family":"Oswald","role":"aut","display":"Oswald, Marcus","roleDisplay":"VerfasserIn"}],"title":[{"title_sort":"Speeding up IP-based algorithms for constrained quadratic 0-1 optimization","title":"Speeding up IP-based algorithms for constrained quadratic 0-1 optimization"}],"relHost":[{"id":{"zdb":["1463397-8"],"eki":["25491179X"],"issn":["1436-4646"]},"origin":[{"publisherPlace":"Berlin ; Heidelberg","dateIssuedDisp":"1971-","publisher":"Springer","dateIssuedKey":"1971"}],"physDesc":[{"extent":"Online-Ressource"}],"title":[{"title":"Mathematical programming","subtitle":"Series A, Series B ; a publication of the Mathematical Programming Society","title_sort":"Mathematical programming"}],"language":["eng"],"recId":"25491179X","type":{"bibl":"periodical","media":"Online-Ressource"},"note":["Gesehen am 05.05.2023","Gliedert sich in Ser. A u. Ser. B"],"disp":"Speeding up IP-based algorithms for constrained quadratic 0-1 optimizationMathematical programming","part":{"volume":"124","text":"124(2010), Seite 513-535","extent":"23","year":"2010","pages":"513-535"},"pubHistory":["1.1971 -"]}],"physDesc":[{"extent":"23 S."}],"name":{"displayForm":["Christoph Buchheim, Frauke Liers, Marcus Oswald"]},"id":{"doi":["10.1007/s10107-010-0377-3"],"eki":["1838735291"]},"origin":[{"dateIssuedDisp":"08 May 2010","dateIssuedKey":"2010"}]} | ||
| SRT | |a BUCHHEIMCHSPEEDINGUP0820 | ||