|M. Pawan Kumar|
Foundations of Polyhedral Combinatorial Optimization
Instructor: M. Pawan Kumar
Polyhedral techniques have emerged as one of the most powerful tools to analyse and solve combinatorial optimization problems. Broadly speaking, many combinatorial optimization problems can be formulated as integer linear programs. By dropping the integer constraints, we obtain a linear program that can be solved efficiently. This seemingly simple approach lies at the heart of the most successful methods in combinatorial optimization---both in theory and in practice.
In this course, we will study the fundamental concepts of polyhedral techniques such as totally unimodular matrices, matroids and submodular functions. Each concept will be illustrated using well-known problems such as bipartite matching, min-cut, max-flow and minimum spanning tree. The course is divided into two parts. In the first part, we will study easy problems (those that admit efficient optimal algorithms). We will use polyhedral techniques to explain why these problems are easy. In the second part, we will study hard problems (specifically, NP-hard problems). We will use polyhedral techniques to obtain provably accurate approximate solutions for various hard problems. We will also briefly discuss the hardness of obtaining accurate approximate solutions.
The course consists of seven lectures (3 hours each) on the following topics:
Part I - Exact Algorithms
Part II - Approximate Algorithms
Students will be evaluated based on a take-home exam. The exam for 2015 is now available (link provided below). You have until Friday 27/3 4pm CET to answer these questions. You can drop your answer sheets in the box in front of my office (A209, Dumas Annexe). The use of course slides is permitted. However, you are not allowed to use textbooks or the Internet. You are also not allowed to discuss these problems with each other.
Slides for all the lectures are available in PPTX and PDF format. Note that the PPTX versions contain animations, which will not be visible in the PDF versions. The slides were made on a Mac, and may not be completely compatible with the Windows version of Powerpoint.
1. Preliminaries: Computational Complexity, Linear Programming
Summary. Decision problems in the class P are those that admit an optimal polynomial-time solution. Decision problems in the class NP are those that have a polynomial-time checkable certificate. NP-complete problems are the hardest problems in NP. P optimization problems are those that admit an optimal polynomial-time solution. NP-hard optimization problems are at least as hard as NP-complete problems.
2. Integer Linear Programming, Totally Unimodular Matrices
Summary. Similar to linear programs, integer linear programs optimize a linear function under linear constraints. However, additionally, they require the
optimization variables to take integral values. Integer linear programs are NP-hard in general.
Integer Linear Programming:
Totally Unimodular Matrices (TUM):
3. Matroids, Greedy Algorithm for Maximum Weight Independent Set
Summary. A matroid is a pair of a finite ground set and a non-empty collection of subsets of the ground set (called independent sets) that satisifies the hereditary property and the augmentation property. Given the weights of the elements of the ground set, a greedy algorithm provides the maximum weight independent subset. Example applications of the greedy algorithm include finding the minimum spanning tree of a graph. A precise characterisation of the independent set polytope is possible.
4. Matroid Intersection, Matroid Union
Summary. The intersection of two matroids defined on the same ground set need not necessarily result in another matroid. However, it is possible
to obtain the largest common independent set of two matroids using the matroid intersection theorem. Furthermore, a precise characterisation of the common
independent set polytope is possible.
5. Submodular Functions
Summary. A submodular function is a set function that satisfies the diminishing returns property. The (extended) polyhedron defined by a submodular function is called the (extended) polymatroid associated with the submodular function. A linear function can be optimized over the (extended) polyhedron using the greedy method. Submodular functions can be minimized efficiently. We will also briefly cover monotone submodular function maximization under simple cardinality constraints.
6-7. Relaxations for NP-Hard Problems
Summary. NP-hard problems can be formulated as integer programs, which can then be relaxed to convex programs by dropping the integer constraints. Through various examples, we illustrate that convex relaxations provide provably accurate approximate solutions for NP-hard problems.