M. Pawan Kumar 
HOME

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 minmax relationships. Each concept will be illusrated using wellknown problems such as shortest paths, minimum spanning tree, mincut and maxflow. 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:
Shortest Path:
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 (realvalued) 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:
Disjoint Path:
Slides: 3. Minimum Cut, Maximum Flow Summary. Flow is a function on the arcs of a directed graph such that its value is nonnegative, 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 nonnegative arc capacities.
Slides: 4. Matroids 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.
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.
Slides: 6. P, NP, and NPComplete Problems Summary. We will study two types of decision problems (problems with a "yes" or "no" answer): those with a polynomialtime algorithm (P), and those with a polynomialtime checkable certificate (NP). Any NP problem can be reduced to the satisfiability (SAT) problem, which makes SAT NPcomplete. The NPcompleteness of several other problems is proved by reducing SAT to those problems. We also define NPhard problems, which may not have polynomialtime checkable certificates, and may not even be decision problems.
Slides: 7. Approximation Algorithms Summary. We can obtain approximate solutions to NPhard problems using carefully designed efficient algorithms. We will study some wellknown examples of approximation algorithms that are provably accurate.
Lab Sessions 1. Shortest Path Summary. Compute the shortest paths between Paris metro stations using Djikstra's method, BellmanFord method, and FloydWashall method. 2. Minimum Spanning Tree Summary. Compute the minimum spanning tree using Kruskal's method and Prim's method. 34. Minimum Cut, Maximum Flow Summary. Compute the maximum flow and the minimum cut using Dinic's method. 