|
|
|
Benchmark
Recherche Opérationnelle
-
Multi-Choice
Knapsack with Deadlines
Thierry Benoist, Eric Bourreau, Yves
Caseau, Benoît Rottembourg Towards
Stochastic Constraint Programming: A
Study of On-Line Multi-Choice Knapsack
with Deadlines. In Proceedings
CP'01, LNCS 2239, pages 61-76, Springer
2001
Cliquez ici
pour télécharger les instances.
Les résultats reportés
ici sont la moyenne de 1000 lancements.
Les bornes supérieures ont été
calculées par programmation entière.
La meilleure solution du problème
principal a été obtenu
par Bruno Martin en 2002. (in Combinatorial
Aspects of Yield Management, a Reinforcement
Learning Approach).
-
|
Problem
|
Master
|
Pb1
|
Pb2
|
Pb3
|
Pb4
|
Pb5
|
Pb6
|
Pb7
|
|
Best
average gain (1000 runs)
|
500
(Martin)
|
500
|
510
|
459
|
87
|
489
|
1323
|
948
|
|
Far-seeing
upper bounds
|
542
|
556
|
508
|
101
|
-
|
1443
|
-
|
587
|
|
Problem
|
Pb8
|
Pb9
|
Pb10
|
Pb11
|
Pb12
|
Pb17
|
Pb18
|
Pb19
|
|
Best
average gain (1000 runs)
|
538
|
426
|
542
|
488
|
504
|
486
|
495
|
548
|
|
Far-seeing
upper bounds
|
-
|
-
|
-
|
-
|
-
|
-
|
-
|
-
|
|
|
|
