La contrainte MinCumulative

Yanick Ouellet
Claude-Guy Quimper

9 avril 2021
Université Laval

1

Motivation

6789101112131415161718

1920

21

22

2

Motivation

6Demande

718

1

91

10

1

11

1

12

1132

14

1

15

116

117

118

1

19

120

121

122

12

Motivation

6Demande

7

18

1

91

10

1

11

112

1

13

2

14

1

15

1

16

1

17

1

18

1

19

120

1

21

122

12

Approches pour résoudre le problème

MIP
S1 + p1 ≤ S2

3

Approches pour résoudre le problème

MIPPPCS1 + p1 ≤ S2

MinCumul(S, p, h, d)3Approches pour résoudre le problème

MIP

PPC

S1 + p1 ≤ S2

MinCumul(S, p, h, d)

SAT[[S1 = 2]] ∨ [[S2 = 2]]3

Approches pour résoudre le problème

MIP

PPC

S1 + p1 ≤ S2

MinCumul(S, p, h, d)SAT

Méta-heuristiques[[S1 = 2]] ∨ [[S2 = 2]]

def lns(S, p, h, d):3

Programmation par contraintes

4

Programmation par contraintes

Solveur4

Programmation par contraintes

Solveur4

Exemple d’un modèle
Problème
Assigner un quart de travail à Robert, Nancy et Monique.

5

Exemple d’un modèle
Problème
Assigner un quart de travail à Robert, Nancy et Monique.
Variables• R ∈ {AM, PM}• N ∈ {AM, PM}• M ∈ {AM, PM}

5

Exemple d’un modèle
Problème
Assigner un quart de travail à Robert, Nancy et Monique.
Variables• R ∈ {AM, PM}• N ∈ {AM, PM}• M ∈ {AM, PM}
Contraintes• Au moins deux quarts en AM• Au moins un quart en PM• Robert ne peut pas travailler avec Monique (R 6= M)
5

Fonctionnement d’un solveurPrincipe• Construit un arbre de recherche

6Fonctionnement d’un solveur

Principe• Construit un arbre de recherche
Heuristique de branchement• Choisis une variable et une valeur à assigner

6Fonctionnement d’un solveur

Principe• Construit un arbre de recherche
Heuristique de branchement• Choisis une variable et une valeur à assigner
Contraintes• Algorithme de vérification• Algorithme de filtrage6

Arbre de rechercheR ∈ {AM, PM}N ∈ {AM, PM}M ∈ {AM, PM}

R = AMN ∈ {AM, PM}

R = AM

R = AM

N = PM

N = AM

M = PM

M = PM7

Arbre de rechercheR ∈ {AM, PM}N ∈ {AM, PM}M ∈ {AM, PM}

R = AMN ∈ {AM, PM}M ∈ {AM, PM}

R = AM

R = AM

N = PM

N = AM

M = PM

M = PM

7

Arbre de rechercheR ∈ {AM, PM}N ∈ {AM, PM}M ∈ {AM, PM}

R = AMN ∈ {AM, PM}M ∈ {
AM, PM}

R = AM

R = AM

N = PM

N = AM

M = PM

M = PM

7

Arbre de rechercheR ∈ {AM, PM}N ∈ {AM, PM}M ∈ {AM, PM}

R = AMN ∈ {AM, PM}
M = PM

R = AM

R = AM

N = PM

N = AM

M = PM

M = PM

7

Arbre de rechercheR ∈ {AM, PM}N ∈ {AM, PM}M ∈ {AM, PM}

R = AMN ∈ {AM, PM}
M = PM

R = AM

R = AM

N = PM

N = AM

M = PM

M = PM

7

Arbre de rechercheR ∈ {AM, PM}N ∈ {AM, PM}M ∈ {AM, PM}

R = AMN ∈ {AM, PM}
M = PM

R = AM

R = AM

N = PM

N = AM

M = PM

M = PM

7

Arbre de rechercheR ∈ {AM, PM}N ∈ {AM, PM}M ∈ {AM, PM}

R = AMN ∈ {AM, PM}
M = PM

R = AM

R = AM

N = PM

N = AM

M = PM

M = PM

7

Arbre de rechercheR ∈ {AM, PM}N ∈ {AM, PM}M ∈ {AM, PM}

R = AMN ∈ {AM, PM}
M = PM

R = AM

R = AM

N = PM

N = AM

M = PM

M = PM7

Définition d’une tâche

h1 = 2est1

lct1
p1 = 40 1 2 3 4 5 6 7 8 9 10Notation• est : Earliest Starting Time• lct : Lastest Completion Time• p : Processing time
• h : Height8

Contrainte MinCumulative
Définition
MinCumulative(S, p, h, d)Variables et paramètres
• I : Ensemble des tâches

9

