Optimisation discrète

Dr. Kahina Ghazli

[email protected]

Département de Recherche Opérationnelle

Université A. Mira de Béjaia

Année académique 2024 – 2025

Dr. Kahina Ghazli Optimisation discrète 1 / 33

Organisation du cours

Support : Slides (transparents)

Parties
Introduction à l’Optimisation Discrète : Modélisation
(Définitions, Exemples de problèmes classiques d’OC, etc.)
Programmation linéaire en nombres entiers (Formulation,
Résolution : Algorithme branch and bound, Algorithme de
coupes)
Programmation dynamique
Evaluation
Contrôle continu (projet ? ? ?)
Examen
Tout est sur e-learning

Dr. Kahina Ghazli Optimisation discrète 2 / 33

 Modélisation

Dr. Kahina Ghazli Optimisation discrète 3 / 33

Modélisation et aide à la décision

Aider à choisir la meilleure décision

Décision ←
→ vecteur de variables x ∈ Rn
Meilleure ←
→ fonction objectif f : Rn → R ⇒ Optimisation
Contraintes ←
→ domaine admissible X ⊂ Rn

min f (x) tel que x ∈ X

x

Les éléments de X sont dits solutions réalisables

Solution optimale : est une solution x⋆ ∈ X vérifiant

f (x⋆ ) ≤ f (x) ∀x ∈ X

.
Maximiser f revient à minimiser −f .
Dr. Kahina Ghazli Optimisation discrète 4 / 33
Exemple 1 : Distribution optimale de ressources entre
activités concurrentes

Trois ressources A (bois), B (clous) et C (tissu) sont utilisées pour

obtenir deux produits T (table) et L (lits). On a besoin de : deux
unités de bois pour construire une table et trois pour un lit, deux
unités de clou pour une table et une pour un lit, et une unité de
tissu pour une table et trois pour un lit. On dispose de 13 unités de
A, 11 de B et 9 de C. Les produits T et L rapportent,
respectivement, 300 et 400 euros par unités produites.
Combien d’unités de L et T faut-il produire pour maximiser le
profit ?

Dr. Kahina Ghazli Optimisation discrète 5 / 33

Exemple 1 : Formulation

1 Choix des variables : x1 unités de T, x2 unité de L.

2 Contraintes :
2x1 + 3x2 ≤ 12, (ressource A)
2x1 + x2 ≤ 11, (ressource B)
x1 + 3x2 ≤ 9, (ressource C)

x1 , x2 ≥ 0.
3 Fonction objectif :

max 300x1 + 400x2

x1 ,x2

Dr. Kahina Ghazli Optimisation discrète 6 / 33

Exemple 1 : Formulation

En résumé, le problème de production se modélise sous la forme

d’un programme linéaire :

 max 300x1 + 400x2

 x1 ,x2

 tel que 2x1 + 3x2 ≤ 12


 2x1 + x2 ≤ 11
x1 + 3x2 ≤ 9




x1 , x2 ≥ 0


Dr. Kahina Ghazli Optimisation discrète 7 / 33

Exemple 2 : Maximisation de la surface d’un rectangle

Supposons que l’on veut plier un fil de fer de longueur L en rectangle de

manière à maximiser la surface du rectangle.

Dr. Kahina Ghazli Optimisation discrète 8 / 33

Exemple 2 : Maximisation de la surface d’un rectangle

Supposons que l’on veut plier un fil de fer de longueur L en rectangle de

manière à maximiser la surface du rectangle.

Formulation
max S = lw
l,w
L
tel que l+w = 2

Dr. Kahina Ghazli Optimisation discrète 8 / 33

Exemple 2 : Maximisation de la surface d’un rectangle
Supposons que l’on veut plier un fil de fer de longueur L en rectangle de
manière à maximiser la surface du rectangle.

Formulation
max S = lw
l,w
L
tel que l+w = 2
Solution
L Lw
− w2


S= −w w =
2 2
dS L
= − 2w = 0
dw 2
Solution optimale : w = l = L4

La solution analytique n’existe pas souvent ! ! !

→ Importance des algorithmes !
Dr. Kahina Ghazli Optimisation discrète 8 / 33
Exemple 3 : Sélection de projets

5 projets doivent être évalués sur 3 ans. Étant donné le coût de

