**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.**TD7**: please download maxcut.zip**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.**TD6**: download sentence_cp and nlp_freq; also this run file**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).: (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.*A couple of useful notions you won't find in a book***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*N*1 / 1*N*= 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.

The lecture notes are being composed as I teach.

- Lecture notes
- Stephen Vavasis' proof of the Motzkin-Straus theorem
- Code for TD1
- Code for TD2
- Code for TD3
- Code for TD4
- Code for TD5
- Code for TD6
- Code for TD7
- Code for TD8

- Leo Liberti (Office 1065, LIX @ Turing Building)

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

- AMPL is
*A**M*athematical*P*rogramming*L*anguage. 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.

- The AMPL website
- The first 2 chapters of the AMPL book
- An AMPL tutorial
- Another operations research course I taught at X in 2007/2008
- X open courseware page