Large-scale Mathematical Optimization

(INF580 -- Optimisation mathématique à large échelle)

DIX (LIX), École Polytechnique

2nd trimester 2023/2024 (jan-mar)

News (chronological order)

See the Moodle course page
The course will take place in Petite Classe (PC) 4. Find it in this map
Download a small portfolio selection dataset in AMPL format
Slides for TD1
Fill in the code structure for the line monitor example
Slides for TD2 and corresponding AMPL .dat files. There is also a difficult version of the TD2, which concerns computability and universality. It is not recommended, but if you finish everything in the other (easier) version, you're welcome to test your strength on the hard one.
Solutions to TD1.
I updated the lecture notes (so download them again) to eliminate a modelling error in the blending problem of TD2 (thanks to Ms. Florence Pautet X21 for pointing this -- and the correct formulation -- out!).
Solutions to TD2.
Slides for TD3.
Solutions to TD3 (aside from the Motzkin-Straus formulation).
Slides for TD4 and the tiny_gph.dat AMPL .dat file.
The AMPL .mod file of the Motzkin-Straus max clique formulation (part of the solution of TD3).
Solutions to TD4.
Slides for TD5 and some code.
Solutions to TD5.
Slides and some code to be filled in for TD6.
Solutions to TD6.
Slides and some code to be filled in for TD7.
Solutions to TD7.
Slides and some code to be filled in for TD8.
Solutions to TD8.
Please evaluate this course before the exam.

Current status of exam slots:

240318 mon	1000-1100 INF580 exam Dimitri
240318 mon	1100-1200 INF580 exam Artur+Guilherme
240319 tue	1030-1130 INF580 exam Ines+Khadija
240320 wed	1100-1200 INF580 exam Florence+Emile
240320 wed	1400-1500 INF580 exam Valentine
240320 wed	1500-1600 INF580 exam Joao+Joao
240320 wed	1600-1700 INF580 exam [free]
240322 fri	1030-1130 INF580 exam Emanuele+Florido
240322 fri	1130-1230 INF580 exam [free]

Teaching Material

Lecture slides. They may evolve during the course.
A new set of lecture notes. They may evolve during the course.
The lecture notes I used until until 2017
The AMPL book

Teacher

Leo Liberti (Office 2015, LIX @ Turing Building)

Timetable

240313 wed	14-1815 INF580
240308 fri	14-1815 INF580
240301 fri	14-1815 INF580
240216 fri	14-1815 INF580
240209 fri	14-1815 INF580
240202 fri	14-1815 INF580
240126 fri	14-1815 INF580
240119 fri	14-1815 INF580
240112 fri	14-1815 INF580

Every "teaching slot" will be composed by 2h lectures (fri 14-16) in and 2h of computer practice (fri 1615-1815)

Exam: either project (in pairs) on a topic agreed with me, or oral

Software

AMPL is A Mathematical Programming Language. Optimization problems coded in AMPL look very close to their corresponding mathematical formulation.
Each problem instance is coded in AMPL using three files: a model file (extension .mod), a data file (extension .dat) and a run file (extension .run).
The model file contains the mathematical formulation of the problem.
The data file contains the numerical values of the problem parameters. Different data files for the same model file correspond to different instances of the same optimization problem.
The run file specifies the solution algorithm. This may be implemented in an external numerical solver, such as CPLEX, or coded by the user in the AMPL language itself. We will often use a combination of the two.
Although AMPL is a commercial software, various limited editions of AMPL can be downloaded for free here.
An unlimited version of AMPL for this course, with a dynamic license limited to May 15th 2024, can be obtained here. "Dynamic license" means you need to be connected to the internet to use it. Network-free teaching bundles can also be obtained for Linux, MacOS, Windows, but without the hassle-free installer.
AMPL is natively a command-line tool, which makes it easy to use it as part of a "pipe" command (this is a Unix command-line trick that pipes the output of a command into the input of another: it achieves a sequential algorithm without any loops). Although there is also a bare graphical user interface to use AMPL, I do not advise you to use it. It is more productive to use AMPL with a command line. Its own program files (.mod, .dat, .run) can be written using a normal text editor (nowadays, however, AMPL people advise students to use Python+AMPL on Google Co-lab: use the license UUID bf5b5ed2-ea35-4373-8776-1ab021939a37 when prompted).

More resources about mathematical programming and OR

The slides from an old course I gave at X until 2010 (INF572)

The exercise book from INF572