j - Université de Reims Champagne

Info0804
Recherche Opérationnelle
Cours 6
Optimisation combinatoire :
Applications et compléments
Pierre Delisle
Université de Reims Champagne-Ardenne
Département de Mathématiques et Informatique
17 février 2014
Plan de la séance
●
Différents problèmes d'optimisation
académiques et industriels
–
Problèmes de planification de personnel dans les
transports
–
Problèmes d'ordonnancement
●
Optimisation et calcul HPC
●
Métaheuristiques parallèles
Info0804
Cours 6
2
Le problème de la planification du personnel dans
les systèmes de transport
Info0804
Cours 6
3
2 problèmes
d'optimisation
Offre de service
Opérationnel
Courses commerciales
connues par les
voyageurs
Info0804
Cours 6
4
Problème de Graphicage
●
Définition de l'offre de service
–
●
Quels sont les points qui seront desservis ?
Découpage en services voiture
–
Info0804
Quelles sont les lignes qui seront empruntées par
les véhicules ?
Cours 6
5
Vehicle scheduling problem
●
●
Différentes formulations
–
Travelling Salesman Problem (TSP)
–
Multiple Travelling Salesman Problem (MTSP)
–
Vehicle Routing Problem (VRP)
–
Capacitated Vehicle Routing Problem (CVRP)
–
Vehicle Routing Problem with Time
Windows(VRPTW)
–
Vehicle Routing and Scheduling Problem (VSRP)
+ contraintes « industrielles »
Info0804
Cours 6
6
Habillage
●
Découpage en services agent
–
Info0804
De quelle façon assigner les personnels aux
véhicules ?
Cours 6
7
Approche de résolution habituelle
●
●
●
●
Générer et affecter un coût à un ensemble initial (S)
d’horaires de personnel réalisables
Formuler le problème de choisir dans S un sousensemble de coût minimum qui réalise toutes les
tâches
–
Couverture d’ensemble (Set Covering Problem) ou
–
Partitionnement d’ensemble (Set Partitioning Problem)
Résolution du SCP/SPP en utilisant un algorithme
approprié (Branch and bound basé sur la PL)
Utilisation de techniques de génération de colonnes
pour déterminer S
Info0804
Cours 6
8
Modélisation du problème
d'habillage
●
●
Modélisation sous forme de problèmes d'optimisation
classiques de la recherche opérationnelle
–
Vue concise de la structure sous-jacente des problèmes
industriels
–
Utilisation de méthodes d'optimisation existantes
–
Différentes contraintes industrielles peuvent ensuite être ajoutées
3 problèmes
–
Set Covering Problem (SCP)
–
Set Partitioning Problem (SPP)
–
Crew Scheduling Problem (CSP)
Info0804
Cours 6
9
Set Covering Problem
●
Ensemble fini X
●
Ensemble S de sous-ensembles de X
●
Trouver un sous-ensemble de S
●
●
–
Qui couvre tous les éléments de X
–
De cardinal minimum
Solutions possibles
–
s1, s2, s3, s4, s5
–
s2, s5, s6
Exemple : Formation d'un comité
Info0804
Cours 6
10
Set Partitioning Problem
●
Ensemble fini X
●
Ensemble S de sous-ensembles de X
●
Trouver un sous-ensemble de S
–
Qui couvre tous les éléments de X
–
De cardinal minimum
–
Chaque élément ne doit être
couvert qu'une seule fois
●
Solutions possibles
–
●
s 2, s 5, s 6
Exemple : Planification d'un mariage !
Info0804
Cours 6
11
Modélisation mathématique du SCP
et du SPP
Minimiser
n
∑
cjxj
(1)
Le coût de l'ensemble des colonnes
i = 1,..., m
(2)
Chaque ligne doit être couverte :
- Au moins une fois pour le SCP (≥)
- Exactement une fois pour le SPP (=)
j = 1,..., n
(3)
Une colonne peut être sélectionée (1) ou non (0)
j= 1
Sous les contraintes
n
∑
aijxj ≥ 1
j= 1
xj ∈ (0,1)
c1
c2
c3
c4
c5
2
8
5
9
4
Ligne 1
1
1
1
0
0
Ligne 2
0
0
1
0
1
Ligne 3
0
1
0
1
0
Ligne 4
0
0
0
1
1
- {c1, c3, c4} est une solution réalisable du SCP mais
pas du SPP
- {c2, c5} est une solution réalisable du SCP et du SPP
Exemple
Info0804
Cours 6
12
SCP, SPP et planification de
personnel
●
●
●
Division des services voiture en morceaux de course
Création de services agent couvrant plusieurs
morceaux de course
Set Covering ou Set Partitioning ?
–
Info0804
Exemple : déplacement haut-le-pied (deadhead) permis ou non
Cours 6
13
Le problème de Crew Scheduling
●
N tâches effectuées par k personnels
●
Début et fin d'une journée
N-1
Tâches
de travail au même dépôt
●
●
●
N
k
0
i
Temps de travail maximum T
2
1
Arc de transition
–
De coût cij
–
S'il est possible pour un personnel
de réaliser i puis j
Temps
Trouver les chemins de personnel
–
–
–
Info0804
N+1
j
Personnel 1
0
1
2
N+1
Personnel 2
0
i
j
N-1
Personnel 3
0
k
N
N+1
N+1
De coût total minimum
De sorte que chaque tâche soit réalisée une seule fois
Et que le temps de travail impliqué dans chaque chemin ne dépasse pas
le temps de travail T
Cours 6
14
Modélisation mathématique du CSP
Minimiser
∑
cij xij
(1)
Le coût de l'ensemble des arcs de transition
j = 1,..., N
(2)
Le nombre d'arcs quittant une tâche est égal au
nombre d'arcs entrant dans la tâche
i = 1,...,N
(3)
Un arc quitte chaque tâche
(4)
K arcs originaires de 0 (dépôt) sont utilisés (K
tâches sont choisies pour être la première tâche
sur un chemin)
i, j
Sous les contraintes
∑
xjk =
∑
xij = 1
k
∑
xij
i
j
∑
x0 j = K
j
(Contraintes de limite de temps) (5)
xij ∈ (0,1) ∀ i, j
Info0804
(6)
Chaque arc peut être utilisé au
maximum une fois (les chemins
sont arc disjoints)
Cours 6
15
Relaxation lagrangienne pour le
CSP
Minimiser
∑
cij xij +
N
∑
ui (1 −
i= 1
i, j
∑
xij )
(1) Introduction des multiplicateurs u et relaxation
i
de l’équation 3 (un arc quitte chaque tâche)
j
Sous les contraintes
∑
xjk =
k
∑
∑
xij
j = 1,..., N
(2)
Il doit y avoir K chemins d’arcs
disjoints contraints par la limite de
temps T
(4)
La fonction objectif est de
minimiser le coût (lagrangien) total
de ces K chemins
i
x0 j = K
j
(Contraintes de limite de temps) (5)
xij ∈ (0,1) ∀ i, j
Info0804
(6)
Difficulté du problème : nécessité
d’avoir des chemins d’arcs disjoints
- Solution : relaxer l’équation 6
Cours 6
16
Relaxation lagrangienne pour le
CSP
Minimiser
∑
N
∑
cij xij +
∑
ui (1 −
i= 1
i, j
xij )
j
Sous les contraintes
∑
xjk =
k
∑
∑
xij
j = 1,..., N
i
Problème relaxé :
Trouver les k chemins contraints par la limite
de temps, de coût (lagrangien) minimum,
parmi N chemins
Solution du problème relaxé :
Borne inférieure de la solution du CSP
original
Optimisation de subgradient :
Permet de trouver les bons ui
x0 j = K
j
(Contraintes de limite de temps)
x 0 j ∈ (0,1)
j = 1,..., N
xij ≥ 0 entier ∀ i ≠ 0, j
Info0804
On permet aux arcs (et donc aux tâches)
d’apparaître dans plusieurs chemins,
sauf ceux qui démarrent au dépôt
Cours 6
17
Méthode par séparation et
évaluation (Branch and bound)
●
Si la procédure d'optimisation de subgradient trouve
une solution réalisable
–
●
●
On a trouvé la solution optimale du problème original
Sinon
–
i.e. si, dans la meilleure solution, il reste des tâches de degrés
entrant/sortant différents de 1
–
i.e. si certaines tâches sont utilisées plusieurs fois ou pas du tout
…une procédure de séparation-évaluation est
nécessaire pour trouver la solution optimale
–
Info0804
À partir de la solution associée à la meilleure borne inférieure, interdire
successivement les arcs associés à des tâches de degrés
entrant/sortant > 1
Cours 6
18
Méthode par séparation et
évaluation (Branch and bound)
Info0804
Cours 6
19
Problème d'ordonnancement industriel :
Production d'aluminium
Info0804
Cours 6
20
Le processus industriel de
production d'aluminium
Info0804
Cours 6
21
Le processus de coulée
●
Coulée de l'aluminium sur une machine à
couler horizontale
Info0804
Cours 6
22
Considérations du problème
●
Déterminer l’ordre de passage de n commandes en considérant
plusieurs contraintes technologiques et administratives
●
Date de livraison à respecter pour chaque commande
●
Deux types de réglages:
●
–
Changement du moule pour des produits de dimension différente
–
Drainage des fours pour des produits d’alliage différent
Objectifs multiples à minimiser
–
Pertes de temps à la machine à couler
–
Retard total pour l’ensemble des commandes
–
Perte de capacité de transport
Info0804
Cours 6
23
Exemple de problème
Info0804
Cours 6
24
Single Machine Scheduling Problem
●
●
●
●
Une machine est toujours disponible durant la période
d'ordonnancement
La machine traite les jobs un à la fois
Le temps de traitement de chaque job sur la machine
est connu et ne dépend pas des jobs précédents
Le temps de traitement inclut le temps de setup et le
temps sur machine
Info0804
Cours 6
25
Objectifs classiques à optimiser
Info0804
Cours 6
26
Implémentation logicielle
Info0804
Cours 6
27
Variantes
●
Plusieurs machines parallèles
●
Atelier sériel (flowshop)
Info0804
Cours 6
28
Variantes
●
Atelier à cheminements multiples (job shop)
Info0804
Cours 6
29
Optimisation et calcul HPC
Info0804
Cours 6
30
Optimisation et calcul HPC
●
●
Architectures parallèles actuelles
–
Clusters, SMPs, processeurs multi-coeur, GPUs, hybrides
–
Offrent des ressources de calcul imposantes
–
Le problème est de les utiliser efficacement !
Stratégies de parallélisation des méthodes arborescentes
–
●
●
Maître-esclave, décomposition de domaine
Stratégies de parallélisation des métaheuristiques
–
Accélération du processus de recherche de solutions
–
Amélioration de la recherche par la concurrence
Problématiques
–
–
Info0804
Performance, portabilité et reproductibilité sur une architecture cible
Architectures hybrides → méthodes hybrides
Cours 6
31
Hybridation technologique
Info0804
Cours 6
32
Hybridation technologique
Info0804
Cours 6
33
Métaheuristiques parallèles
Conception
Implémentation
Info0804
Cours 6
34
Métaheuristiques parallèles
●
●
Métaheuristiques : stratégies efficaces pouvant
demander beaucoup de ressources
–
Temps de calcul
–
Mémoire
Les 2 contributions principales du parallélisme
aux métaheuristiques :
–
Accélérer le processus de recherche de solutions
–
Améliorer la recherche par des activités
concurrentes
Info0804
Cours 6
35
Stratégies de parallélisation
des métaheuristiques
●
●
●
Processus de recherche simple
–
Parallélisation interne
–
Décomposition de domaine
Processus de recherche multiples
–
Processus indépendants
–
Processus coopératifs
Approches hybrides
Info0804
Cours 6
36
La coopération entre
processus de recherche
●
Résolution d’un problème par un groupe
d’agents coopérant
●
Nouvelle forme d’apprentissage
●
Parallélisme naturel
●
3 questions importantes
–
Quelle information doit être partagée ?
–
À quel moment doit-elle être partagée ?
–
Entre quels processus doit-elle être partagée ?
Info0804
Cours 6
37
Parallélisation des
algorithmes génétiques
●
Parallélisation maître-esclave sur une population
unique
–
–
●
Paralélisation de grain fin sur une population unique
–
●
Population sur le processeur maître
Appel aux esclaves pour appliquer les opérateurs
génétiques
Répartition des individus sur les processeurs
Parallélisation de gros grain sur des population
multiples (modèle en îles)
–
–
Info0804
Une population par processeur
Migration d'individus
Cours 6
38
Parallélisation de l’OCF
●
Niveau Colonie
–
–
–
●
Interaction (indépendant/coopératif)
Échange d’information (phéromone/solutions)
Coordination et schéma d’échange
Niveau Fourmi
–
–
–
–
Info0804
Construction des solutions
Gestion de la phéromone
Gestion de la liste de candidats
Recherche locale
Cours 6
39
Études de cas
Info0804
Cours 6
40
Résolution exacte du CSP sur CPU/GPU
Info0804
Cours 6
41
Architecture GPU
GPU
Architecture massivement parallèle
Prix raisonnable
CUDA (Compute Unified
Device Architecture)
Challenges
Conception
Programmation
Info0804
Cours 6
42
Relaxation lagrangienne pour le
CSP
Problème relaxé
Relaxation lagrangienne pour le CSP
- Construction du problème
- Définition des arcs fixés
- Résolution du problème relaxé
- Optimisation de subgradient
Branch and Bound
Calcul des plus courts chemins
contraints
bloc i : plus court chemin à partir de i
thread : sommet du graphe
Info0804
Cours 6
43
Résultats expérimentaux
●
●
●
Code
–
C++
–
CUDA 4.0
Problèmes tests
–
50 à 500 tâches
–
OR-Library (benchmarks publics de la communauté scientifique)
Nœud de calcul GPU sur Clovis
–
GPU Tesla C2050 – Architecture Fermi
–
448 unités de calcul
Info0804
Cours 6
44
Résultats expérimentaux
180
Temps CPU
Temps d'exécution (s)
160
155
Temps CPU+GPU
140
120
100
93
84
80
60
53
43
40
20
20
0
0
0
50
0
0
100
2
1
150
2
1
200
4
1
250
4
15
20
1
300
350
400
450
500
Nombre de tâches
Info0804
Cours 6
45
Optimisation par Colonie de Fourmis sur
CPU/GPU
Info0804
Cours 6
46
Optimisation par Colonie de
Fourmis
●
Inspiré des comportements collectifs
des insectes sociaux
●
Construction des solutions
–
●
Règle de transition

