MA/OR/IE 505 - Linear Programming
Spring 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 id: kksivara at ncsu dot edu
Office Hours: T and H - 10-11 am and by appointment

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

Teaching Assistant:
Sahar Karimi (skarimi at ncsu dot edu)
Office hours: M and W - 11-12 pm in Burlington 2143.

Course Outline and Policies: The course outline can also be downloaded as the following pdf file ma505outline.pdf.

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 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
  • ILOG CPLEX: High performance software for mathematical programming and optimization
  • The Optimization Toolbox in MATLAB

    • Class Project:
  • Class project is now available: Due in class on Tuesday, April 25th, 2006

    • Homework Assignments:

    Handouts:
  • 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
  • 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.

    Exams:
    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
  • 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
  • Optimization Online, an eprint site for the optimization community
  • Decision Tree for Optimization Software
  • NEOS Server for Optimization

    • 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: 4th-May-2006

    Webmaster: Kartik Sivaramakrishnan
    © Copyright 2006