M. Pawan Kumar
 
 

HOME

RESEARCH

PUBLICATIONS

GROUP

TALKS

TEACHING

CV

 

 

 

 

 

Introduction to Discrete Optimization

Instructor: M. Pawan Kumar

Discrete optimization is concerned with the subset of optimization problems where some or all of the variables are confined to take a value from a discrete set. Examples include several important problems in various fields of applied mathematics and computer science, such as

  • Finding the best (shortest, cheapest, most scenic) route from one place to another.
  • Connecting cities using a road network that minimizes the cost.
  • Selecting a subset of projects, each requiring a subset of available resources, to maximize profit.
  • Finding the best assignment of students to universities.

In this course, we will study the fundamental concepts of discrete optimization such as greedy algorithms, dynamic programming and min-max relationships. Each concept will be illusrated using well-known problems such as shortest paths, minimum spanning tree, min-cut and max-flow. We will also identify which problems are easy and which problems are hard, and briefly discuss how to obtain an approximate solution to hard problems.

Course Outline

The course consists of seven lectures (3 hours each) on the following topics:

In addition, there will be four lab sessions (3 hours each) where the students will write the code for the following problems:

Grading

Students will be evaluated based on their lab work (50%) and a final exam that will last 3 hours (50%). The use of printed materials such as slides, notes and textbooks will be permitted during the exam. No electronic devices will be allowed. Bonus points will be available for class participation and would likely play a very important role in your final grade.

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

Summary. Given a directed graph (vertices, arcs and arc lengths), the goal is to find the minimum length or shortest path from one vertex to another. This problem can be solved efficiently when the graph does not contain a negative length directed circuit.

Preliminaries:

  • Graph preliminaries
  • Complexity preliminaries

Shortest Path:

  • Breadth-first search
  • Djikstra's algorithm
  • Bellman-Ford algorithm
  • Floyd-Warshall algorithm

Slides:

2. Minimum Spanning Tree, Disjoint Paths

Summary. Given an undirected graph (vertices, edges and edge lengths), a spanning tree is a subgraph that consists of all vertices and whose edges form a tree. The minimum spanning tree problem requires us to find the spanning tree with the minimum length. The problem can be solved efficiently for arbitrary (real-valued) edge lengths. Given a directed graph, the disjoint paths problem requires us to find the maximum number of arc disjoint paths between two vertices, where two paths are arc disjoint if they do not contain a common arc. The problem is equivalent to finding the maximum number of vertex disjoint paths between two subset of vertices, and the maximum number of internal vertex disjoint paths between two vertices. All the disjoint path problems can be solved efficiently.

Minimum Spanning Tree:

  • Prim's algorithm
  • Kruskal's algorithm

Disjoint Path:

  • Menger's theorem(s)
  • Algorithm for finding maximum number of arc-disjoint paths

Slides:

3. Minimum Cut, Maximum Flow

Summary. Flow is a function on the arcs of a directed graph such that its value is non-negative, less than the length (or capacity) of the arc, and for all vertices other than a source vertex and a sink vertex, the excess flow is 0. The maximum flow problem requires us to find the flow with the maximum value. A cut is a set of arcs from one subset of vertices that contain the source to another subset of vertices that contain the sink. The minimum cut problem requires us to identify the subsets of vertices which minimize the capacity of the cut. The maximum flow problem and the minimum cut problem are equivalent to each other, and both can be solved efficiently for directed graphs with non-negative arc capacities.

  • Max-Flow Min-Cut theorem
  • Ford-Fulkerson algorithm
  • Dinit's algorithm

Slides:

4. Matroids

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.

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

Slides:

5. Submodular Functions

Summary. A submodular function is a set function that satisfies the diminishing returns property. We will show how a pairwise submodular function can be minimized by computing the minimum cut on an appropriate digraph.

  • Submodular functions
  • Pairwise submodular functions
  • Minimizing pairwise submodular functions via min-cut

Slides:

6. P, NP, and NP-Complete Problems

Summary. We will study two types of decision problems (problems with a "yes" or "no" answer): those with a polynomial-time algorithm (P), and those with a polynomial-time checkable certificate (NP). Any NP problem can be reduced to the satisfiability (SAT) problem, which makes SAT NP-complete. The NP-completeness of several other problems is proved by reducing SAT to those problems. We also define NP-hard problems, which may not have polynomial-time checkable certificates, and may not even be decision problems.

  • Random access machine
  • Cook's theorem
  • Reductions

Slides:

7. Approximation Algorithms

Summary. We can obtain approximate solutions to NP-hard problems using carefully designed efficient algorithms. We will study some well-known examples of approximation algorithms that are provably accurate.

  • Multiway cut
  • Maximum cut

Lab Sessions

1. Shortest Path

Summary. Compute the shortest paths between Paris metro stations using Djikstra's method, Bellman-Ford method, and Floyd-Washall method.

2. Minimum Spanning Tree

Summary. Compute the minimum spanning tree using Kruskal's method and Prim's method.

3-4. Minimum Cut, Maximum Flow

Summary. Compute the maximum flow and the minimum cut using Dinic's method.