MATP6620 / DSES6760
Combinatorial Optimization and Integer Programming

January 8, 2009

MR 10:00-11:50 Carnegie 101 Spring 2009

Course Outline

I intend to follow this outline fairly closely, but, if appropriate, I will alter what is included in the course. Problems such as node packing, the traveling salesman problem, the knapsack problem, the quadratic assignment problem, and the MaxCut problem, will be discussed throughout the course.

1. Fundamentals: (1-2 weeks) Linear programming. Graph theory and network flows.
2. Algorithm complexity and NP-completeness: (2-3 weeks) Analysis of algorithms. Polynomial time algorithms. Separation and optimization problems. The ellipsoid method and its consequences for combinatorial optimization.
3. Branch-and-bound. (1 week)
4. Polyhedral theory and cutting plane methods: (3 weeks) Facets of polyhedra. Gomory's cutting plane procedure. Chvatal cuts. Knapsack problem. Branch-and-cut.
5. Heuristic algorithms: (1 week) Simulated annealing. Tabu search. Genetic algorithms.
6. Duality in integer programming: (1 week) Lagrangian relaxation methods.
7. Higher order relaxations: (1-2 weeks) Semidefinite programming, lift-and-project, reformulation-linearization.
8. Mixed integer nonlinear programming. (1 week)

Homework: Approximately every two weeks.

Homework and exam solutions will be made available online. The homeworks will probably contain some computational work. 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.

Exam: One in-class midterm.

As you would expect, the exam must be all your own work. It will take place on or about March 30.

Project:

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. The presentation will take place either on the last day of class or during the time scheduled for a final exam. 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:

• A cutting plane approach to an integer programming problem. The cutting plane methods will require the use of AMPL or the CPLEX callable library or a package from COIN-OR (or C or Fortran).
• A semidefinite programming relaxation approach to an integer programming problem. This will require the use of an SDP package (written in MATLAB).
• Investigation of a heuristic method or of a relaxation approach for an integer programming problem.

Grading policy: $\frac{1}{3}$ homeworks, $\frac{1}{3}$ midterm, $\frac{1}{3}$ project/presentation.

Office hours: Monday 1-3pm or by appointment

Student learning objectives: Develop a thorough understanding of the theory and algorithms of combinatorial optimization and integer programming.

Textbooks:

Required:
		Nemhauser and Wolsey, Integer and Combinatorial Optimization. Wiley, 1988 (paperback 1999). Very detailed, and a standard reference.
Recommended:
		Papadimitriou and Steiglitz, Combinatorial Optimization: Algorithms and Complexity. Prentice Hall 1982. A good alternate text. More graph theory, less polyhedral theory than N&W. Reprinted by Dover in 1998.
Also on reserve:
		Wolsey, Integer Programming. Wiley 1998. Better coverage of heuristics and a little more up-to-date than Nemhauser and Wolsey.
		Lee, A First Course in Combinatorial Optimization. Cambridge University Press, 2004. Available .
		Schrijver, Combinatorial Optimization: Polyhedra and Efficiency. Springer Verlag, 2004. Three volumes, encyclopedic, but still only costing about $100.
		Garey and Johnson, Computers and Intractability. Freeman, 1979. The bible of NP-completeness.

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

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

In addition, an RPI LMS page has been set up for this course.

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.

You may be able to find solutions to some of the homework problems online. Do not use these solutions.

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