Mathematical programming (PM)

dernière modif : le 14/09/2018 à 16:50:43
Titre : Mathematical programming (PM)
Section : TRONC_COMMUN_FOND
Ects : 4
Responsable : Sourour Elloumi (ENSTA ParisTech)
Intervenants :
Sourour Elloumi (ENSTA ParisTech)
Alain Faye (ENSIIE)
Axel Parmentier (ENPC/CERMICS)
Objectif : Mathematical programming (optimizcourses@showation of a function under constraints) is a very general framework for formulating and solving many optimization problems. The purpose of this teaching is to familiarize students with the most useful techniques in discrete and continuous mathematical programming for applications in combinatorial optimization.
Prérequis : algorithme du simplexe, dualité en programmation linéaire, Branch and Bound, notions élémentaires de théorie des graphes, problème du flot maximal
Saisons d'ouvertures : 2017-2018; 2018-2019;
Modalités de contrôle : Examen écrit avec documents : 100% de la note.
Contenu : Overview of mathematical programming. Modeling and selection of a formulation by ILP (compromise relaxation value/size, case of TU matrices, examples). Solving ILP: B&B methods, Gomory cuts, implemented with the dual simplex algorithm. Nonlinear 0-1 optimization (submodular functions, linearization, roof dual, fractional combinatorial optimization). Introduction to robustness in PL. Lagrangian duality applied to combinatorial optimization. Continuous convex quadratic programming. Convex reformulations for quadratic 0-1 optimization and quadratic integer optimization. Presentation of an interior point method for linear programming. Column generation. Polyhedral methods (key concepts for the description of polyhedra, valid inequalities, the problem of separation, cutting algorithms, applications to combinatorial optimization).
Bibliographie :
  • A. Billionnet (2007), Optimisation Discrète, de la modélisation à la résolution par des logiciels de programmation mathématique, Dunod, Paris.
  • M. Minoux (2008), Programmation mathématique, nouvelle édition, Lavoisier, Paris.
  • G.L. Nemhauser and L.A Wolsey (1988), Combinatorial optimization, Wiley-Interscience, New York.
  • L.A. Wolsey (1998), Integer programming. Wiley-Interscience, New York.
  • A. Billionnet (2005), Optimisation quadratique en variables 0-1, Paschos V. Th., Ed., Optimisation combinatoire : Concepts fondamentaux, Ch. 7, Hermès, Paris.