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. Duality in integer programming: (1 week) Lagrangian relaxation methods.
6. Higher order relaxations: (1–2 weeks) Semidefinite programming, lift-and-project, reformulation-linearization.
7. Mixed integer nonlinear programming. (1 week)
8. Heuristic algorithms: (1 week) Greedy algorithms. Feasibility pump.

Lectures: Lecture notes will be posted on LMS.

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 21 (Lecture 18).

Project: The project will involve modeling and computational testing. Depending on the project, the testing may use AMPL or PYOMO or it may use a programming language such as MATLAB or PYTHON 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.

Piazza: This term we will be using Piazza for class discussion. The system is highly catered to getting you help fast and efficiently from classmates and myself. Rather than emailing questions to me, I encourage you to post your questions on Piazza. If you have any problems or feedback for the developers, email team@piazza.com.

Find our class signup link at: https://piazza.com/rpi/spring2023/matp6620

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, course notes, and other information will be available via my homepage,

In addition, an RPI LMS page has been set up for this course. The software package AMPL will be available from there.

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 Head of the Math Sciences department.