TD 9: Programmation Linéaire et Entière avancée

Rappels

• Procédure de rendu
• Deadline de rendu : ce soir à 23:59:59
• Pour exécuter les tests : téléchargez test.tar.gz et décompressez-le dans votre répertoire de travail
• Vidéos du Cours 9 (n'hésitez pas, elles sont bien classées)

Installation de or-tools

mkdir td9  # En etant dans le repertoire or-tools-BlaBlaBla
cd td9
wget --no-cache http://fabien.viger.free.fr/oc/td9/test.tar.gz
tar xf test.tar.gz

Exercice 1: Job assignment

1. Reprenez l'exercice 2 du TD 8: job.h, job.cc.
   On ajoute à présent des contraintes d'exclusivité locale.
   Par exemple: "job X, job Y et job Z sont mutuellement exclusif sur la même machine (quelle qu'elle soit)":
   si le job Y tourne sur la machine #4, alors ni job X ni job Z ne pourront tourner sur la machine #4 (mais ils pourront tourner sur une autre machine).
   Implémentez dans un fichier job1.cc (vous pourrez copier job.cc) la fonction BestJobAssignment1() décrite dans job1.h.

   #ifndef __JOB1_H
   #define __JOB1_H
   
   #include "job.h"
   
   // Comme BestJobAssignment(), mais on a des contraintes d'exclusivités locales:
   // pour chaque liste d'exclusivité L dans "local_exclusive",
   // cela exprime le fait que 2 jobs ayant des indices dans L ne peuvent être
   // placés sur la même machine.
   vector<int> BestJobAssignment1(const vector<Resources>& jobs,
                                  const vector<Resources>& machines,
                                  const vector<vector<int>>& local_exclusive);
   
   #endif  // __JOB1_H

   Test: make job1
   
   RENDU: job1.cc (ne changez pas le .h!)
   
   
2. On revient à la version de base (sans les contraintes d'exclusivité locale), et on ajoute des contraintes de dépendence locale.
   Par exemple: "Si job X tourne sur une machine, il a besoin de job Y sur la même machine".
   NOTE: Je pourrais vous demander de cumuler ces contraintes avec les précédentes, il n'y aurait aucun problème! Mais ça vous empêcherait de "sauter" une question.
   
   Implémentez dans un fichier job2.cc (vous pourrez copier job.cc) la fonction BestJobAssignment2() décrite dans job2.h.

   #ifndef __JOB2_H
   #define __JOB2_H
   
   #include "job.h"
   
   #include <utility>
   using std::pair;
   
   // Comme BestJobAssignment1(), mais on a en plus des contraintes de dépendance
   // locales: pour chaque paire (A, B) dans "local_dep", job A dépend de job B
   // localement, ce qui veut dire que si job A tourne sur une machine, alors
   // job B tourne aussi, et sur la meme machine.
   vector<int> BestJobAssignment2(const vector<Resources>& jobs,
                                  const vector<Resources>& machines,
                                  const vector<pair<int, int>>& local_dep);
   
   #endif  // __JOB2_H

   Test: make job2
   
   RENDU: job2.cc (ne changez pas le .h!)
   
   
3. On ajoute à la version de base des contraintes d'exclusivité globale.
   Par exemple: "Si job X tourne (sur n'importe quelle machine), alors job Y ne peut pas tourner (meme sur une autre machine)".
   Implémentez dans un fichier job3.cc (vous pourrez copier job.cc) la fonction BestJobAssignment3() décrite dans job3.h.

   #ifndef __JOB3_H
   #define __JOB3_H
   
   #include "job.h"
   
   // Comme BestJobAssignment1(), mais les exclusivités sont globales
   // (2 jobs "exclusifs" ne peuvent pas tourner tous les 2, meme sur
   //  des machines différentes).
   vector<int> BestJobAssignment3(const vector<Resources>& jobs,
                                  const vector<Resources>& machines,
                                  const vector<vector<int>>& global_exclusive);
   
   #endif  // __JOB3_H

   Test: make job3
   
   RENDU: job3.cc (ne changez pas le .h!)
   
   
4. On ajoute a la version de base des contraintes d'inter-dépendance globale.
   Par exemple: "job X et job Y ont besoin l'un de l'autre, mais peuvent tourner sur des machines différentes. Donc si job X tourne, alors job Y tourne (possiblement sur une autre machine), et vice-versa".
   Implémentez dans un fichier job4.cc (vous pourrez copier job.cc) la fonction BestJobAssignment4() décrite dans job4.h.

   #ifndef __JOB4_H
   #define __JOB4_H
   
   #include "job.h"
   
   #include <utility>
   using std::pair;
   
   // Comme BestJobAssignment2(), mais les dépendances sont bidirectionelles,
   // et globales: chaque paire (A, B) dans "global_dep" implique que
   // les jobs A et B ne peuvent pas tourner l'un sans l'autre (pas forcément
   // sur la même machine).
   vector<int> BestJobAssignment4(const vector<Resources>& jobs,
                                  const vector<Resources>& machines,
                                  const vector<pair<int, int>>& global_dep);
   
   #endif  // __JOB4_H

   Test: make job4
   
   RENDU: job4.cc (ne changez pas le .h!)
   
   

Exercice 2: assignement des étudiants

• Chaque cours dispose d'une capacité d'accueil limitée
• Pour chaque cours, chaque étudiant donne une valeur entre 0 et 10 exprimant son intérêt pour le cours

• Implémentez dans un fichier students.cc la fonction StudentsAssignment() décrite dans students.h. Ça ressemblera beaucoup au problème des jobs, avec un objectif un peu différent.

  
  #include <vector>&
  
  using std::vector;
  
  // DESCRIPTION DU PROBLÈME
  // Les étudiants sont numérotés de 0 à num_etudiants-1
  // Les cours sont numérotés de 0 à num_cours-1, chacun a une capacité limite
  // en nombre d'étudiants.
  // Ces limites sont stockées dans l'entrée "cours"
  // Chaque étudiant assigne des valeurs réelles aux différents cours:
  // de 0 (s'il ne veut pas s'inscrire) à 10 (s'il veut absolument s'inscrire)
  // La somme de ces valeurs vaut toujours 10.
  //
  // Ces valeurs sont stockées dans l'entrée "valeurs":
  //    valeurs[j][i] contient la valeur que l'étudiant j assigne au cours i.
  // La "valeur totale" d'un étudiant j est la somme des valeurs[j][i] pour
  // tous les cours auxquels il a pu être assigné.
  //
  // On ne pourra pas forcément assigner tout le monde à ses cours préférés,
  // mais on souhaite que le moins bien loti ne se plaigne pas: il faut
  // MAXIMISER la "valeur totale" MINIMALE parmi tous les étudiants.
  //
  // On renverra cette "valeur du moins bien loti".
  double StudentsAssignment(const vector<int>& cours,
                            const vector<vector<double>>& valeurs);
      

Exercice 3: Too Big For Mip

1. Implémentez dans un fichier job0.cc la fonction BestJobAssignment0() décrite dans job0.h.
   
   Indices:
   • Vous pourrez copier-coller le code de job.cc pour avoir la fonction "de base", en le modifiant pour:
     • Ajouter une limite de temps: solver.set_time_limit(1000) donne au solveur une limite de 1 seconde, par exemple.
     • Prendre en compte les profits
   • Vous devrez sans doute, si vous utilisez les limite de temps, faire attention à la valeur de retour de Solve(): MPSolver::OPTIMAL, MPSolver::FEASIBLE, etc. Voir l'enum ResultStatus (définie dans linear_solver.h)
   • Vous pourrez essayer de séparer le probleme en sous-problemes

   #ifndef __JOB0_H
   #define __JOB0_H
   
   #include "job.h"
   
   // Comme le BestJobAssignment() original (sans contraintes exotiques),
   // mais cette fois:
   // 1) Les jobs rapportent un certain "profit", et vous voulez maximiser
   //    la somme des profits des jobs assignés.
   // 2) Vous devrez etre capables de traiter des problemes
   //    de taille beaucoup plus grande
   // 3) Vous ne devez pas dépasser 10s de temps de calcul.
   // 4) Du coup, vous n'etes pas obligé de renvoyer la solution optimale:
   //    votre solution sera jugée en fonction de sa qualité (elle devra
   //    bien sûr etre faisable!)
   vector<int> BestJobAssignment0(const vector<Resources>& jobs,
                                  const vector<double>& profits,
                                  const vector<Resources>& machines);
   
   #endif  // __JOB0_H

   Test: make job0
   
   RENDU: job0.cc (ne changez pas le .h!)