Large-scale Mathematical Optimization

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

DIX (LIX), École Polytechnique

2nd trimester 2022/2023 (jan-mar)

News (chronological order)

See the Moodle course page
TD1: slides are here. Finish coding up the AMPL line monitoring example.
TD1: line monitoring code
Lecture 2: I wrote some new notes about formal systems and Gödel's first incompleteness theorem.
TD2: see slides here, and some of the .dat files here.
TD2: see the assignment code with the instance generator here
Find some more challenging exercises for TD2 (about computability concepts) here.
TD2: find solutions to (easy) exercises here
TD3: here are the TD3 slides
TD3: find solutions to exercises here
TD4: slides here and some useful code
TD4: solutions to exercises
TD5: slides and code
TD5: solutions to exercises
TD6: slides and code
TD6: solutions to exercises
TD7: slides and code
TD7: solutions to exercises
Please fill in the course evaluation form
Exam schedule with slots filled so far

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
Downloadable AMPL packages (Linux/MacOSX/Windows with a 4-month temporary license)

Teacher

Leo Liberti (Office 2015, LIX @ Turing Building)

Timetable

230106 fri	14-1815 INF580 cours+TD n.1 amphi Gregory  
230113 fri	14-1815 INF580 cours+TD n.2 amphi Gregory
230120 fri	14-1815 INF580 cours+TD n.3 amphi Gregory
230127 fri	14-1815 INF580 cours+TD n.4 amphi Gregory
230203 fri	14-1815 INF580 cours+TD n.5 amphi Gregory
230210 fri	14-1815 INF580 cours+TD n.6 amphi Gregory
230217 fri	14-1815 INF580 cours+TD n.7 amphi Gregory
230224 fri	14-1815 INF580 cours+TD n.8 amphi Gregory
230309 thu	14-1815 INF580 cours+TD n.9 amphi Gregory
230315 wed	14-17 INF580 exam

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.
A commercial version for this course, with license limited to April 30th, 2023, can be downloaded here. You will be asked to register on the AMPL website or to log in with Google, GitHub, or Twitter account. You will then see a webpage with buttons to download AMPL in any of the Linux64, macOS, or Win64 architectures. Linux64 and macOS architectures download to compressed .tgz files, whereas the Win64 downloads to a compressed .zip file.
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.

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