Les caractéristiques numériques prises en compte sont les dimensions de la matrice des contraintes (nombre de variables et de contraintes du problème), sa densité (c'est-à-dire le pourcentage de 1 dans la matrice) et aussi le nombre maximum de 1 par ligne. Nous avons sélectionné des instances parmi 7 familles (41, 61, a1, e1, nre1, cyc6, clr10) en nous assurant de couvrir une vaste gamme de caractéristiques numériques (voir Tableau 3.1).
Nom Variables Contraintes Densité (%) Max-Uns SCP41 1000 200 2.0 30 SCP41r 500 100 2.0 16 SCP61 1000 200 5.0 68 SCP61r 500 100 4.9 38 SCPA1 3000 300 2.0 81 SCPA1r1 500 50 1.8 17 SCPA1r2 1000 100 2.0 30 SCPE1 500 50 20.0 116 SCPE1r1 200 20 24.8 67 SCPE1r2 100 10 29.3 41 SCPNRE1 5000 500 10.0 560 SCPNRE1r1 200 20 10.7 31 SCPNRE1r2 100 10 11.2 14 SCPCYC6 192 240 2.1 4-4 SCPCLR10 210 511 12.3 10-126
Table 3.1: Caractéristiques numériques des instances sélectionnées
Lorsque les solution optimales ne sont pas connues, les résultats peuvent malgré tout être confrontés avec les meilleurs solutions connues rapportées dans [Grossman et al.97]. La comparaison (voir Tableau 3.3) présente GRASP comme étant aussi performant que les autres heuristiques sur pratiquement toutes les instances, se révélant même parfois meilleur. La seule instance pour laquelle GRASP trouve un moins bon résultat est le SCPCYC6. Notons malgré tout que ce problème est particulier étant donné que la meilleure solution trouvée par [Grossman et al.97] a été obtenue à l'aide d'un simple algorithme glouton (et a d'ailleurs aussi été trouvée par l'un de nos algorithmes gloutons).
SCP41 SCP61 SCPA1 SCPE1 Solution Optimale 429 138 253 5 GRASP 433 138 255 5 Différence 0.9 % 0 % 0.8 % 0 %
Table 3.2: Comparaison de GRASP avec les solutions optimales connues
SCP41U SCP61U SCPA1U SCPE1 SCPNRE1U SCPCYC6 SCPCLR10 Littérature 41 21 40 5 17 60 28 GRASP 40 21 40 5 17 61 25
Table 3.3: Comparaison de GRASP avec les meilleurs résultats de la littérature