M. Pawan Kumar
 
 

HOME

RESEARCH

PUBLICATIONS

GROUP

TALKS

TEACHING

CV

 

 

 

 

 

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.

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 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.

  • Exam Paper for 2015 (PDF)

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 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.

Linear programming is a special case of convex programming where the objective function is linear and the feasible region is a polyhedron. We cover some basics of linear programming including duality and complementary slackness.

Computational Complexity:

  • Decision problems
  • P, NP and NP-complete problems
  • Optimization problems
  • P and NP-hard problems

Linear Programming:

  • Convex sets and convex functions
  • Polyhedra and vertices
  • Linear program: Definition and examples
  • Duality and complementary slackness
  • Optimization

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 NP-hard in general.

Totally unimodular matrices (TUM) are matrices for which every square submatrix has a determinant of 0, 1 or -1. We show how TUM can be used to identify easy problems. Examples of easy problems include minimum st-cut and bipartite matching.

Integer Linear Programming:

  • Integer linear program: Definition and examples
  • Duality relationship
  • Integer polyhedron

Totally Unimodular Matrices (TUM):

  • TUM: Definition and examples
  • TUM and integral vertices
  • Example: Minimum Cut, Maximum Flow
  • Example: Bipartite Matching, Vertex Cover

Slides:

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.

  • Matroids: Definition and examples
  • Greedy algorithm for maximum weight independent set
  • Example: minimum spanning tree
  • Independent set polytope

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.

The union of matroids defines a matroid. The ground set is the union of the ground sets of the constituent matroids. A set is independent if it is the union of independent sets in the constitutent matroids. Matroid union theorem provides the rank function of the resulting matroid in terms of the rank functions of the constituent matroids.

Matroid Intersection:

  • Matroid intersection theorem
  • Common independent set polytope

Matroid Union:

  • Matroid mapping
  • Matroid union theorem

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.

  • Submodular functions and polymatroids
  • Optimization over polymatroids
  • Minimizing a submodular function
  • Montone submodular function maximization under cardinality constraints

Slides:

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.

  • Relaxations
  • Minimum set cover
  • Maximum satisfiability
  • Multiway cut
  • Metric labeling