16:711:513
Discrete Optimization
Wednesday 30:30 - 6:30 PM
Room 139, RUTCOR building, Busch Campus
Instructor
- Endre Boros,
- Office: 117 RUTCOR building, Busch Campus
- Phone: 732-445-3235
- Email: boros@rutcor.rutgers.edu
- URL: http://rutcor.rutgers.edu/~boros
Office Hours
- After class, or by
appointment.
Exams and Grading
- Final grades will be based on class activity, homeworks and the final.
Syllabus
-
- Review of linear programming, duality theorem, Farkas' lemma, ellipsoid algorithm; complexity theory; a sample combinatorial problem and its analysis.
- Introduction to integer programming, pseudo-Boolean programming, overview of basic algorithms. Introduction to polyhedral combinatorics, analysis of spanning tree problems.
- Greedy algorithms, independence systems, matroids, submodular optimization.
- Short review of network optimization, and shortest path algorithms.
- Matching theory, theorems by Petersen, Berge, König-Egerváry, Frobenius, and Hall. Algebraic and polyhedral descriptions, theorems by Tutte, Berge, Lovász, Gallai, Edmonds, Hoffman and Kruskal, Balinski, Nemhauser and Trotter; the Hungarian method, Edmonds' blossom-shrinking algorithm, and Lovász's algorithm.
- Applications of matchings: chain covers and anti chains and Dilworth theorem; bi-stochastic matrices, theorem by Birkhoff and von Neumann; Euclidean TSP and Christofides' heuristic; maximum cuts in planar graphs.
- Stable matchings, Gale-Shapley theorem, polyhedral results.
- Knapsack problem, dynamic programming and approximation algorithms.
- Cutting-stock problems, Gilmore-Gomory algorithm, bin-packing problems and approximations, theorems by de la Vega and Lueker, Garey, Graham, Johnson and Yao, and Karmarkar and Karp.
- Set covering problems, exact and approximation algorithms, theorems by Lovász and Stein, Chvátal, Johnson, and Papadimotriou and Steiglitz.
- General and binary integer programming, LP relaxation, rounding. Implicit enumeration and branch-and-bound tecniques.
- Unimodularity, total unimodularity, TDI systems; theorems of Hoffman and Kruskal, Veinott and Dantzig, Ghouila-Houri, and Edmonds and Giles.
- Hilbert bases, integer version of Helly's and Caratheodory's theorems; results by Gordan, Doignon, Bell and Scarf, and Cook, Fonlupt and Schrijver.
- Value function, subadditive, surrogate and Lagrangean duality.
- Valid inequalities, cutting planes, Gomory's algorithm, Chvátal cuts, lift-and-project algorithms by Lovász and Schrijver, and by Balas and Ceria.
Books about discrete optimization
-
- W.J. Cook, W.H. Cunningham, W.R. Pulleyblank and A. Schrijver:
Combinatorial Optimization
(Wiley, 1998)
- G. Cornuéjols: Combinatorial Optimization: Packing and Covering (SIAM, 2001)
- B. Korte and J. Vygen: Combinatorial Optimization: Theory and Algorithms (Springer, 2000)
- T. Lengauer:
Combinatorial Optimization in Circuit Layout Design (Wiley, 1990)
- G.L. Nemhauser and L.A. Wolsey:
Integer and Combinatorial Optimization
(Wiley, 1988)
- C.H. Papadimitriu and K. Steiglitz:
Combinatorial Optimization: Algorithms and Complexity (Prentice-Hall, 1982)
- A. Schrijver: Combinatorial Optimization (vols. I-III) (Springer, 2002)
- A. Schrijver:
Theory of Linear and Integer Programming
(Wiley, 1986, reprinted 1999)
- L.A. Wolsey:
Integer Programming
(Wiley, 1998)