Contrainte MinCumulative
Définition
MinCumulative(S, p, h, d)Variables et paramètres
• I : Ensemble des tâches
• T : Ensemble des instants

9

Contrainte MinCumulative
Définition
MinCumulative(S, p, h, d)Variables et paramètres
• I : Ensemble des tâches
• T : Ensemble des instants• Si ∈ [esti , lcti −pi ] : Dates de début de i ∈ I9

Contrainte MinCumulative
Définition
MinCumulative(S, p, h, d)Variables et paramètres
• I : Ensemble des tâches
• T : Ensemble des instants• Si ∈ [esti , lcti −pi ] : Dates de début de i ∈ I• pi : Temps de traitement de i ∈ I9

Contrainte MinCumulative
Définition
MinCumulative(S, p, h, d)Variables et paramètres
• I : Ensemble des tâches
• T : Ensemble des instants• Si ∈ [esti , lcti −pi ] : Dates de début de i ∈ I• pi : Temps de traitement de i ∈ I• hi : Hauteur de i ∈ I9

Contrainte MinCumulative
Définition
MinCumulative(S, p, h, d)Variables et paramètres
• I : Ensemble des tâches• T : Ensemble des instants• Si ∈ [esti , lcti −pi ] : Dates de début de i ∈ I• pi : Temps de traitement de i ∈ I• hi : Hauteur de i ∈ I• dt : Demande à l’instant t ∈ T

9Contrainte MinCumulative

Définition
MinCumulative(S, p, h, d)Décomposition
Xhi ≥ dt ∀t ∈ Ti∈I|Si ≤t<Si +pi

9Contrainte MinCumulative

Définition
MinCumulative(S, p, h, d)Décomposition
Xhi ≥ dt ∀t ∈ Ti∈I|Si ≤t<Si +pi

Objectif
Développer un algorithme de vérification et de filtrage

9Nature de la contrainte

NP-Complet
Décider si la contrainte admet une solution est NP-Complet.

10Nature de la contrainte

NP-Complet
Décider si la contrainte admet une solution est NP-Complet.
Conséquence
Il faut utiliser une relaxation pour détecter l’incohérence etfaire du filtrage.

10

Relaxation complètement élastiqueh=2est

lct
p=4

0 1 2 3 4 5 6 7 8 9 1011

Relaxation complètement élastiqueh=2

e=8estlct

p=40 1 2 3 4 5 6 7 8 9 10Relaxation• Énergie : Aire de la tâche (p · h)11

Relaxation complètement élastiqueh=2estlct
p=4

0 1 2 3 4 5 6 7 8 9 10

Relaxation• Énergie : Aire de la tâche (p · h)11

Relaxation complètement élastique0 1 2 3 4 5 6 7 8 9 10

Relaxation• Énergie : Aire de la tâche (p · h)
• On peut placer l’énergie n’importe où dans [est, lct)
• Préemption possible

11Relaxation complètement élastique0 1 2 3 4 5 6 7 8 9 10

Relaxation• Énergie : Aire de la tâche (p · h)
• On peut placer l’énergie n’importe où dans [est, lct)
• Préemption possible• Possible de dépasser la hauteur

11

Algorithme de vérification
Intuition• Utiliser la relaxation complètement élastique• Trouver une façon de couvrir la demande avec l’énergie

12

Algorithme de vérification
Intuition• Utiliser la relaxation complètement élastique• Trouver une façon de couvrir la demande avec l’énergie

Demande : 2 ∀t ∈ [0, 10)

0 1 2 3 4 5 6 7 8 9 10

12

Algorithme de vérification
Intuition• Utiliser la relaxation complètement élastique• Trouver une façon de couvrir la demande avec l’énergieDemande : 2 ∀t ∈ [0, 10)

0 1 2 3 4 5 6 7 8 9 1012

Algorithme de vérification
Intuition• Utiliser la relaxation complètement élastique• Trouver une façon de couvrir la demande avec l’énergie

Demande : 2 ∀t ∈ [0, 10)

0 1 2 3 4 5 6 7 8 9 10

12

Algorithme de vérification
Algorithme
1. Trier les tâches par lct

13

Algorithme de vérification
Algorithme
1. Trier les tâches par lct
2. Traiter chaque tâche i13

Algorithme de vérification
Algorithme
1. Trier les tâches par lct
2. Traiter chaque tâche i• Céduler son énergie le plus tôt possible

13

Algorithme de vérification
Algorithme
1. Trier les tâches par lct
2. Traiter chaque tâche i• Céduler son énergie le plus tôt possible• Sans dépasser la demande ni son lcti

13

Algorithme de vérification
Algorithme
1. Trier les tâches par lct
2. Traiter chaque tâche i• Céduler son énergie le plus tôt possible• Sans dépasser la demande ni son lcti

