Discrete Optimization

Currently, this course is taught in the Applied Mathematics and Computer Science stream at MIPT School of Applied Mathematics and Computer Science as an alternative to the functional programming course. Different versions of the course have been taught at MIPT since 2011 as both a special course and a core course.

Important Course News

• Last year’s (2017) open list of questions for those completing the course on the coding track.

Course Logistics

• Students who are only taking the DO course can complete it through one of two “tracks”:
  • theory track: write theory tests during seminars and a final theoretical assignment
  • coding track: write programs in Python 3, and at the end of the semester take a written test on definitions and formulations from a pre-announced list of possible questions

Assignments

• The file with seminar problems and theory track homework is available at this link.

Lectures

• Slides from some of last year’s lectures can be found at this link.
• Renato Werneck’s lecture on the shortest path problem, slides 20-36.

Lecture Plan

• Distinctive features of discrete optimization problems. Overview of classical discrete optimization problem formulations: set covering, vertex cover, shortest path, minimum spanning tree, matching problems, assignment problems, scheduling theory problems, packing problems (bin packing, knapsack), flow problems (maximum flow, minimum cost flow, multi-commodity flows), transportation problem (Hitchcock problem), traveling salesman problem.
• Local search as a broad general approach to solving discrete optimization problems. Neighborhood systems. Example of neighborhood system in TSP: trade-off between neighborhood strength and size. Example where 2-neighborhood cannot achieve global optimum. Kernighan-Lin heuristic: variable depth local search. Local search extensions: simulated annealing and tabu search.
• Non-existence of polynomially-sized exact neighborhood system in TSP (assuming \(\mathrm{P}\neq \mathrm{NP}\)). Local greedy heuristics in TSP not explicitly fitting the local search paradigm (not transitioning between cycles but building cycle from scratch). Quality measures for heuristic (approximate) algorithms: approximation ratio and domination number. Nearest neighbor algorithm: idea, theorem that approximation ratio is bounded above by \(O(\log \text{#vertices})\).
• Discrete Linear Subset (DLS) problem. TSP and MST as special cases of DLS minimization problems; transition to maximization. Hereditary systems. Bases and circuits. Rank and lower rank of a set, rank spread. Matroids: equivalent definitions, examples. Quality estimation of greedy algorithm on hereditary system through its rank spread. Corollary about correctness of greedy algorithm for minimum spanning tree construction. Rank spread estimation through bound on number of circuits. Submodularity of matroid rank function. Matroid intersection. Circuit number estimation for hereditary system through number of matroids in intersection. Probability of DLS problem solution uniqueness with random weight selection: isolation lemma and its two proofs (J. Spencer and N. Ta-Shma).
• Prim’s and Borůvka’s algorithms for MST problem: examples, implementation (without heaps). Prim’s algorithm using Fibonacci heaps.
• Discrete homogeneous resource allocation problems: discrete maximin problem, maximization of sum of concave functions. Optimality criteria (Germeier’s equalization principle, Gross criterion). Two algorithms for solving discrete maximin problem. Product optimization with fixed sum.
• Review of basic linear programming concepts. Standard and canonical form problems. Transition between inequalities and equations. Problem geometry: simplex algorithm as local search over polytope vertices.
• Example of polytope where simplex algorithm may require exponentially many steps under certain conditions: Klee-Minty theorem. Upper bound on number of steps for “lucky simplex method”: Kalai-Kleitman theorem on polytope graph diameter.
• Introduction to smoothed analysis of algorithms: average between random input analysis and worst-case analysis. Spielman-Teng theorem on simplex method.
• Duality in linear programming: dual problem solution as optimality certificate for primal problem solution. Fourier-Motzkin elimination. Farkas lemma: existence of certificate for linear inequality system infeasibility. Derivation of strong duality theorem from Farkas lemma. Economic interpretation of duality in bargaining problem.
• TSP formulations in terms of integer linear programming. Miller-Tucker-Zemlin constraints (polynomial number of inequalities in TSP). Note on “non-catastrophic nature of exponential number of constraints in LP problems”.- Простой «комбинаторный» алгоритм для задачи о вершинном покрытии (ВП) с approximation ratio = 2. Постановка задачи о взвешенном вершинном покрытии (ВВП) в терминах целочисленного линейного программирования. Алгоритм решения задачи ВВП вида «решаем задачу ЛП → округляем»; утверждение о том, что достигается approximation ratio = 2. Формулировка двойственной задачи к задаче ВВП: потенциалы на рёбрах. «Комбинаторный» (без использования ЛП) алгоритм решения задачи ВВП на основе двойственности; доказательство того, что для этого алгоритма approximation ratio = 2.
• General covering problem (equivalent to Set Cover problem). Matrix formulation. Integer linear programming formulation, dual problem formulation. Theorem that size/weight of greedy cover is no more than \(\ln k\) times larger than optimal size/weight (where \(k\) is maximum number of ones in a row). Achievability (in order) of this estimate. Estimation of greedy cover weight through optimal weight with bounded weights of individual rows.
• Maximum cardinality matching problem in arbitrary graph. Augmenting paths (statement that matching is not maximal ⇔ there exists augmenting path). Problem with finding augmenting paths without bipartiteness: blossoms. Statements about blossom contraction. Edmonds’ algorithm.
• Dijkstra’s algorithm modifications for fast practical solution of shortest path problem: “bidirectional” Dijkstra’s algorithm, use of landmarks (in case of triangle inequality).
• Floyd-Warshall algorithm for finding shortest paths and negative weight cycles.
• Minimum cost flow problem (with fixed value). Two algorithms: gradual minimization of flow cost at constant value; value increment through minimal possible cost increment.
• “Biological” metaheuristics: genetic algorithms, ant colony algorithms. Illustration on shortest path and TSP problems.
• Branch and bound method.
• Exhaustive enumeration problems for complex discrete objects. Read’s approach: ordered enumeration. Avis-Fukuda method: reverse search.
• Online optimization. “Buy vs. rent” problem. “Secretary problem”. Analysis of LRU (Least Recently Used) caching algorithm. Heuristic algorithms in Bin Packing problem.
• On the concept of reoptimization. NP-hardness of exact solution for reoptimization in metric TSP when increasing weight of one edge. Approximation algorithms for reoptimization with better approximation ratio than Christofides’ algorithm, when increasing weight of one edge and when adding one vertex to the graph.

Useful Links

• Claire Mathieu’s courses on approximation algorithms on Coursera: Part 1 and Part 2
• Pascal Van Hentenryck’s course Discrete Optimization on Coursera.
• James Stuckey’s course Modeling Discrete Optimization on Coursera.
• Friedrich Eisenbrand’s course Linear and Discrete Optimization on Coursera.
• Ant Colony Optimization and Evolutionary Multiobjective Optimization demos on Wolfram Demonstrations Project.
• Graphical Linear Programming for Two Variables, Graphical Linear Programming for Three Variables, The Fundamental Theorem of Linear Programming and Graph of Inequalities demos on Wolfram Demonstrations Project.
• Free package for solving linear optimization problems LPSolve. Libraries exist for many programming languages that allow using LPSolve functions. Example script for LPSolve.
• Powerful software environment for solving optimization problems IBM ILOG CPLEX with its own programming language OPL. Can be downloaded and used free for 90 days.
• Catalog of applied problems where matching problem is used
• Website entirely dedicated to TSP, including catalog of applied problems
• TSP Software — catalog of solvers for TSP
• David Johnson’s slides on traveling salesman problem
• Catalog of papers on smoothed analysis

Literature

• S. Dasgupta, C. Papadimitriou, U. Vazirani. Algorithms. Moscow: MCCME, 2014.
• A. A. Korbut, Yu. Yu. Finkelstein. Discrete Programming. Moscow: Nauka, 1969.
• C. H. Papadimitriou, K. Steiglitz. Combinatorial Optimization: Algorithms and Complexity. Moscow: Mir, 1985. (Original: Dover Publications, 1998.)
• T. L. Saaty. Integer Methods of Optimization and Related Extremal Problems. Moscow: Mir, 1973. (Original: Optimization in Integers and Related Extremal Problems. McGraw-Hill, 1970.)
• I. Kh. Sigal, A. P. Ivanova. Introduction to Applied Discrete Programming: Models and Computational Algorithms. Moscow: Fizmatlit, 2003.
• D. Avis, K. Fukuda. Reverse search for enumeration // Discrete Appl. Math. 65. 1996. pp. 21–46.
• W. J. Cook, W. H. Cunningham, W. R. Pulleyblank, A. Schrijver. Combinatorial Optimization. Wiley, 1997.
• C. P. Gomes, H. Kautz, A. Sabharwal, B. Selman. Satisfiability Solvers // Handbook of Knowledge Representation. Elsevier, 2008.
• H. J. Greenberg. Myths and Counterexamples in Mathematical Programming
• S. Jukna. Extremal Combinatorics (2nd edition). Springer, 2011.
• B. Korte, J. Vygen. Combinatorial Optimization: Theory and Algorithms (5th edition). Springer-Verlag, 2014. Russian translation available: B. Korte, J. Vygen. Combinatorial Optimization. Theory and Algorithms. Moscow: MCCME Publishing, 2015.
• J. Matoušek, B. Gärtner. Approximation Algorithms and Semidefinite Programming. Springer, 2012.
• J. Matoušek, B. Gärtner. Understanding and Using Linear Programming. Springer, 2007.
• R. C. Read. Every One a Winner or How to Avoid Isomorphism Search When Cataloguing Combinatorial Configurations // Annals of Discrete Math. 2. 1978. pp. 107–120.
• A. Schrijver. A Course in Combinatorial Optimization. 2013.
• L. Trevisan. Combinatorial Optimization: Exact and Approximate Algorithms. 2011.
• V. V. Vazirani. Approximation Algorithms. Springer, 2002.
• V. V. Vazirani. A proof of the MV matching algorithm. 2014.

For the lecture on reoptimization:

• H.-J. Böckenhauer, J. Hromkovič, T. Mömke, P. Widmayer. On the Hardness of Reoptimization // SOFSEM 2008: Theory and Practice of Computer Science. Lecture Notes in Computer Science, Volume 4910, 2008. P. 50-65.
• N. Guttmann-Beck, R. Hassin, S. Khuller, B. Raghavachari. Approximation Algorithms with Bounded Performance Guarantees for the Clustered Traveling Salesman Problem // Algorithmica, 2000, Vol. 28. Pp. 422-437.
• G. Ausiello, B. Escoffier, J. Monnot, V. Paschos. Reoptimization of minimum and maximum traveling salesman’s tours // Journal of Discrete Algorithms 7 (2009). 453–463.