chaque projet pour chaque année et le profit obtenu par l’exécution
d’un projet, décider quels projets exécuter sans dépasser le budget
disponible pour chaque année.

Dr. Kahina Ghazli Optimisation discrète 9 / 33

Exemple 3 : Formulation

Variables
Pour tout j, 1≤ j ≤ 5,

1 si le projet j est sélectionné,
xj =
0 sinon.
Formulation

Dr. Kahina Ghazli Optimisation discrète 10 / 33

Optimisation Continue Vs. Discrète

min f (x) tel que x∈X

x

Si l’ensemble X est continu, on parle de problème d’optimisation

continue.
Si l’ensemble X est discret, on parle de problème d’optimisation
discrète,
il est dit problème en nombres entiers ou problème entier si
toutes les variables sont entières. Il est dit binaire ou à
variables bivalentes si les variables ne peuvent prendre que les
valeurs 0 ou 1.
Si seulement une partie des variables doivent être entières
(discrètes) et d’autres continues, on parle de problème mixte
(Mixed Integer Problem ou MIP)

Lorsque X est discret et fini (ou dénombrable), on parle d’un

problème d’optimisation combinatoire ⇒ minimisation d’une
fonction sur un ensemble fini (mais potentiellement très grand)
Dr. Kahina Ghazli Optimisation discrète 11 / 33
Modélisation mathématique des problèmes combinatoires
Une grande partie des problèmes combinatoires peuvent se formaliser comme
un problème de programmation linéaire en nombres entiers (PLNE) ou en
variables binaires (PLNE 0–1) :
n

n
P 


 min cj xj 
 min
P
c j xj
j=1

 
j=1
 
n
 
P n
aij xj ≤ bi (i = 1, . . . , m) P
aij xj ≤ bi (i = 1, . . . , m)
i=1
 

  i=1
lj ≤ xj ≤ uj (j = 1, . . . , n)
 
xj ∈ {0, 1} (j = 1, . . . , n)

 

xj entier (j = 1, . . . , n)


(PLNE) (PLNE 0–1)

où n, m ∈ N∗ , les cj (1 ≤ j ≤ n), aij (1 ≤ j ≤ n, 1 ≤ i ≤ m) et bi

(1 ≤ i ≤ m) sont des reels.

Les PLNE et PLNE 0–1 sont des problèmes d’optimisation NP-difficiles dans le
cas général. On les résout en général par des méthodes exactes de recherche
arborescente (les méthodes de séparation et d’évaluation) ou bien par des
méthodes approchées (diverses heuristiques).

Dr. Kahina Ghazli Optimisation discrète 12 / 33

Solveurs de PLNE
L’intérêt des programmes linéaires (en nombres entiers) est qu’il existe de
nombreux solveurs disponible sur le marché (solveurs commerciaux) ou
bien en libre accès. Ces solveurs implémentent les algorithmes standards,
plus ou moins performants, pour résoudre les PL ou les PLNE. Quelques
solveurs de PLNE :
IBM CPLEX
GUROBI
SCIP
LINGO
LPSOLVE
GLPK
...
A côté des solveurs, on trouve des langages de modélisation, permettant
d’exprimer de manière algébrique des problèmes d’optimisation (linéaires
ou non) comme AIMMS, AMPL, LINDO, MPL ou OPL, . . .
Dr. Kahina Ghazli Optimisation discrète 13 / 33
Exemples de problèmes d’optimisation combinatoire

Problème d’affectation
Problème du voyageur de commerce
Problème de transport et logistique
Problèmes dans les réseaux
Problème du sac à dos
Problème de chargement (avions, bateaux, . . .)
Problème d’investissement
Problème de couverture
Installation des relais GSM et réseaux sans fils
Problème de partitionnement
Organisation des votes, gestion des vols aériens
Problème d’emballage
Organisation des opérations chirurgicales
..
.

Dr. Kahina Ghazli Optimisation discrète 14 / 33

Problème d’affectation

Le "problème d’affectation" consiste à affecter n tâches à n agents à un

coût total minimum. Chaque agent peut réaliser une unique tâche pour
un coût donné et chaque tâche doit être réalisée par un unique agent. Le
problème d’affectation est aussi nommé : AP ou "Assignment Problem".

Dr. Kahina Ghazli Optimisation discrète 15 / 33

