In this course we will consider modern techniques and recent results regarding polyhedra from combinatorial optimization. In the lecture we will introduce basic concepts, present main results and analyze their proofs. In the exercise part the these techniques will be applied to smaller problems and the overall material will be consolidated.
We first consider techniques for comparing the strength of linear relaxations and the strength of adding families of cutting planes, respectively. In the second part we present negative results regarding the (often exponential) number of inequalities that are required for such a relaxation.
After introducing the combinatorial object of a matroid and investigating basic structural properties we will discuss the Greedy algorithm for solving the underlying optimization problem. The algorithm allows us to derive polyhedral results on the associated integer hulls, the so-called matroid polytopes. We furthermore show that even the intersection of two such matroid polytopes is integeral (Matroid Intersection Theorem) and how matroids help to show that optimization over submodular functions can be done in polynomial time.
Here we investigate the phenomenon that a description of a polyhedron may require fewer linear inequalities if one allows to write it as a projection of a higher dimensional polyhedron (an extended formulation). We will discuss several examples and construction techniques for such extended formulations as well as a technique for proving bounds on the possible savings of this phenomenon. We use the latter to show that a description of the cut polytope (associated with the maximum cut problem) requires an exponential number of inequalities, regardless of projections.
We will show that the following problems are equivalent for 0/1-polytopes:
To show this we will analyze the proof of the central result on the equivalence of optimization and separation.