Cours

MATH0462-1, Optimisation discrète

Les répétitions sont données par Sébastien Mathieu depuis 2012.

Projet TSP (2011)

Deadline: le code et un rapport (max. 7 pages) sont à rendre pour le 6 décembre à 23:59
Enoncé du projet: tsp-enonce.pdf
Code C++ des classes: classes-v5.tgz
Documentation des classes et interfaces: tsp-doc.pdf
Machine mise à votre disposition: thales02.montefiore.ulg.ac.be
Documentation et exemples CPLEX: cplex (les exemples sont aussi installés dans: /usr/local/src/cplex-12.2/cplex/examples/src/)
Instances: TSPLIB

Note: le fichier LPSolver.o fonctionne uniquement sur thales02. Pour linker avec CPLEX, utiliser "-lcplex -lpthread" dans la ligne de commande de g++.

Séances d'exercices (2011)

Séance	Date	Heure	Local	Notes
Répétition 1	30 septembre	15:30	I.21	Modélisations (énoncés, exemples AMPL: model.mod, ex2.dat )
Répétition 2	7 octobre	15:30	I.21	Modélisations efficaces (énoncés, données: fl10.dat, fl40.dat, fl100.dat, fl300.dat )
Répétition 3	14 octobre	15:30	I.21	Branch and Bound (énoncés)
Répétition 4	21 octobre	15:30	I.21	Présentation du projet
Répétition 5	28 octobre	15:30	I.21	Cuts (énoncés)
Répétition 6	4 novembre	15:30	I.21	Cuts (mêmes énoncés)
Répétition 7	18 novembre	15:30	I.21	Flows (énoncés)
Répétition 8	25 novembre	15:30	I.21	Matching, Assignment (énoncés)
Répétition 9	2 décembre	15:30	I.21	Dynamic Programming, Relaxation Lagrangienne
Projet	9 décembre		I.21

Exercices AMPL

Machine: thales02.montefiore.ulg.ac.be
Site de GLPK: www.gnu.org/s/glpk
Manuel de référence GNU MathProg (pdf), un clone d'AMPL.
Exemples utiles de modèles AMPL (pdf)

Commandes utiles

Résoudre un problème avec GLPK:

glpsol -m problem.mod -d problem.data

Traduire un fichier AMPL en fichier LP:

glpsol --check -m problem.mod -d problem.data --wlp problem.lp

Résoudre un problème au format LP, avec cplex:

cplex

Dans cplex, exécuter:

r problem.lp
opt

Afficher la solution, dans cplex:

disp sol var *

Pour quitter cplex:

Données complémentaires

Facility location

3x5: fl00.data
50x2000: fl01.data
100x4000: fl02.data

Steiner tree

10-4: st00.data
16-6: st01.data
18-8: st02.data
Remarque:

param N; # vertices: 1..N
param M; # mandatory vertices: 1..M, M <= N
param d{i in 1..N, j in 1..N}; # edge cost (symmetric matrix)

Optimisation Discrète