Mathematical programming

General information

Lecture times: Tuesday, Thursday 8.35-9.55am.
Room: Burnside, 920.
Instructor: Nicolas Bousquet.
Office hours: Thursday 1pm to 3pm and by appointment.
Email: firstname.lastname2@mcgill.ca

Overview

We will first start with a few general lectures on mathematical programming, optimization problems and linear programming. In particular, we will illustrate these concepts on some simple examples. Then we will introduce some general concepts of linear algebra and geometry which will be used all along these lectures. We will then spend a couple of lectures on the Simplex Algorithm. The simplex algorithm is an algorithm solving Linear Programmings which provides excellent results in practice. Another interesting aspect of the simplex algorithm is that it also provides information on possible evolutions of the system if the data is modified as we will see during the lectures dealing with sensitivity analysis.
Then we will consider a much more theoretical aspect of linear programming: duality. We will introduce the concept of duality in linear programming and we will show that the value of a linear programming is not affected by considering its dual problem. We (may) see several applications of this result.
The last main part of the lectures will be integer linear programming. We will see that continuous linear programmings and discrete linear programmings are quite different and cannot be solved in the same way. We will see several methods for Integer Linear Programmings and see that the gaps between Linear Programming and their corresponding Integer Linear Programming can be huge. We will end the lectures with a few applications of LP to graph and game theory.
The remaining lectures will deal with convex optimization, non-linear optimization or applications of mathematical programming to several areas (such as economy, game theory or graph theory).

Pre-requisites

Students should know the basics from Calculus and Linear Algebra.

NOTE: Math 417/487 may be used as a pre-requistite for Discrete Optimization II.

Content

Lecture notes (which will be updated all along the term) can be found there.
Lecture notes of Sven O. Krumke on cutting planes. We will overview part 9.1 and 9.3 of these notes.

Assignments and exercises

Assignment 1 which has to be returned before September, 18th. Correction.
Assignment 2 which is due by October, 2nd. Correction.
Assignment 3 which is due by Tuesday, October, 21st. Correction.
A few simple additional exercises to prepare the midterm.
Midterm, Thursday, October, 30th. Correction.
Assignment 4 due by Tuesday, November, 11th. Correction.
Assignment 5 due by Thursday, November, 27th. Correction with Figures a and b.
Here a collection of exercises to prepare the exam. The list will be updated little by little (last update December, 3rd).

Textbooks

The text for the first 2/3 of the course is: Applied Mathematical Programming by Bradley, Hax, and Magnanti (Addison-Wesley, 1977).
If you want to solve your linear programs, you can go there where a solver using the Simplex algorithm is proposed.
For the remaining of the lectures, lecture notes or additionnal pdf will be provided.