MATP6640/DSES6770 Linear Programming

MR 10:00-11:50, Carnegie 101
Spring 2008

Course Outline: Optimization is concerned with optimal allocation of resources, and linear programming is the fundamental optimization problem. There has been a great deal of progress in linear programming and huge problems can now be solved routinely using two different types of approaches -- the simplex method and interior point methods. This course discusses these two classes of approaches, the theory underlying them, and extensions of the approaches.

1. Polyhedral theory: (2 weeks) The feasible region of a linear programming problem is a polyhedron, ie, the intersection of a finite collection of half spaces. The structure of polyhedra is discussed, including the Goldman Resolution theorem, and the Weyl and Minkowski theorems.
2. The simplex algorithm: (1-2 weeks) The simplex method is the traditional method for solving linear programming problems. I will discuss the simplex method in matrix terms, and indicate how it can be implemented efficiently.
3. Decomposition and column generation methods for large scale problems: (2 weeks) Some large linear programs can be broken into smaller ones and the polyhedral structure of linear programming can be exploited to develop an algorithm. For other problems, the number of variables is very large and an attractive approach is to generate columns of the constraint matrix only as needed.
4. The ellipsoid algorithm: (1 week) The ellipsoid algorithm was the first polynomial algorithm for linear programming. It was developed originally as an algorithm for nonlinear programming.
5. Interior point methods: (8 weeks) Topics to be discussed include the similarity of these algorithms to traditional nonlinear programming methods, the polynomial complexity of many of these algorithms, the asymptotic rate of convergence of the algorithms, and the computational results achieved. Interior point methods for semidefinite programming and second order cone programming problems will be discussed. Efficient linear algebra techniques will also be discussed.

Grading policy: The grade will be determined by three elements: homework, a midterm exam, and a project. The three elements will be equally important. For the purposes of Mid-Term Assessment, homework and exam scores will be posted online, with identifying data removed.

I will give out a homework approximately every two weeks. The homeworks will probably contain some computational work using AMPL, a mathematical programming modeling language. You should learn a fair amount from the homeworks. Therefore, try working out the solutions on your own. If you have difficulties, you may talk to me or to other students about the homeworks, but you must write up your solutions on your own. You may be able to find the solutions to some of the homework questions on the web: do not use these solutions!

There will be an in-class midterm exam on about Thursday, April 3. The exam must be all your own work.

The project will involve modeling and computational testing. Depending on the project, the testing may use AMPL or it may use a programming language such as AMPL or C or FORTRAN. You will write up your solution and give a presentation in class. Your project can be one of the following:

• a topic arising in your research that fits well with the topics covered in the course. You would work on your own on such a project.
• another project you suggest or I suggest. You can work in groups of up to three people on such a project. All group members should contribute equally to the project. Each individual should turn in a one-page description of their contribution to the project along with the group report.

Possible topics include:

• Install a COIN-OR package on cmc-math, and get some computational results. Create instructions so anyone can run the package.

• Benchmark some solvers: eg MOSEK vs CPLEX for SOCP problems

• Develop a column generation or cutting plane algorithm for an integer program or another hard optimization problem.

• Investigate warm-starting methods for semidefinite programming.

• Combine interior point and simplex cutting plane algorithms: start with interior point, crossover to simplex.

• Combine Dantzig-Wolfe decomposition with simplex: Use DW to get a good solution, create a bfs, finish off.

• Compare two different approaches. Eg, compare CPLEX LP solver with some linear cuts to CPLEX socp for an SOCP.

Student learning objectives: Develop a thorough understanding of the theory and algorithms of linear programming.

Textbooks:

		V. Chvátal, Linear Programming. Freeman, 1983. Covers most of the first half of the course.
		S. Wright, Primal-dual Interior Point Methods. SIAM, 1997. Covers most of the second half of the course.

Because there is considerable continuing research on interior point methods, I will draw some material from current papers. I will put links to several papers on the course webpage as the course progresses. The following textbooks each cover part of the course and are on reserve in the library.

		K. G. Murty, Linear Programming. Wiley, 1983. Similar to Chvátal.
		Roos, Terlaky, and Vial, Theory and Algorithms for Linear Optimization. Wiley, 1997. Excellent for interior point methods.
		R. Vanderbei, Linear Programming. Kluwer, 1996. Good coverage of both simplex and interior point methods.
		Y. Ye, Interior Point Algorithms. Wiley, 1997. Very good for interior point methods, with an emphasis on potential reduction methods.
		Fiacco and McCormick, Nonlinear programming; sequential unconstrained minimization techniques. Wiley, 1968. Reprinted by SIAM. The techniques presented in this book can be specialized to give interior point methods for linear programming.

    

Prerequisites: MATP4700/DSES4770, or permission of instructor. Familiarity with linear programming and linear algebra will be assumed. Some elements of MATP6600/DSES6780 and MATP4820/DSES4780, such as the Karush-Kuhn-Tucker optimality conditions and Newton's method, will be used, although it is not necessary to have seen this material before.

The World Wide Web: This outline, the homeworks, and other information will be available via my homepage,

http://www.rpi.edu/~mitchj/matp6640

Academic Integrity: Student-teacher relationships are based on mutual trust. Acts which violate this trust undermine the educational process. The Rensselaer Handbook defines various forms of academic dishonesty and procedures for responding to them. The penalties for cheating can include failure in the course, as well as harsher punishments.

Appealing grades: As with any other administrative question regarding this course, see me in the first instance. If we are unable to reach agreement, you may appeal my decision to the Chair of the Math Sciences department.

Cell phones: Please make sure that cell phones and pagers are turned off during class. If your cell phone disrupts class, you are expected to bring candy or cookies for everyone at our next class.

	John Mitchell	276-6915
	Amos Eaton 325	mitchj at rpi dot edu
	Office hours: Thursdays 2-4pm, or by appointment.