MATP6640 / ISYE6770 Linear Programming
Office hours: Tuesdays 2-4pm, Wednesdays 11am-1pm, or by appointment.
on reserve in the library.
Scores are available on LMS
- Homework 1: Mean 42.9/50, median 42, min 36, max 48, standard deviation 3.3.
- Homework 2: Mean 51.6/60, median 52, min 37, max 60, standard deviation 6.7.
A version of AMPL along with current versions of solvers
(including cplex 12.6) is available
Handwritten scanned copies of my notes from previous semesters (pdf files):
- Introduction, basic feasible solutions,
duality, and the simplex algorithm.
- Introduction: January 21: Pages 1-8.
Pages 5-8 are covered in
- Basic feasible solutions, degeneracy: January 24: Pages 9-19.
- Duality: January 28: Pages 20-29.
- The simplex algorithm: January 31: Pages 30-42.
See also two handouts.
- Multiple optimal solutions, handling free variables
and upper bounds: February 4: Pages 43-50.
See also a handout.
- Revised simplex, resolution.
- February 4:
Revised simplex method, pages 1-8.
- February 7:
Dual simplex method, via a
Fourier-Motzkin elimination, pages 16-22.
Resolution, pages 9-15.
The Weyl and Minkowski theorems, pages 23-28.
- February 11:
Using Farkas to prove strong duality, page 29.
Klee Minty cube: February 11.
analysis of the simplex method: February 11.
Focus on the results on pages 4, 5, and 9.
ellipsoid method: February 14.
- Dantzig-Wolfe decomposition,
cutting stock problems, network simplex, multicommodity network flows.
- February 14: introduction to Dantzig-Wolfe, pages 1-5.
- February 21 and 25: Dantzig-Wolfe iteration and behavior, block angular structure,
pages 6-17. Also,
an example of Dantzig-Wolfe decomposition.
- February 25 and 28: Lagrangian relaxation, cutting stock problems, pages 18-27.
- March 4 and 7:
Network simplex, multicommodity network flow problems,
Here are some
notes on network flows.
- Stochastic programming:
March 7 and 18.
The results on sample average approximation can be found
tutorial on stochastic programming
by Shapiro and Philpott.
to interior point methods:
strict complementarity, the central path,
primal-dual framework, complexity theory, affine methods,
the centering direction, a potential-reduction method.
Pages 1, 3-8 covered on March 21.
Pages 2, 9-22 covered on March 25.
Pages 24-27 and 29 covered on April 1.
Pages 32-40 covered on April 4.
- Barrier methods.
Pages 6-20 covered on March 28.
- Long-steps, quadratic convergence, predictor-corrector,
finite termination, crossover, infeasible methods.
Pages 11-16 covered on April 8.
Pages 6-10 covered on April 11.
- Homogenized methods,
Mehrotra's predictor-corrector, sparse linear algebra,
interior point cutting plane methods.
Pages 1-4 covered on April 8.
Pages 5-9 covered on April 11.
Pages 10-14 summarized in ten minutes on April 11.
Pages 19-25 covered on April 15.
Slides 3/72 to 30/72 of this
on interior point cutting plane methods were covered on April 15.
The talk is based on a
Pages 1-7 covered on April 15.
Pages 18-20 covered on April 22.
Pages 13-15, 17, 27, and 30 covered on April 25.
Pages 8-12, 22-26, 31-32 covered on April 29.
Pages 16, 28-29, and 33 covered on May 2.
The example on sensor location is
Page 21 covered on May 6.
Pages 35/72 to 53/72 and 67/72 to 69/72 from this
on interior point cutting plane methods should be covered.
It is based on a
by Boyd and Vandenberghe, contains a wealth of material on SDP, SOCP,
and conic programming.
- Completely positive programming. May 6.
- The material on linear programs with complementarity constraints
on May 6 is from two talks:
slides 4/54 to 14/54 from
and slides 12/41 to 24/41 from
algebra. (Jan 24.)
affine sets, convex sets, and cones. (Jan 24.)
- Dimension, polyhedra, and
faces. (Jan 24.)
An iteration of the simplex algorithm
the algorithm. (Feb 3.)
Handling upper bounds in
the simplex algorithm. (Feb 7.)
- The dual simplex
algorithm. (Feb 10.)
- Extreme points
and extreme rays of polyhedra. (Feb 17.)
- An example of Dantzig-Wolfe decomposition. (February 21.)
Papers and resources:
John Mitchell's homepage.