M. Pawan Kumar 
HOME

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 optimizationboth 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 wellknown problems such as bipartite matching, mincut, maxflow 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, NPhard 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. Course Outline The course consists of seven lectures (3 hours each) on the following topics: Part I  Exact Algorithms
Part II  Approximate Algorithms Grading Students will be evaluated based on a takehome 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.
Resources 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. Additional Material:
Lectures 1. Preliminaries: Computational Complexity, Linear Programming Summary. Decision problems in the class P are those that admit an optimal polynomialtime solution. Decision problems in the class NP are those that have a polynomialtime checkable certificate. NPcomplete problems are the hardest problems in NP. P optimization problems are those that admit an optimal polynomialtime solution. NPhard optimization problems are at least as hard as NPcomplete problems. Computational Complexity:
Linear Programming:
Slides: 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 NPhard in general. Integer Linear Programming:
Totally Unimodular Matrices (TUM):
Slides: 3. Matroids, Greedy Algorithm for Maximum Weight Independent Set Summary. A matroid is a pair of a finite ground set and a nonempty 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.
Slides: 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. Matroid Intersection:
Matroid Union:
Slides: 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.
Slides: 67. Relaxations for NPHard Problems Summary. NPhard 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 NPhard problems.