Problème d’affectation

À tout couple tâche/agent (i, j), on associe une variable

d’affectation, xij , binaire :

1 si la tâche i est affectée à l’agent j,
xij =
0 sinon.

Le coût total de réalisation des tâches s’exprime alors par la

Pn P n
somme : cij xij .
i=1 j=1
n
P
Le nombre d’agents réalisant la tâche i est donné par : xij = 1
j=1
pour tout i = 1, . . . n et le nombre de tâches réalisées par l’agent j
Pn
est donné par : xij = 1, pour tout j = 1, . . . n.
i=1

Dr. Kahina Ghazli Optimisation discrète 15 / 33

Problème d’affectation

On peut donc modéliser le problème d’affectation sous la forme :

Il s’agit de définir une bijection de {1, · · · , n} sur {1, · · · , n} ou encore une

permutation de n objets.

Dr. Kahina Ghazli Optimisation discrète 16 / 33

Problème d’affectation
On peut donc modéliser le problème d’affectation sous la forme :

Ce problème est un "faux" problème en variables entières : les contraintes

xij ∈ {0, 1} peuvent être remplacées par xij ≥ 0, la matrice des contraintes est
totalement unimodulaire. Pour n = 3, la matrice A des contraintes :
1 1 1 0 0 0 0 0 0
 
 0 0 0 1 1 1 0 0 0 
0 0 0 0 0 0 1 1 1
 
A=
 
1 0 0 1 0 0 1 0 0

 
 0 1 0 0 1 0 0 1 0 
0 0 1 0 0 1 0 0 1

Une matrice A est dite totalement unimodulaire si toute matrice carrée extraite
de A a pour déterminant 0, 1 ou -1.
Dr. Kahina Ghazli Optimisation discrète 16 / 33
Problème d’affectation

Soit le problème d’affectation suivant :

 
1 4 9
C= 6 2 5 
5 8 10

(C est la matrice des coûts d’affectation)

Dr. Kahina Ghazli Optimisation discrète 17 / 33

Problème d’affectation

Soit le problème d’affectation suivant :

 
1 4 9
C= 6 2 5 
5 8 10

(C est la matrice des coûts d’affectation)

Algorithme de "force brute" ou de "recherche exhaustive" :
énumérer explicitement toutes les solutions x ∈ X et retenir la meilleure.
Ceci est possible, étant donné que X est de petite taille (cardinalité) :
|X| = n! = 3! = 6 alternatives.
La solution optimale du problème est donnée par

x∗11 = x∗22 = x∗33 = 1 avec z ∗ = 13

Dr. Kahina Ghazli Optimisation discrète 17 / 33

Problème d’affectation
Soit le problème d’affectation suivant :
 
