Login
- Original title:
- Circuits, Cutting Planes, and Compact Formulations
- Translated title:
- Circuits, Schnittebenen und kompakte Formulierungen
- Author:
- Brugger, Matthias
- Year:
- 2024
- Document type:
- Dissertation
- Faculty/School:
- TUM School of Computation, Information and Technology
- Advisor:
- Schulz, Andreas S. (Prof. Dr.)
- Referee:
- Schulz, Andreas S. (Prof. Dr.); Kaibel, Volker (Prof. Dr.); Borgwardt, Steffen (Prof. Dr.)
- Language:
- en
- Subject group:
- MAT Mathematik
- TUM classification:
- MAT 001
- Abstract:
- We study three fundamental aspects of the theory of integer and linear programming. First, we study polyhedra whose integer hull is obtained by means of certain cutting planes and show that they are hard to recognize. Second, we explore the limitations of a technique for bounding sizes of extended formulations. Finally, we consider circuits and circuit diameters of polyhedra and investigate whether bounded counterexamples to the Hirsch conjecture may disprove its circuit analogue.
- Translated abstract:
- Diese Arbeit widmet sich drei theoretischen Aspekten der ganzzahligen und linearen Optimierung. Zuerst untersuchen wir Polyeder, deren ganzzahlige Hülle sich mit bestimmten Schnittebenen erreichen lässt. Dann beschäftigen wir uns mit den Grenzen einer Technik, um Größen erweiterter Formulierungen zu beschränken. Schließlich betrachten wir Circuits und Circuit-Durchmesser von Polyedern und untersuchen Polytope, die die Hirsch-Vermutung widerlegen, im Circuit-Fall.
- WWW:
- https://mediatum.ub.tum.de/?id=1721226
- Date of submission:
- 26.09.2023
- Oral examination:
- 13.03.2024
- File size:
- 1598779 bytes
- Pages:
- 147
- Urn (citeable URL):
- https://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:bvb:91-diss-20240313-1721226-1-3
- Last change:
- 11.11.2024
BibTeX