Phase expérimentale pour le TLBP/B-P

Description de l’environnement des tests

Le logiciel de résolution Nous utilisons les logiciels ILOG Cplex et ILOG Solver qui sont des librairies programmées en C++ proposées par ILOG pour la résolution de modèles linéaires en nombres entiers, en variables mixte ou encore de modèles quadratiques. Pour résoudre un PLNE, Cplex met en œuvre un algorithme de Branch & Cut, c’est-à-dire une procédure par séparation et évaluation intégrant plusieurs types de coupes telles que les coupes de cliques et les coupes de sac à dos. Quant à Solver c’est une PSE qui intègre des algorithmes de filtrage associés à certaine contraintes du type allDiff pour imposer aux variables de prendre des valeurs distinctes.

Jeux de données (instances)

Pour pouvoir faire des conclusions statistiques, nous générons aléatoirement un grand nombre des jeux de données. Pour générer ces instances, nous fixons les paramètres tels que les densités des graphes de contraintes et les cardinalités des ensembles N et B. Nous y intégrons l’ensemble des pré-traitements décrits précédemment (voir la sous-section 4.3.1). Nous vérifions également la cohérence des paramètres entre eux. Par exemple, si nous générons un graphe de précédence dont le chemin le plus long est égale à une valeur k + 1, il n’est pas possible d’imposer une borne supérieure sur le nombre de stations m0 qui soit inférieure1 à k . Chaque instance générée est donc réalisable. Nous indiquons dans le tableau 6.1 les paramètres les plus importants que nous avons utilisé pour construire les jeux de données. 

Représentation des résultats statistiques

Nous rapportons les résultats des expérimentations globalement sous deux formes. La première forme est classique, elle correspond à un nuage de points représentant chacun le temps de résolution d’une instance donnée appartenant à une des familles. Nous utilisons cette représentation lorsque le nombre d’instances testées le permet. Pour les sections dont le nombre de tests est très important, nous employons une seconde forme nommée candlesticks.

Celle-ci représente les temps d’exécution des instances appartenant à une sous-famille donnée. Sa représentation graphiquement nécessite de calculer les valeurs suivantes : – le maximum : le point extrême le plus haut (limite de la droite), – le 3ème quartile : pour un échantillon de valeurs triées, il correspond à la valeur délimitant deux tranches, à savoir : celle des 75% plus petites valeurs des 25% restantes. Cette valeur représente graphiquement le côté supérieur du rectangle, – le 1er quartile : cette valeur délimite les 25% plus petites valeurs de l’échantillon des autres qui leurs sont supérieures, il est indiqué graphiquement par le côté inférieur du rectangle, – le minimum : le point extrême le plus bas. Nous intégrons la médiane de l’échantillon représentée graphiquement par un trait horizontal.