1 4 9
C= 6 2 5 
5 8 10
(C est la matrice des coûts d’affectation)
Algorithme de "force brute" ou de "recherche exhaustive" :
énumérer explicitement toutes les solutions x ∈ X et retenir la meilleure.
Ceci est possible, étant donné que X est de petite taille (cardinalité) :
|X| = n! = 3! = 6 alternatives.
La solution optimale du problème est donnée par
x∗11 = x∗22 = x∗33 = 1 avec z ∗ = 13
Problème : la cardinalité de X est en général gigantesque ! Exemple :
pour n=20 ; |X| = 20! ≈ 2.43 × 1018 alternatives
> Algorithme très coûteux en terme de temps de calcul et d’espace
mémoire.
> Existence d’un algorithme de résolution efficace ("Algorithme
hongrois", Kuhn 1955)
Dr. Kahina Ghazli Optimisation discrète 17 / 33
Problème du voyageur de commerce

Ce problème consiste à déterminer un tour (circuit d’un seul tenant)

passant une et une seule fois par n villes qui soit de coût minimum. Ce
problème est aussi nommé : TSP ou "Travelling Salesman Problem".

Dr. Kahina Ghazli Optimisation discrète 18 / 33

Problème du voyageur de commerce

On associe à chaque couple (i, j) de villes à visiter (i = 1, . . . , n,

j = 1, . . . , n ), une distance cij égale à dij s’il existe un moyen
d’aller directement de i à j, fixée à ∞ sinon :

 dij si la ville j est visitée immédiatement
cij = après la ville i dans la tournée,
∞ sinon.


On associe à chaque couple (i, j) de villes à visiter (i = 1, . . . , n,

j = 1, . . . , n ) une variable d’affectation, xij , binaire :

 1 si la ville j est visitée immédiatement
xij = après la ville i dans la tournée,
0 sinon.


Dr. Kahina Ghazli Optimisation discrète 18 / 33

Problème du voyageur de commerce
Le TSP est alors modélisé par :

Les deux premières contraintes traduisent le fait que chaque ville doit être
visitée exactement une fois ; la troisième contrainte interdit les solutions
composées de sous-tours disjoints, elle est généralement appelée
contrainte d’élimination des sous-tours.

Dr. Kahina Ghazli Optimisation discrète 19 / 33

Problème du voyageur de commerce
Le TSP est alors modélisé par :

Les deux premières contraintes traduisent le fait que chaque ville doit être
visitée exactement une fois ; la troisième contrainte interdit les solutions
composées de sous-tours disjoints, elle est généralement appelée
contrainte d’élimination des sous-tours.
Dr. Kahina Ghazli Optimisation discrète 20 / 33
Problème du voyageur de commerce
Le TSP est alors modélisé par :

Les deux premières contraintes traduisent le fait que chaque ville doit être
visitée exactement une fois ; la troisième contrainte interdit les solutions
composées de sous-tours disjoints, elle est généralement appelée
contrainte d’élimination des sous-tours.
Dr. Kahina Ghazli Optimisation discrète 21 / 33
Problème du voyageur de commerce
Le TSP est alors modélisé par :

Ce modèle est une extension du problème d’affectation. La valeur

optimale du problème d’affectation peut servir de fonction d’évaluation
dans une procédure "Branch and Bound" pour le problème du voyageur
de commerce.
Dr. Kahina Ghazli Optimisation discrète 21 / 33
Problème du voyageur de commerce

Dr. Kahina Ghazli Optimisation discrète 22 / 33

Problème du sac à dos

Le "problème de chargement" , "de selection" ou "du sac à dos" consiste

à choisir des objets qui feront partie d’un chargement de manière à
maximiser la valeur totale des objets choisis sans dépasser la capacité
maximale. Ce problème est aussi nommé : KP ou "Knapsack Problem".

Dr. Kahina Ghazli Optimisation discrète 23 / 33

Problème du sac à dos
Plus formellement, soit un ensemble de n éléments et une ressource
disponible en quantité limitée W . Pour i = 1, . . . , n, on note pi le profit
associé à la sélection de l’élément i et on note wi la quantité de
ressource que nécessite l’élément i, s’il est sélectionné. Les coefficients pi
et wi prennent des valeurs positives pour tout i = 1, . . . , n.

Le "problème du sac-à-dos" consiste à choisir un sous-ensemble des n

éléments qui maximise le profit total obtenu, en respectant la quantité de
ressource disponible.
Dr. Kahina Ghazli Optimisation discrète 23 / 33
Problème du sac à dos
On associe à chaque élément i une variable de sélection, xi , binaire :

1 si l’élément i est sélectionné,
xi =
0 sinon.

n
P
Le profit total obtenu peut alors s’écrire comme la somme : p i xi .
i=1
n
P
La quantité totale de ressource utilisée comme la somme : wi xi .
i=1
Le problème du sac à dos se modélise donc sous la forme :

Ce problème se particularise par le fait de posséder une seule contrainte : la

contrainte de ressource ou contrainte de sac-à-dos.
Dr. Kahina Ghazli Optimisation discrète 24 / 33
Problème de couverture

Soit P = {1, . . . , m} un ensemble fini d’éléments. Soit P1 , . . . , Pn des sous

ensembles de P .

Le problème de la recherche d’une couverture de coût minimal consiste à

sélectionner des sous-ensembles d’éléments Pj de façon à ce que chaque
élément de P apparaisse au moins une fois, et cela avec le coût global le plus
petit. Ce problème est aussi nommé : SCP ou "Set Covering Problem".
S
Une couverture de P est une collection de Pj qui vérifie : Pj = P
j

Dr. Kahina Ghazli Optimisation discrète 25 / 33

Problème de couverture

Le SCP se modélise sous la forme

n

P


 min cj xj
j=1


n
SCP P
aij xj ≥ 1 i = 1, . . . , m

j=1



xj ∈ {0, 1} j = 1, . . . , n


avec  
1 si i ∈ Pj 1 si Pj appartient à la couverture
aij = et xj =
0 sinon 0 sinon

La première contrainte assure que les sous-ensembles couvrent tous les

éléments de l’ensemble de base P . Chaque élément de l’ensemble de base P est
couvert au moins une fois.

Dr. Kahina Ghazli Optimisation discrète 25 / 33

Problème de partitionnement

Soit P = {1, . . . , m} un ensemble fini d’éléments. Soit P1 , . . . , Pn des

sous ensembles de P .

Le problème de la recherche d’une partition de coût minimal consiste à

sélectionner des sous-ensembles d’éléments Pj de façon à ce que chaque
élément de P apparaisse une fois exactement, et cela avec le coût global
le plus petit. Ce problème est aussi nommé : SPP ou "Set Partitioning
Problem".

Une partition de P est une couverture qui vérifie : Pj ∩ Pk = ∅

Dr. Kahina Ghazli Optimisation discrète 26 / 33

Problème de partitionnement

Le SPP se modélise sous la forme :


Pn


 min cj xj
j=1


n
SP P P
 aij xj = 1 i = 1, . . . , m
j=1



xj ∈ {0, 1} j = 1, . . . , n


avec  
1 si i ∈ Pj 1 si Pj appartient à la couverture
aij = et xj =
0 sinon 0 sinon

La première contrainte assure que chaque élément de l’ensemble de base

P soit couvert exactement une fois.

Dr. Kahina Ghazli Optimisation discrète 26 / 33

Problème de pavage (ou d’emballage)
Soit P = {1, . . . , m} un ensemble fini d’éléments. Soit P1 , . . . , Pn des sous
ensembles de P .

Dans le "problème de pavage", les sous-ensembles d’objets Pj ont une valeur

(un profit) plutôt qu’un coût : le problème consiste à sélectionner des
sous-ensembles disjoints d’éléments Pj de façon à maximiser la valeur totale.
Ce problème est aussi nommé : SPkP ou "Set Packing Problem".
n

P


 max c j xj
j=1


n
SP kP P
aij xj ≤ 1 i = 1, . . . , m

j=1



xj ∈ {0, 1} j = 1, . . . , n


avec  
1 si i ∈ Pj 1 si Pj appartient à la couverture
aij = et xj =
0 sinon 0 sinon

T S
Un pavage de P est une collection de Pj telle que Pj = ∅ et Pj ⊂ P
j j

Dr. Kahina Ghazli Optimisation discrète 27 / 33

Problème de pavage (ou d’emballage)
Soit P = {1, . . . , m} un ensemble fini d’éléments. Soit P1 , . . . , Pn des sous
ensembles de P .

Dans le "problème de pavage", les sous-ensembles d’objets Pj ont une valeur

(un profit) plutôt qu’un coût : le problème consiste à sélectionner des
sous-ensembles disjoints d’éléments Pj de façon à maximiser la valeur totale.
Ce problème est aussi nommé : SPkP ou "Set Packing Problem".
n

P


 max c j xj
j=1


n
SP kP P
aij xj ≤ 1 i = 1, . . . , m

j=1



xj ∈ {0, 1} j = 1, . . . , n


avec  
1 si i ∈ Pj 1 si Pj appartient à la couverture
aij = et xj =
0 sinon 0 sinon

La première contrainte impose que les sous-ensembles Pj soient disjoints. Elle

assure que chaque élément de l’ensemble de base P soit couvert au plus une
fois.
Dr. Kahina Ghazli Optimisation discrète 27 / 33
Illustration

Soient P = {1, 2, 3, 4, 5, 6, 7} et Pj , j = 1, . . . , 6, des sous-ensembles de P .

Soit cj le coût associé à chaque sous-ensemble.

Pj cj
P1 = {1, 2, 7} 5
P2 = {2, 4, 6, 7} 65
P3 = {3, 5} 30
P4 = {4, 6} 60
P5 = {1, 3, 5, 6} 25
P6 = {7} 15

Formuler le problème de recherche de couverture (resp. partition, pavage)

minimale (resp. minimale, maximal) de P comme un PLNE à variables binaires.

(Traité en cours !)

Dr. Kahina Ghazli Optimisation discrète 28 / 33

Méthodes de résolution exactes
Un algorithme universel (Algorithme de force brute) pour la résolution
des problèmes d’optimisation combinatoire : énumérer successivement
toutes les solutions x ∈ X et retenir la meilleure.
Problème : à l’exception de quelques cas triviaux, la taille (cardinalité) de
l’ensemble X est gigantesque !

Les méthodes exactes fournissent évidemment la (une) solution optimale

d’un problème posé. La faiblesse de ces méthodes réside dans le temps
(et parfois l’espace mémoire) nécessaire à la résolution d’une instance.

En simplifiant, on peut séparer les problèmes d’optimisation combinatoire

en deux groupes.
Les problèmes "faciles" : Ce sont les problèmes pour lesquels un bon
algorithme exact, c’est-à-dire polynomial, est connu.
Les problèmes "difficiles" : Ce sont les problèmes pour lesquels
aucun algorithme exact polynomial n’est connu et pour lesquels de
sérieux arguments permettent de penser qu’il n’en existe pas.

Dr. Kahina Ghazli Optimisation discrète 29 / 33

Méthodes de résolution exactes
Les méthodes de résolution exactes se caractérisent par le fait qu’elles
permettent d’obtenir une ou plusieurs solutions dont l’optimalité est
garantie.

Parmi ces méthodes, on peut remarquer l’algorithme simplexe. Pour les

problèmes de type ILP, MILP ou 0-1ILP, il existe plusieurs méthodes :
le "Branch and Bound" consistant à faire une énumération implicite
en séparant le problème en sous-problèmes et en évaluant ceux-ci à
l’aide d’une relaxation jusqu’à ne plus avoir que des problèmes
faciles à résoudre ou dont on sait avec certitude qu’ils ne peuvent
pas contenir de solution optimale.
les méthodes polyédrales consistant à ajouter progressivement des
contraintes supplémentaires afin de ramener le domaine des
solutions admissibles à un domaine convexe.
la programmation dynamique consistant à placer le problème dans
une famille de problèmes de même nature mais de difficulté
différente puis à trouver une relation de récurrence liant les solutions
optimales de ces problèmes.
Dr. Kahina Ghazli Optimisation discrète 30 / 33
Méthodes de résolution approchées

Il est parfois nécessaire de disposer d’une solution de bonne qualité

(proche de l’optimale) dans un contexte de ressources (temps de calcul
et/ou mémoire) limitées. Dans ce cas, l’optimalité de la solution ne sera
pas garantie, ni même l’écart avec la valeur optimale. Le temps
nécessaire pour obtenir une telle solution sera beaucoup plus faible et
pourra même être fixé.

Ce type de méthodes, dites heuristiques est utile pour des problèmes

nécessitant une solution en temps très court ou pour résoudre des
instances de grande taille. Elles peuvent être utilisées afin d’initialiser une
méthode exacte.

Parmi ces méthodes, on distingue les heuristiques ciblées sur un problème

particulier et les métaheuristiques plus puissantes et adaptables pour
résoudre un grand nombre de problèmes. Une métaheuristique, pour être
performante sur un problème donné nécessite une adaptation fine.

Dr. Kahina Ghazli Optimisation discrète 31 / 33

Méthodes de résolution approchées

Une heuristique est un algorithme de résolution ne fournissant pas

nécessairement une solution optimale pour un problème d’optimisation
donné. Une bonne heuristique possède cependant plusieurs
caractéristiques :
elle est de complexité raisonnable (idéalement polynomiale mais en
tout cas efficace en pratique) ;
elle fournit le plus souvent une solution proche de l’optimum ;
la probabilité d’obtenir une solution de mauvaise qualité est faible ;
elle est simple à mettre en oeuvre

Dr. Kahina Ghazli Optimisation discrète 32 / 33

Méthodes de résolution approchées

Les méthodes approchées se classent en différentes catégories dont

les plus connues sont :

Constructives : Algorithmes glouton

Grasp
Recherche locale : Algorithmes de descente
Multi-départs
Algorithme à seuil
Recuit-simulé
Recherche tabou
Evolutionnistes : Algorithmes génétiques
Algorithmes d’évolution
Recherche dispersée
Méthode des chemins
Systèmes de fourmis

Dr. Kahina Ghazli Optimisation discrète 33 / 33