IFT6551
PROGRAMMATION EN NOMBRES ENTIERS
HIVER 2012
RESPONSABLE: Bernard GENDRON
plan
de cours évaluation
horaire
références
devoirs
Ce cours vise, d'une part, à introduire l'étudiant à de
nombreux problèmes d'optimisation pouvant être formulés
à l'aide de variables
entières et, d'autre part, à le familiariser avec les
méthodes de la programmation en nombres entiers. Pour plus de détails,
consultez le texte suivant, qui propose une
synthèse des sujets traités.
Une familiarité avec les notions de base en programmation
linéaire et non-linéaire est préférable;
toutefois, les notions
nécessaires à la compréhension du cours seront
revisées.
Messages d'intérêt
public :
-
Mouvement étudiant :
Les séances de cours manquées sont remplacées par des lectures d'articles.
Le devoir 2 devra être remis dans les deux jours suivant la fin du mouvement étudiant.
Un devoir 3 semblable aux deux premiers devoirs et comptant aussi pour 20% sera à faire dans un délai de deux semaines suivant la fin du mouvement étudiant.
L'examen final comptant pour 40% sera à faire dans un délai de deux semaines suivant la remise du devoir 3.
-
Lectures obligatoires:
Balas, Ceria, Conuejols, Natraj: Gomory Cuts Revisited
Balas, Ceria, Cornuejols: A Lift-and-Project Cutting-Plane Algorithm for Mixed 0-1 Programs
Atamturk, Savelsbergh: Integer Programming Software Systems
Martello, Pisinger, Toth: New Trends in Exact Algorithms for the 0-1 Knapsack Problem
Atamturk, Nemhauser, Savelsbergh: A Combined Lagrangian, Linear Programming and Implication Heuristic for Large-Scale Set Partitioning Problems
-
Lectures complémentaires:
Cornuejols: Revival of the Gomory Cuts in the 1990's
Lodi: Integer Programming Computation
Erlenkotter: A Dual-Based Procedure for Uncapacitated Facility Location
Dantzig, Fulkerson, Johnson: Solution of a Large-Scale Traveling Salesman Problem
Applegate, Bixby, Chvatal, Cook: Concorde
-
Les fichiers en format PDF (extension ".pdf") peuvent être
visualisés à l'aide du logiciel Acrobat Reader.
-
Le professeur assurera les disponibilités suivantes :
Mardi 16h30-17h, salle 3531, pavillon André-Aisenstadt (CIRRELT)
Mercredi 16h30-17h, salle 3531, pavillon André-Aisenstadt (CIRRELT)
Évaluation :
Devoir 1 - résolution de problèmes: 20 %
Devoir 2 - résolution de problèmes: 20 %
Devoir 3 - résolution de problèmes: 20 %
Examen final (à la maison): 40 %
Horaire :
Mardi 14h30 - 16h30, salle 1177, pavillon André-Aisenstadt
Jeudi 14h30 - 16h30, salle 1175, pavillon André-Aisenstadt
Devoirs :