Large-scale Mathematical Optimization

(CSC_52080_EP, ex-INF580) -- Optimisation mathématique à large échelle)

DIX (LIX), École Polytechnique

2nd trimester 2024/2025 (jan-mar)

News (chronological order)

See the Moodle course page
The course will take place in Petite Classe (PC) 4 (moved to PC18 on Fri, 7 Feb only). Find it in this map
Download a small portfolio selection dataset in AMPL format
Slides for TD1
Transportation problem files
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 for TD1
Slides for TD3
Solutions for TD2
Slides for TD4 and some files for the exercises
Solutions for TD3
Solutions for TD4
TD5, some code, and files for the exercises
TD6 and files for the exercises
solutions for TD5
solutions for TD6
Lecture 7 will be a guest lecture by Igor Klep on Polynomial optimization and the Lasserre's moment-SOS hierarchy
Exercises for TD7 to be carried out in Julia
TD8 and files for the exercises (the filenames refer to "TD7" because the lecture 7 was taught by a guest teacher this year: ordinarily, I teach this material in lecture 7)

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

250314 fri	14-1815 CSC_52080_EP (ex-INF580) @PC04
250307 fri	14-1815 CSC_52080_EP (ex-INF580) @PC04
250221 fri	14-1815 CSC_52080_EP (ex-INF580) @PC04
250214 fri	14-1815 CSC_52080_EP (ex-INF580) @PC04
250207 fri	14-1815 CSC_52080_EP (ex-INF580) @PC18
250131 fri	14-1815 CSC_52080_EP (ex-INF580) @PC04
250124 fri	14-1815 CSC_52080_EP (ex-INF580) @PC04
250117 fri	14-1815 CSC_52080_EP (ex-INF580) @PC04
250110 fri	14-1815 CSC_52080_EP (ex-INF580) @PC04

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.
Unlimited version of AMPL for this course, with a license limited to April 2025, can be obtained here. Some of the installers ask you for the license UUID: it's 42b877f3-c7cc-4da9-b46f-b9371049f68c
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: but don't ask me help about making Co-lab work with AMPL, since I don't use it (or any other programming language) this way, or even with any graphical user interface. I started programming with command line tools, which I still think are a much faster coding methodology.

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