Mathematical programming

(INF580 -- Programmation Mathématique)

DIX (LIX), École Polytechnique

2nd trimester 2016/2017 (jan-mar)

News

TD 9: assignment in the code (complete dgpisomap.py and dgpsolve.py)
Lecture 9: The second part of two lectures on Distance Geometry (DG): Formulation-based algorithms for solving the DGP on protein graphs, and the IsoMap algorithm.
Questionnaire: please take this Google Form questionnaire on the course
CPLEX on python: here and also on Anaconda python (conda install -c ibmdecisionoptimization docplex=2.0.15)
Evaluation. Deliverables are as follows. (i) An oral presentation of around 20 minutes. (ii) The slides of this presentation (if you use them, or else I'll take pictures of what you write on the blackboard). (iii) A document (PDF), containing: your project title, your name, your email address, a short abstract (10 lines), and three sections: (a) one where you formally describe the problem you are solving, informally give some applications of it (or say why it's important), and very briefly describe the sources you used (papers, websites, etc; these sources must appear in the bibliography; (b) another where you formally describe the methodology you used (mathematical programming formulations, algorithms); (c) a third where you describe your results. (iv) The code you implemented and a short README file that tells me how to run it. Send me all this in a .ZIP file named by your surname(s).
TD 8: assignment in the code
Lecture 8: The first part of two lectures on Distance Geometry (DG): Heron's theorem, Multidimensional Scaling, Principal Component Analysis, the DG Problem (DGP), its NP-hardness
TD 7: computational experiments with the Kissing Number Problem (NLP, SDP, LP formulations for lower and upper bounds), see the code here
Lecture 7: The Kissing Number Problem: packing equal spheres on a spherical surface (with some code which will also be used in TD7)
TD 6: this was really a lecture in disguise, about the application of Mathematical Programming techniques to clustering in Natural Language Processing: see the code here
Lecture 6: Stochastic and robust programming (by Fabio D'Andreagiovanni)
TD 5: Establishing trade-offs of parameter values to have "sparsity magic" work correctly with ℓ₁ norm minimization linear programs (the basic code, to be extended, is in this zipped archive)
Lecture 5: Comment to the solution of the Air Courier problem, short introduction to ℓ₁ norm minimization LPs and sparsest solutions of linear systems, with some test code in AMPL (slides).
TD 4: Row generation for the Hamiltonian Cycle problem, and Air Courier problem, last slide in Lecture 4. Make sure you read the README file in the zipped archive!
Lecture 4: NP-hardness of some QP formulations (slides)
TD 3: Missing from calendar for skiing and Portuguese reasons
Lecture 3: NP-hardness of some QP formulations (slides)
TD 2: Formulations of a few basic combinatorial problems in MP using AMPL and Python (code)
Lecture 2: Computational complexity, some combinatorial problems and their formulations (slides)
TD 1: Introduction to modelling software, the AMPL language (slides and code)
Lecture 1: Generalities on MP, decidability of MP (slides)
I obtained some temporarily licensed AMPL packages for Linux32, Linux64, MacOsX64, MSWin32, MSWin64 OSes. They expire in 4 months.

Teaching Material

The whole set of slides for the course
Lecture notes from last year
Downloadable chapters from the AMPL book

Teacher

Leo Liberti (Office 2015, LIX @ Turing Building)

Timetable

  January: 4-6, 11-13, 18, 25-27
  February: 1-3, 8-10, 22-24
  March: 1-3, 8-10, 15

Every "teaching slot" will be composed by 2h lectures (wed 1045-1245) in and 2h of computer practice (fri 14-16 and 1615-1815) in PC37: bring your laptops!

The exam will consist either of an oral examination where I will ask you questions about the course material, or of the presentation of a project about a topic in mathematical programming, with possibly also a reduced part of oral examination. Projects can be conducted in pairs (at most), but the reduced oral exam will have to be given individually.

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.
The student edition of AMPL can be downloaded here for either UNIX or Windows platforms. Download and install, from the same webpage, the solvers CPLEX , MINOS, and SNOPT, too.
I obtained some temporarily licensed AMPL packages for Linux32, Linux64, MacOsX64, MSWin32, MSWin64 OSes.

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

Notes about linear programming I wrote years ago when I was a postdoc

Notes about nonlinear programming I wrote years ago when I was a postdoc