3. Si la demande n’est pas entièrement satisfaite,retourner un échec13Algorithme de vérification
Algorithme
1. Trier les tâches par lct
2. Traiter chaque tâche i• Céduler son énergie le plus tôt possible• Sans dépasser la demande ni son lcti

3. Si la demande n’est pas entièrement satisfaite,retourner un échec
Complexité• Linéaire (plus le tri)

13

Algorithme de vérification
Algorithme
1. Trier les tâches par lct
2. Traiter chaque tâche i• Céduler son énergie le plus tôt possible• Sans dépasser la demande ni son lcti

3. Si la demande n’est pas entièrement satisfaite,
retourner un échec
Complexité• Linéaire (plus le tri)
• Grâce aux ensembles disjoints

13TraceTâches#est

lcte10422

1

1010

348814

TraceTâches#est

lcte1042

3

4

8

82

1

101014

TraceTâches

0

123#

est

lcte

1

0

42

3

4

8

8

2

1

10

10

4

5

6

7

8

91014

TraceTâches#est

lcte104

2

34

8

82

1

10

10

4

5

6

1
10123

78

910

14

TraceTâches0#

est

lcte10423488211010

13333133331234567891014

TraceTâches0#est

lcte10423488211010

1222333

312223333

1234

567891014

TraceTâches0#est

lcte104234882

11010

1222

3

3

3

322

1222333

322

1234

56

78

91014

TraceTâches0#est

lcte10423488211010

12223333221222333322123456789X
1014

Algorithme de filtrage
Intuition• Pour chaque tâche i15

Algorithme de filtrage
Intuition• Pour chaque tâche i
1. Fixer la tâche à son esti

15

Algorithme de filtrage
Intuition• Pour chaque tâche i
1. Fixer la tâche à son esti
2. Exécuter l’algorithme de vérification

15

Algorithme de filtrage
Intuition• Pour chaque tâche i
1. Fixer la tâche à son esti
2. Exécuter l’algorithme de vérification
3. Si l’algorithme échoue, i ne peut pas être cédulée à esti

15

Algorithme de filtrage
Intuition• Pour chaque tâche i
1. Fixer la tâche à son esti
2. Exécuter l’algorithme de vérification
3. Si l’algorithme échoue, i ne peut pas être cédulée à esti
4. Filtrer Si à esti +1

15

Algorithme de filtrage
Intuition• Pour chaque tâche i
1. Fixer la tâche à son esti
2. Exécuter l’algorithme de vérification
3. Si l’algorithme échoue, i ne peut pas être cédulée à esti
4. Filtrer Si à esti +1
5. Recommencer jusqu’à ce que l’algorithme devérification retourne un succès

15

Algorithme de filtrage
Intuition• Pour chaque tâche i
1. Fixer la tâche à son esti
2. Exécuter l’algorithme de vérification
3. Si l’algorithme échoue, i ne peut pas être cédulée à esti
4. Filtrer Si à esti +1
5. Recommencer jusqu’à ce que l’algorithme devérification retourne un succès

Vérification par la bande• Vider le domaine d’une tâche ⇒ échec15

Algorithme de filtrage
Intuition• Pour chaque tâche i
1. Fixer la tâche à son esti
2. Exécuter l’algorithme de vérification
3. Si l’algorithme échoue, i ne peut pas être cédulée à esti
4. Filtrer Si à esti +1
5. Recommencer jusqu’à ce que l’algorithme devérification retourne un succès

Vérification par la bande• Vider le domaine d’une tâche ⇒ échec
• Plus fort que l’algorithme de vérification seul

15

Algorithme de filtrage
Intuition• Pour chaque tâche i
1. Fixer la tâche à son esti
2. Exécuter l’algorithme de vérification
3. Si l’algorithme échoue, i ne peut pas être cédulée à esti
4. Filtrer Si à esti +1
5. Recommencer jusqu’à ce que l’algorithme devérification retourne un succès

Vérification par la bande• Vider le domaine d’une tâche ⇒ échec
• Plus fort que l’algorithme de vérification seul
• Pas préemption pour i15

Algorithme de filtrage
Intuition• Pour chaque tâche i
1. Fixer la tâche à son esti
2. Exécuter l’algorithme de vérification
3. Si l’algorithme échoue, i ne peut pas être cédulée à esti
4. Filtrer Si à esti +1
5. Recommencer jusqu’à ce que l’algorithme devérification retourne un succès

Vérification par la bande• Vider le domaine d’une tâche ⇒ échec
• Plus fort que l’algorithme de vérification seul
• Pas préemption pour i• Peut quand même dépasser sa hauteur
15

TraceTâches
#est

lcte1

0422

11010

348816

TraceTâches
#est

lcte1

0

422

1

610348816

TraceTâches0123#est

