Math 4630/5630

Slides and handouts

· Introduction to Discrete Optimization

· Chapter on Integer Programming

· Introduction to Integer Programming

· IP modeling techniques I

· IP modeling techniques II

· IP modeling techniques III

· IP applications handout

· Modeling process

· Solution Methods for Discrete Optimization Problems

· Solution Methods for NP-hard Discrete Optimization Problems

· Chapter on the Simplex Method

· Simplex handout 1 (Important concepts/definitions; graphical solution of LPs; classification of LPs)

· Simplex handout 2 (Towards the simplex method; structure of simplex; definition of basic solutions)

· Simplex handout 3 (Details of simplex method)

· Simplex handout 4 (only the first slide, tableau notation; the rest is optional)

· Simplex handout 5 (Unbounded problems, Multiple optimal solutions; only the first 3 slides, the rest is optional)

· Beale's example on cycling (optional)

· Solving Integer Programs

· Solving graph problems by integer programming (optional)

· Branch-and-Bound I

· Branch-and-Bound II

· Extra problem on Branch-and-Bound (solution in class)

· Cutting Planes I

· Cutting Planes II

· Algorithms for network optimization problems (Min. Spanning Tree, TSP)

· Christofides' algorithm for TSP (optional)

· Chapter on Dynamic Programming

· Deterministic Dynamic Programming

· Stochastic Dynamic Programming (optional)

· Summary of big ideas