|M. Pawan Kumar|
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
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.
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:
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.
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. 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.
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:
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.
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.
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.
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.
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.
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.