MA/OR/IE 505 - Linear Programming
Fall 2006, North Carolina State University

Introduction:
This is the official webpage for MA/OR/IE 505 - Linear Programming taught by Kartik Sivaramakrishnan. Please check this page regularly for announcements, course handouts, homeworks, and exams. The webpage should be up to date! However, please send information about missing links and necessary updates to Kartik via email.

Instructor:
Kartik Sivaramakrishnan
Office coordinates: Harrelson Hall 235
Phone: (919) 513-7445
Email: kksivara at ncsu dot edu
Office Hours: T and H - 1-2 pm and by appointment

Time and Place: T and H - 11.45-1.00 pm in Daniels 216.

Teaching Assistant:
YuanYuan Peng (ypeng2 at ncsu dot edu)
Office hours: T and H - 3-4 pm in Burlington 2153.

Course Outline and Policies:

Course schedule:

Computer Programs:
  • AMPL model file for Polly's diet problem
  • AMPL data file for Polly's diet problem
  • Kartik's MATLAB code for the revised simplex method
  • Kartik's MATLAB code for the dual simplex method
  • Kartik's MATLAB session on sensitivity analysis
  • Kartik's Dantzig-Wolfe decomposition code in MATLAB for the block angular LP (26.8) on page 435 of Chvatal
    (requires Kartik's revised simplex code to solve the subproblems)
  • Kartik's branch and bound code for solving mixed integer programs in MATLAB
    (The code requires Kartik's revised simplex and dual simplex codes)
  • A simple primal-dual interior point code in MATLAB
    (Taken from CS 525 taught by Stephen J. Wright at the University of Wisconsin)

    • Information on AMPL, CPLEX, and MATLAB:
  • AMPL Modeling Language for Mathematical Programming
  • Information on writing loops in AMPL can be found here and here
  • ILOG CPLEX: High performance software for mathematical programming and optimization
  • The Optimization Toolbox in MATLAB

    • Class Project:
  • The class project is now available: Due in class on Tuesday, December 5th, 2006.

    • Homework Assignments:

    Handouts:
  • The many facets of linear programming: A nice survey article by Michael Todd
  • The first chapter of the AMPL book: useful for writing your AMPL model and data files
  • LU factorization: Lecture 20 in "Numerical Linear Algebra" by Trefethen and Bau, SIAM, Philadelphia, 1997.
  • LU factorization with pivoting: Lecture 21 in "Numerical Linear Algebra" by Trefethen and Bau, SIAM, Philadelphia, 1997.
  • The Gilmore-Gomory paper on an LP approach for the cutting stock problem
  • The 2nd Gilmore-Gomory paper on the cutting stock problem
  • A survey article on column generation
  • Decomposition methods for large scale linear programming: Chapter 12 in "Applied Mathematical Programming" by Bradley, Hax, and Magnanti, Addison Wesley, 1977.
  • Kartik's lecture notes on the Dantzig-Wolfe decomposition scheme
  • Lecture notes on Benders decomposition by Robert Freund at MIT (The Power Plant Investment Model considered in these notes can be found in this handout on stochastic programming).
  • The Padberg-Rinaldi paper on a branch-and-cut algorithm for solving large scale traveling salesman problems - a classic!
  • Branch and Price Algorithms for solving large scale integer programs
  • Branch and Bound Algorithms for Integer Programming: Chapter 7 in "Integer Programming" by Laurence Wolsey, John Wiley, 1998.
  • An introduction to primal-dual interior point methods for LP: Chapter 1 in "Primal-Dual Interior-Point Methods" by Stephen J. Wright, SIAM, 1997.
  • Kartik's lecture notes on sensitivity analysis: Pages 1,3,5; Pages 2,4,6; Pages 7,9,11; Pages 8,10,12; Page 13; Page 14; Page 15.

    • Exams:
  • The midterm test will be held in class on Tuesday, the 10th of October.
  • The final exam will be in class on Tuesday, the 12th of December between 8-11 am.

    • Solutions to homeworks:

    Supplementary Reading:
  • The Traveling Salesman Problem: Webpage maintained by William Cook at Georgia Tech.
  • References for Linear Programming
  • Linear Programming FAQ
  • Myths and Counterexamples in Mathematical Programming: Maintained by Harvey Greenberg
  • Optimization Online, an eprint site for the optimization community
  • Decision Tree for Optimization Software
  • NEOS Server for Optimization
  • Semidefinite Programming webpage

    • Academic Integrity:
    Please review the guidelines posted at the following website.

    Disability Services for Students:
    "Reasonable accommodations will be made for students with verifiable disabilities. In order to take advantage of available accomodations, students must register with Disability Services for Students at 1900 Student Health Center, Campus Box 7509, 515-7653. For more information on NC State's policy on working with students with disabilities, please see the Academic Accommodations for Students with Disabilities Regulation (REG02.20.1)".
    Last Updated: 12th-December-2006

    Webmaster: Kartik Sivaramakrishnan
    © Copyright 2006