Mathematical programming

DIX (LIX), École Polytechnique

2nd trimester 2015/2016 (dec-feb)

News

• ORAL EXAM. The scolarité assigned us a slot for the exam: Friday, 19th February 2016, between 14 and 17 in Salle 64, in front of Amphithéâtre Cauchy.
• Summary of TD8. MILP reformulation of the max-norm DGP. Python implementation of the Isomap heuristic (no-one did this).
• TD8. Download this DGP instance generator, with a corresponding solution drawing code which transforms the solution into a LaTeX TiKZ environment, which you can compile into a PDF. Both are written in AMPL; you should adapt your variable names so they fit these codes, or the converse.
• Summary of lecture 8. Distance geometry: fundamental problem, applications, formulations for 1- and 2-norm, Euclidean Distance Matrices and the completion problem, SDP formulations of the EDMCP, diagonally dominant inner approximations, duality and iterative method, Isomap heuristic, random projections.
• Summary of TD7. We went through my Python code for solving Max Cut using MIQP, MILP, SDP and randomized rounding. Only four of you managed to load the required Python libraries, which is a little disappointing. I then asked you to implement the "trivial" randomized approximation algorithm, which flips a coin per vertex, and assigns the vertex to the cut only if the coin turns up head.
• Summary of lecture 7. I had hoped to pass through my office and print my lecture notes before I showed up to class, but TWO "colis suspects" and a technical problem on the RER B made me so late as to have to give that up. Even teaching just from memory, we went trhrough the definition and the applications of the Max Cut problem, then some mathematical programming formulations, focusing on the SDP one. I then told you about the randomized rounding, and proved to you that, on average, it delivers an approximation ratio of around 0.878 times the optimal objective function value of the SDP formulation.
• Lecture 7: PREPARE FOR THE GOEMANS-WILLIAMSON ALGORITHM IN ALL ITS GLORY, AND ALL OF ITS GORY DETAILS! (see the most recent version of the lecture notes)
• Summary of TD6. Some "research experiments" in natural language using Constraint Programming in AMPL. Although the success of our experiments can be reasonably questioned, my hope is that I showed you a "hands-on" approach to doing research in mathematical programming and algorithmics in general.
• Summary of lecture 6. Notions of constraint programming. Please see this paper.
• Summary of TD5. Reformulation of a complicated application model to do with software architecture (choice between developing new software modules or using old ones).
• Summary of lecture 5. Elementary reformulations (part II). Application to the hyperplane clustering problem (HCP).
• A couple of useful notions you won't find in a book: (i) learning to derive the LP dual of a structured problem by lying sideways looking at the blackboard bearing the primal; (ii) there is a relationship of solution difficulty between logical variables and constraints with "and" and "or" connectives: [variable and variable] involves a product and is hence difficult, [constraint or constraint] inolves union/disjunction of sets and is therefore difficult, whereas [variable or variable] involves a sum and is easy, like [constraint and constraint] which only requires juxtaposition.
• Summary of TD4. Solving a bi-objective LP using scalarization or bisection on one of the objectives. Solving a bilevel LP using dual replacement of the lower-level LP.
• Summary of lecture 4. Systematics of mathematical programming (part III): multiobjective programming, bilevel programming, semi-infinite programming. Elementary reformulations (part I).
• Summary of TD3. Modelling of PECS with graphical Python output. Exercise: Modelling of the KNP and of the feasibility version of the KNP.
• Summary of lecture 3. Systematics of mathematical programming (part II): cNLP, NLP, cMINLP, MINLP, cQP, QP, QCQP, SDP. NLP examples: packing equal circles in a square (PECS). MINLP example: the Kissing Number Problem (KNP). Proof of the Motzkin-Straus theorem.
• Summary of TD2. The max network flow problem in AMPL, with random instance generation (and mention of graphical output for GraphViz). Problem: model the Power Generation Problem and solve it using AMPL and CPLEX.
• Exam format. 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, but the reduced oral exam will have to be given individually.
• Summary of lecture 2. Systematics of mathematical programming (part I): LP, MILP, ILP, BLP. LP examples: production planning, diet problem, solving over- and under-determined linear systems, Delsarte's LP bound for codes and the Kissing Number Problem, network flow (max, min-cost, multicommodity, shortest path tree formulation, connectivity). MILP examples: optimization of a power generation park, traveling salesman problem (compact formulation). ILP example: scheduling with precedence constraints. BLP examples: vertex cover, set cover, set packing, set partitioning.
• Summary of TD1. AMPL, Python+Pyomo installation and basic syntax and usage. The transportation problem in AMPL and Python. Problem: find a 5-digit integer N such that N1 / 1N = 3 (exactly).
• Summary of lecture 1. Imperative vs. declarative programming, definition of the mathematical programming language, uses in industry, the transportation problem, structured and flat mathematical programs, AMPL and Python.

Teaching Material

The lecture notes are being composed as I teach.

Timetable

```151202 wed	1045-1245 INF585 Amphi Grégory
151202 fri	1400-1600 INF585 PC06

151209 wed	1045-1245 INF585 Amphi Grégory
151211 fri	1400-1600 INF585 PC06

151216 wed	1045-1245 INF585 Amphi Grégory
151218 fri	1400-1600 INF585 PC06

160106 wed	1045-1245 INF585 Amphi Grégory
160108 fri	1400-1600 INF585 PC06

160113 wed	1045-1245 INF585 Amphi Grégory
160115 fri	1400-1600 INF585 PC06

160120 wed	1045-1245 INF585 Amphi Grégory
160122 fri	1400-1600 INF585 PC06

160127 wed	1045-1245 INF585 Amphi Grégory
160129 fri	1400-1600 INF585 PC06

160203 wed	1045-1245 INF585 Amphi Grégory
160205 fri	1400-1600 INF585 PC06

160210 wed	1045-1245 INF585 Amphi Grégory
160212 fri	1400-1600 INF585 PC06
```

Every "teaching slot" will be composed by 2h lectures (wed 1045-1245) in Amphi Grégory and 2h of computer practice (fri 14-16) in PC06: 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, but the reduced oral exam will have to be given individually.

```160217 wed      Controles
160219 wed      Controles
160222-26       Soutenances projets
```

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 Linux64, MacOsX64, 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