lcte10422

16103488564

7891016

TraceTâches
#est

lcte

10422

16103

48

8

561
1012347891016

TraceTâches

0#est

lcte

10

422

1610

348

8

122222122222

123

4

56

78

91016

TraceTâches

0#

est

lcte

10422

16103488

12222233

122222331234567891016

TraceTâches

0#est

lcte

10

42216103488333312222233

12222233

1234

567891016

TraceTâches

0#est

lcte

1042216103

488

3

33

3

12222233

122222

3

3

12

3

4

5

6

7

78

91016

Algorithme de filtrage - Complexité

Algorithme naïf• Complexité dépend du nombre d’instants dans l’horizon

17Algorithme de filtrage - Complexité

Algorithme naïf• Complexité dépend du nombre d’instants dans l’horizon• En pire cas, Θ(n2 · |T |)17

Algorithme de filtrage - Complexité

Algorithme naïf• Complexité dépend du nombre d’instants dans l’horizon• En pire cas, Θ(n2 · |T |)Algorithme intelligent• Utilise l’overflow pour filtrer de plus qu’une unité• Détails dans l’article

17

Algorithme de filtrage - Complexité

Algorithme naïf• Complexité dépend du nombre d’instants dans l’horizon• En pire cas, Θ(n2 · |T |)Algorithme intelligent• Utilise l’overflow pour filtrer de plus qu’une unité• Détails dans l’article• Même pire cas, mais plus efficace en pratique

17

Expérimentations - Problème
Problème
Céduler des quarts de travail

18

Expérimentations - Problème
Problème
Céduler des quarts de travail
Employé• Intervalle d’heures total à travailler• Un quart maximum par jour
• 5 jours consécutifs maximum• Entre 4 et 6 heures par quart

18

Expérimentations - Problème
Problème
Céduler des quarts de travailEmployé• Intervalle d’heures total à travailler• Un quart maximum par jour
• 5 jours consécutifs maximum• Entre 4 et 6 heures par quart
DemandePossiblement différente pour chaque tranche de 15 minutes
18

Expérimentations - Modèles

Concurrents• Décomposition (en programmation par contraintes)• Modèle MIP

19

Expérimentations - Modèles

Concurrents• Décomposition (en programmation par contraintes)• Modèle MIP
Objectif• Avec un modèle « simple », trouver des solutions auxinstances difficiles• Être plus efficace que les autres méthodes exactes

19Expérimentations - Modèles
Choix d’algorithme• Vérification seulement• Filtrage naïf• Filtrage intelligent

20

Expérimentations - Modèles
Choix d’algorithme• Vérification seulement• Filtrage naïf• Filtrage intelligent
Modélisation• Une seule MinCumulative pour tout le problème• Une MinCumulative par paire de jours• Un quart de travail qui commence au jour d doit
terminer au plus au jour d + 1• Plus petit n pour chaque contrainte

20

Expérimentations

Méthodologie• Modélisation en Minizinc• Solveur de contraintes : Chuffed• Solveur MIP : CPlex• Limite de 20 minutes

21

Instances aléatoires

Description• 400 instances générées pour comparer le comportement
sur des instances faciles• Paramètres générés aléatoirement avec un petit nombre
de jours

22

Résultats - Instances aléatoires
Configuration# Trouvée# MeilleureDécomposition
MIP
Vérification - Unique
Vérification - MultipleNaïf - UniqueNaïf - Multiple
Intelligent - UniqueIntelligent - Multiple

400
347
398
400
400
400
400
400

81
168
94
236
129
249
131257• Trouvée : Instances pour lesquelles au moins une solution a ététrouvée• Meilleure : Instances pour lesquelles la meilleure solution a ététrouvée
23

Véritables instances

Description• 225 instances de Curtois et al.

24

Véritables instances

Description• 225 instances de Curtois et al.
• Version simplifiée du banc d’essai original

24

Véritables instances

Description• 225 instances de Curtois et al.
• Version simplifiée du banc d’essai original• Très difficile pour une méthode exacte

24

Véritables instances

Description• 225 instances de Curtois et al.
• Version simplifiée du banc d’essai original• Très difficile pour une méthode exacte• Même trouver une seule solution est difficile

24

Résultats - Véritables instances
Configuration# Trouvée# MeilleureDécomposition
MIPVérification - Unique
Vérification - MultipleNaïf - UniqueNaïf - Multiple
Intelligent - UniqueIntelligent - Multiple

00
804
14
100
600110• Trouvée : Instances pour lesquelles au moins une solution a ététrouvée• Meilleure : Instances pour lesquelles la meilleure solution a ététrouvée
25

Conclusion• Introduction de la contrainte MinCumulative• Algorithme de vérification linéaire
• Algorithme de filtrage quadratique• Efficace en pratique26