On the Proof Complexity of Linear Programming Based Branch-and-Bound
Gläser, Maximillian
Produktnummer:
180aaa1b6d3c1d44f1961a006d1b70b5ea
| Autor: | Gläser, Maximillian |
|---|---|
| Themengebiete: | Branch-and-Bound Integer Programming Lineare und ganzahlige Programmierung |
| Veröffentlichungsdatum: | 11.11.2024 |
| EAN: | 9783843955300 |
| Sprache: | Englisch |
| Seitenzahl: | 171 |
| Produktart: | Kartoniert / Broschiert |
| Verlag: | Dr. Hut |
Produktinformationen "On the Proof Complexity of Linear Programming Based Branch-and-Bound"
This thesis investigates the proof system associated to the branch-and-bound method for linear integer programming, that is, we treat branch-and-bound trees as proofs of the integer-freeness of certain polyhedra (equivalently, of the infeasibility of integer linear programs). We treat both the proof system resulting from branch-and-bound branching on variable disjunctions as well as the one resulting from branching on general disjunctions. We investigate lower bounds for these proof systems, their automatizability and the complexity of estimating the minimum required size of a tree. In particular, we derive the first super-polynomial lower bound for branch-and-bound using general disjunctions via interpolation.
Sie möchten lieber vor Ort einkaufen?
Sie haben Fragen zu diesem oder anderen Produkten oder möchten einfach gerne analog im Laden stöbern? Wir sind gerne für Sie da und beraten Sie auch telefonisch.
Juristische Fachbuchhandlung
Georg Blendl
Parcellistraße 5 (Maxburg)
8033 München
Montag - Freitag: 8:15 -18 Uhr
Samstags geschlossen