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 April 8.

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 MATLAB or C or FORTRAN. You will write up your solution and give a presentation in class. The presentation will take place either during the last week of classes 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.

Student learning objectives: Develop a thorough understanding of the theory and algorithms of combinatorial optimization and integer programming. An ability to apply knowledge of mathematics, science and engineering. An ability to design and conduct experiments, as well as to analyze and interpret data. An ability to identify, formulate and solve engineering problems.

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

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 are turned off during class.