Instances tests pour le problème de Set Packing

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# ContraintesDensité (%)Max-UnsMeilleure valeur connue
pb_100rnd0100.dat1005002,002372*
pb_100rnd0200.dat1005002,00234*
pb_100rnd0300.dat1005002,964203*
pb_100rnd0400.dat1005003,03416*
pb_100rnd0500.dat1001002,002639*
pb_100rnd0600.dat1001002,00264*
pb_100rnd0700.dat1001002,934503*
pb_100rnd0800.dat1001003,07439*
pb_100rnd0900.dat1003002,002463*
pb_100rnd1000.dat1003002,00240*
pb_100rnd1100.dat1003003,084306*
pb_100rnd1200.dat1003002,97423*
pb_200rnd0100.dat2001 0001,494416*
pb_200rnd0200.dat2001 0001,49432*
pb_200rnd0300.dat2001 0001,002731*
pb_200rnd0400.dat2001 0001,00264*
pb_200rnd0500.dat2001 0002,488184*
pb_200rnd0600.dat2001 0002,49814*
pb_200rnd0700.dat2002001,5341 004*
pb_200rnd0800.dat2002001,50483*
pb_200rnd0900.dat2002001,0021 324*
pb_200rnd1000.dat2002001,002118*
pb_200rnd1100.dat2002002,488545*
pb_200rnd1200.dat2002002,57843*
pb_200rnd1300.dat2006001,504571*
pb_200rnd1400.dat2006001,49445*
pb_200rnd1500.dat2006001,002926*
pb_200rnd1600.dat2006001,00279*
pb_200rnd1700.dat2006002,488255*
pb_200rnd1800.dat2006002,56819*
pb_500rnd0100.dat5002 5001,2310323
pb_500rnd0200.dat5002 5001,201025
pb_500rnd0300.dat5002 5000,705776
pb_500rnd0400.dat5002 5000,70562
pb_500rnd0500.dat5002 5002,2220122*
pb_500rnd0600.dat5002 5002,19208
pb_500rnd0700.dat5005001,20101 141*
pb_500rnd0800.dat5005001,191089*
pb_500rnd0900.dat5005000,7052 236*
pb_500rnd1000.dat5005000,705179*
pb_500rnd1100.dat5005002,2620424*
pb_500rnd1200.dat5005002,182033
pb_500rnd1300.dat5001 5001,2110474
pb_500rnd1400.dat5001 5001,211038
pb_500rnd1500.dat5001 5000,6951 196
pb_500rnd1600.dat5001 5000,70588
pb_500rnd1700.dat5001 5002,1720192
pb_500rnd1800.dat5001 5002,202013
pb_1000rnd0100.dat.gz1 0005 0002,605067*
pb_1000rnd0200.dat.gz1 0005 0002,59504*
pb_1000rnd0300.dat.gz1 0005 0000,6010661
pb_1000rnd0400.dat.gz1 0005 0000,601048
pb_1000rnd0500.dat.gz1 0001 0002,6050222
pb_1000rnd0600.dat.gz1 0001 0002,655015
pb_1000rnd0700.dat.gz1 0001 0000,58102 260
pb_1000rnd0800.dat.gz1 0001 0000,6010175
pb_2000rnd0100.dat.gz2 00010 0002,5410040*
pb_2000rnd0200.dat.gz2 00010 0002,551002*
pb_2000rnd0300.dat.gz2 00010 0000,5520478
pb_2000rnd0400.dat.gz2 00010 0000,552032
pb_2000rnd0500.dat.gz2 0002 0002,55100140
pb_2000rnd0600.dat.gz2 0002 0002,561009
pb_2000rnd0700.dat.gz2 0002 0000,56201 811
pb_2000rnd0800.dat.gz2 0002 0000,5620135

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.

Famille d'instances# Variables# ContraintesDensité (%)Max-UnsValeurs des solutions efficaces
2mis100_300.tar.gz1003002,002Sol_2mis100_300.tar.gz
2mis100_500.tar.gz1005002,002Sol_2mis100_500.tar.gz
2mis101_300.tar.gz1003002,002Sol_2mis101_300.tar.gz
2mis101_500.tar.gz1005002,002Sol_2mis101_500.tar.gz
2mis200_1000.tar.gz2001 0001,002Sol_2mis200_1000.tar.gz
2mis200_600.tar.gz2006001,002Sol_2mis200_600.tar.gz
2mis201_1000.tar.gz2001 0001,002Sol_2mis201_1000.tar.gz
2mis201_600.tar.gz2006001,002Sol_2mis201_600.tar.gz
2spp100_300.tar.gz1003003,084Sol_2spp100_300.tar.gz
2spp100_500.tar.gz1005002,964Sol_2spp100_500.tar.gz
2spp101_300.tar.gz1003002,974Sol_2spp101_300.tar.gz
2spp101_500.tar.gz1005003,034Sol_2spp101_500.tar.gz
2spp200_1000.tar.gz2001 0001,494Sol_2spp200_1000.tar.gz
2spp200_600.tar.gz2006001,504Sol_2spp200_600.tar.gz
2spp201_1000.tar.gz2001 0001,494Sol_2spp201_1000.tar.gz
2spp201_600.tar.gz2006001,494Sol_2spp201_600.tar.gz
2spp202_1000.tar.gz2001 0002,488Sol_2spp202_1000.tar.gz
2spp202_600.tar.gz2006002,488Sol_2spp202_600.tar.gz
2spp203_1000.tar.gz2001 0002,498Sol_2spp203_1000.tar.gz
2spp203_600.tar.gz2006002,568Sol_2spp203_600.tar.gz