TP2 : Problème de partitionnement

Le SPP (Set Partitioning Problem) est un problème d'optimisation sur des variables binaires xjÎ{0,1} de la forme :
Minimiser  
n
å
j=1
cj xj
    (1)
En vérifiant  
n
å
j=1
aijxj=1     i=1,...,m   aijÎ{0,1}
    (2)

L'application classique de SPP est le problème de génération des rotations d'équipages dans les compagnies aériennes. Dans cette formulation, chaque ligne (i=1,...,m) représente un vol qui doit être effectué. Chaque colonne (j=1,...,n) correspond à la rotation possible d'un équipage. La matrice (aij) est définie avec aij=1 si la rotation j effectue le vol i, aij=0 sinon. L'objectif est de trouver un ensemble de rotations qui couvre tous les vols et qui est « minimal » : on prend cj le coût de la rotation j.

  1. En utilisant ILOG Solver, implanter un algorithme de résolution du problème suivant :

    Rotation : 1 2 3 4 5 6 7 8 9 10
    Coût : 5 1 2 1 4 1 3 2 1 2
    vol 1 1 0 1 0 1 0 0 0 0 1
    vol 2 1 1 1 1 1 1 0 1 0 0
    vol 3 1 0 0 1 0 1 1 1 1 0
    vol 4 1 1 0 0 0 0 1 0 1 1

  2. Le fichier /usr/local/serveur/ILOG/rotations.dat contient les données d'un problème réel. C'est un fichiers contenant des entiers dans l'ordre suivant : Résoudre ce problème1.

  3. Pour améliorer la recherche, modifier l'instanciation des variables afin que la valeur 1 soit tentée avant la valeur 0 (justifier ce choix). Pour cela, définir une sous-classe de IlcIntSelectI en redéfinissant la méthode select() et définir la « handle » de type IlcIntSelect correspondante. Puis utiliser le but 
    IlcGenerate(const IlcIntVarArray, IlcChooseIntIndex, IlcIntSelect);
1
Meilleure solution, prouvée, de coût 11307.
This document was translated from LATEX by HEVEA.