Informations heuristique

Phéromone
Mise à jour de la phéromone
–
Intensification
–
Évaporation
Info0804
Cours 6
Initialisation des traces de phéromone
Pour un nombre de cycles donné faire
●
Pour chaque fourmi k faire
- Positionnement de la fourmi k sur
une ville choisie aléatoirement
- Construction de la tournée par la
règle de transition
- Calcul de la longueur de la tournée
●
Mise à jour de la meilleure tournée
●
Mise à jour des traces de phéromone
47
Optimisation par Colonie de
Fourmis sur GPU
Info0804
Cours 6
48
Résultats expérimentaux
50
41,02
Accélérations
40
30
20
10
0
35,39
31,68
13,58
5,74
5,35
eil51
8,62
kroA100
16,77
11,9
d198
20,8
19,72
23,14
20,34
14,76
lin318
rat783
fl1577
d2103
Problèmes
Info0804
Cours 6
49
Conclusion et perspectives
●
●
●
●
●
Calcul HPC → potentiel pour méthodes exactes
et approchées
Intégration aux solutions logicielles
commerciales
Beaucoup de travail reste à faire, conceptuel et
technique
GPU → performance vs. effort de recherche et
développement ?
Mais, que nous réserve le futur du HPC ?
Info0804
Cours 6
50
La semaine prochaine
Pas de semaine prochaine, c'est
terminé ☹
Info0804
Cours 6
51

Download Report