Le problème de Set Packing est défini par le modèle mathématique suivant :
Max somme{i=1,…,n} c(i) x(i)
sc somme{i=1,…,n} t(i,j) x(i) <= 1, pour j=1,…,m
x(i)=0 ou 1
Le format des 64 fichiers de données disponibles ci-dessous est :
Instance | # Variables | # Contraintes | Densité (%) | Max-Uns | Meilleure valeur connue |
pb_100rnd0100.dat | 100 | 500 | 2,00 | 2 | 372* |
pb_100rnd0200.dat | 100 | 500 | 2,00 | 2 | 34* |
pb_100rnd0300.dat | 100 | 500 | 2,96 | 4 | 203* |
pb_100rnd0400.dat | 100 | 500 | 3,03 | 4 | 16* |
pb_100rnd0500.dat | 100 | 100 | 2,00 | 2 | 639* |
pb_100rnd0600.dat | 100 | 100 | 2,00 | 2 | 64* |
pb_100rnd0700.dat | 100 | 100 | 2,93 | 4 | 503* |
pb_100rnd0800.dat | 100 | 100 | 3,07 | 4 | 39* |
pb_100rnd0900.dat | 100 | 300 | 2,00 | 2 | 463* |
pb_100rnd1000.dat | 100 | 300 | 2,00 | 2 | 40* |
pb_100rnd1100.dat | 100 | 300 | 3,08 | 4 | 306* |
pb_100rnd1200.dat | 100 | 300 | 2,97 | 4 | 23* |
pb_200rnd0100.dat | 200 | 1 000 | 1,49 | 4 | 416* |
pb_200rnd0200.dat | 200 | 1 000 | 1,49 | 4 | 32* |
pb_200rnd0300.dat | 200 | 1 000 | 1,00 | 2 | 731* |
pb_200rnd0400.dat | 200 | 1 000 | 1,00 | 2 | 64* |
pb_200rnd0500.dat | 200 | 1 000 | 2,48 | 8 | 184* |
pb_200rnd0600.dat | 200 | 1 000 | 2,49 | 8 | 14* |
pb_200rnd0700.dat | 200 | 200 | 1,53 | 4 | 1 004* |
pb_200rnd0800.dat | 200 | 200 | 1,50 | 4 | 83* |
pb_200rnd0900.dat | 200 | 200 | 1,00 | 2 | 1 324* |
pb_200rnd1000.dat | 200 | 200 | 1,00 | 2 | 118* |
pb_200rnd1100.dat | 200 | 200 | 2,48 | 8 | 545* |
pb_200rnd1200.dat | 200 | 200 | 2,57 | 8 | 43* |
pb_200rnd1300.dat | 200 | 600 | 1,50 | 4 | 571* |
pb_200rnd1400.dat | 200 | 600 | 1,49 | 4 | 45* |
pb_200rnd1500.dat | 200 | 600 | 1,00 | 2 | 926* |
pb_200rnd1600.dat | 200 | 600 | 1,00 | 2 | 79* |
pb_200rnd1700.dat | 200 | 600 | 2,48 | 8 | 255* |
pb_200rnd1800.dat | 200 | 600 | 2,56 | 8 | 19* |
pb_500rnd0100.dat | 500 | 2 500 | 1,23 | 10 | 323 |
pb_500rnd0200.dat | 500 | 2 500 | 1,20 | 10 | 25 |
pb_500rnd0300.dat | 500 | 2 500 | 0,70 | 5 | 776 |
pb_500rnd0400.dat | 500 | 2 500 | 0,70 | 5 | 62 |
pb_500rnd0500.dat | 500 | 2 500 | 2,22 | 20 | 122* |
pb_500rnd0600.dat | 500 | 2 500 | 2,19 | 20 | 8 |
pb_500rnd0700.dat | 500 | 500 | 1,20 | 10 | 1 141* |
pb_500rnd0800.dat | 500 | 500 | 1,19 | 10 | 89* |
pb_500rnd0900.dat | 500 | 500 | 0,70 | 5 | 2 236* |
pb_500rnd1000.dat | 500 | 500 | 0,70 | 5 | 179* |
pb_500rnd1100.dat | 500 | 500 | 2,26 | 20 | 424* |
pb_500rnd1200.dat | 500 | 500 | 2,18 | 20 | 33 |
pb_500rnd1300.dat | 500 | 1 500 | 1,21 | 10 | 474 |
pb_500rnd1400.dat | 500 | 1 500 | 1,21 | 10 | 38 |
pb_500rnd1500.dat | 500 | 1 500 | 0,69 | 5 | 1 196 |
pb_500rnd1600.dat | 500 | 1 500 | 0,70 | 5 | 88 |
pb_500rnd1700.dat | 500 | 1 500 | 2,17 | 20 | 192 |
pb_500rnd1800.dat | 500 | 1 500 | 2,20 | 20 | 13 |
pb_1000rnd0100.dat.gz | 1 000 | 5 000 | 2,60 | 50 | 67* |
pb_1000rnd0200.dat.gz | 1 000 | 5 000 | 2,59 | 50 | 4* |
pb_1000rnd0300.dat.gz | 1 000 | 5 000 | 0,60 | 10 | 661 |
pb_1000rnd0400.dat.gz | 1 000 | 5 000 | 0,60 | 10 | 48 |
pb_1000rnd0500.dat.gz | 1 000 | 1 000 | 2,60 | 50 | 222 |
pb_1000rnd0600.dat.gz | 1 000 | 1 000 | 2,65 | 50 | 15 |
pb_1000rnd0700.dat.gz | 1 000 | 1 000 | 0,58 | 10 | 2 260 |
pb_1000rnd0800.dat.gz | 1 000 | 1 000 | 0,60 | 10 | 175 |
pb_2000rnd0100.dat.gz | 2 000 | 10 000 | 2,54 | 100 | 40* |
pb_2000rnd0200.dat.gz | 2 000 | 10 000 | 2,55 | 100 | 2* |
pb_2000rnd0300.dat.gz | 2 000 | 10 000 | 0,55 | 20 | 478 |
pb_2000rnd0400.dat.gz | 2 000 | 10 000 | 0,55 | 20 | 32 |
pb_2000rnd0500.dat.gz | 2 000 | 2 000 | 2,55 | 100 | 140 |
pb_2000rnd0600.dat.gz | 2 000 | 2 000 | 2,56 | 100 | 9 |
pb_2000rnd0700.dat.gz | 2 000 | 2 000 | 0,56 | 20 | 1 811 |
pb_2000rnd0800.dat.gz | 2 000 | 2 000 | 0,56 | 20 | 135 |
Max-Uns représente le nombre maximum de colonnes à 1 dans une ligne de la matrice t. Lorsque la valeur de la meilleure solution connue est optimale, elle est suivie d'une astérisque. Vous pouvez aussi récupérer toute la série (instances.tar.gz).
Le problème de Set Packing biobjectif est défini par le modèle mathématique suivant :
Max somme{i=1,…,n} c1(i) x(i)
Max somme{i=1,…,n} c2(i) x(i)
sc somme{i=1,…,n} t(i,j) x(i) <= 1, pour j=1,…,m
x(i)=0 ou 1
Le format des 120 fichiers de données disponibles ci-dessous est :
Les fichiers sont regroupés en 20 familles différentes. Toutes les instances d'une même famille ont le même nombre de contraintes et de variables ainsi que la même matrice t, mais ont des vecteurs de coefficients c1 et c2 différents.