Exercise Session 8: Advanced Modeling in Mixed Integer Programming

Reminders

• Course Session 8 (in French)
• How to submit your work
• Deadline for submission: tonight at 23h59.
• To run the tests : download test.tar.gz and unpack it in your work directory

Install or-tools

mkdir td8  # Inside the installed ortools directory
cd td8
wget --no-cache http://fabien.viger.free.fr/oc/td8/test.tar.gz
tar xf test.tar.gz
make ortools_test

Exercise 1: Job assignment

1. Copy the code files from exercise 2 of last session: job.h, job.cc.
   We now add mutual exclusion constraints.
   For example: "job X, job Y and job Z are mutually exclusive on the same machine (whichever machine it might be)":
   if job Y runs on machine #4, then neither job X nor job Z can run on machine #4 (but they may run on another machine).
   Implement in file job1.cc (you may start by copying job.cc) the function BestJobAssignment1() described in job1.h.

   #ifndef __JOB1_H
   #define __JOB1_H
   
   #include "job.h"
   
   // Like BestJobAssignment(), but we add local exclusivity constraints:
   // For each exclusivity list L in "local_exclusive",
   // any 2 jobs in L may never run on the same machine.
   vector<int> BestJobAssignment1(const vector<Resources>& jobs,
                                  const vector<Resources>& machines,
                                  const vector<vector<int>>& local_exclusive);
   
   #endif  // __JOB1_H

   Test: make job1
   
   TO SUBMIT: job1.cc (don't change the .h!)
   
   
2. We go back to the initial version, without the local exclusivity constraints, and now we add local dependency constraints.
   For example: "If job X run on a machine, then job Y needs to also run on that same machine".
   NOTE: This question could totally keep the exclusivity constraints: it would be no problem for the MIP model. But it would prevent you from skipping the previous question (if you can't find a way to do it).
   
   Implement in file job2.cc (you can copy job.cc) the function BestJobAssignment2() described in job2.h.

   #ifndef __JOB2_H
   #define __JOB2_H
   
   #include "job.h"
   
   #include <utility>
   using std::pair;
   
   // Like BestJobAssignment1(), but we add local dependency constraints:
   // for each pair (A, B) in "local_dep", job A depends on job B locally, which
   // means that if job A run on some machine, then job B also runs, and runs on
   // the same 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
   
   TO SUBMIT: job2.cc (don't change the .h!)
   
   
3. We go back to the base version and now we add global exclusivity constraints.
   For example: "If job X runs (on any machine), then job Y cannot run (even on another machine)".
   Implement in file job3.cc (you can copy job.cc) the function BestJobAssignment3() described in job3.h.

   #ifndef __JOB3_H
   #define __JOB3_H
   
   #include "job.h"
   
   // Like BestJobAssignment1(), mais the exclusivity is global:
   // 2 "exclusive" jobs can't both be run, even on different machines.
   // But each of them can run if the other doesn't.
   vector<int> BestJobAssignment3(const vector<Resources>& jobs,
                                  const vector<Resources>& machines,
                                  const vector<vector<int>>& global_exclusive);
   
   #endif  // __JOB3_H

   Test: make job3
   
   TO SUBMIT: job3.cc (don't change the .h!)
   
   
4. We go back to the base version and now we add global inter-dependency constraints.
   For example: "job X and job Y need each other, but may run on different machines. So if job X runs, then job Y runs (possibly on a different machine), and vice-versa.
   Implement in file job4.cc (you may copy job.cc) the function BestJobAssignment4() described in job4.h.

   #ifndef __JOB4_H
   #define __JOB4_H
   
   #include "job.h"
   
   #include <utility>
   using std::pair;
   
   // Like BestJobAssignment2(), but dependencies are bidirectionnal and global:
   // each pair (A, B) in "global_dep" implies that job A and B need each other:
   // if one of them runs, the other must run too (not necessarily on the same
   // 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
   
   TO SUBMIT: job4.cc (don't change the .h!)
   
   

Exercise 2: Assignement of Students to Courses

• Each course has a limited capacity of students.
• For each course, each student gave a score between 0 and 10 that expresses their interest in that course

• Implement in file students.cc the function StudentsAssignment() described in students.h. It will be similar to the job assignment problem, but with a different objective.

  
  #include <vector>&
  
  using std::vector;
  
  // PROBLEM DESCRIPTION
  // Students are numbered 0 ... num_students-1
  // Courses are numbered 0 ... num_cours-1, each has a limited student capacity.
  // Those limits are stored in the "cours" input (it means "courses" in French).
  // Each student assigns a score (not necessarily integer) to each course:
  // from 0 (they don't want to follow that course) to 10 (they really want to
  // follow it).
  // The sum of those scores, for each student, is always 10.
  //
  // The scores are stored in the input "valeurs" (means "values" in French):
  //    valeurs[j][i] is the score that student j gave to course i.
  // The "total score" of a student j will be the sum of valeurs[j][i] for
  // all courses i that he was assigned to.
  //
  // We won't necessarily be able to give to each student their favorite courses,
  // but we want to avoid penalizing a student too much:
  // we want to MAXIMIZE the MINIMAL total score among all students.
  //
  // This function returns that worst score (which will be as high as possible).
  double StudentsAssignment(const vector<int>& cours,
                            const vector<vector<double>>& valeurs);
      

Exercice 3: Too Big For Mip

1. Implement in file job0.cc the function BestJobAssignment0() described in job0.h.
   
   Hints:
   • You can copy-paste the code of job.cc to have some skeleton code to get started, and then modify it to:
     • Add a time limit: solver.set_time_limit(1000) gives a time limit to the solver, equal to 1 second (it's in milliseconds).
     • Take into account the profits
   • You will probably have to be careful about the return value of Solve() if you use time limits: MPSolver::OPTIMAL, MPSolver::FEASIBLE, etc. See the ResultStatus enum (found in linear_solver.h)
   • You can try to split the problem into smaller sub-problems.

   #ifndef __JOB0_H
   #define __JOB0_H
   
   #include "job.h"
   
   // Like the original BestJobAssignment() (without exotic constraints),
   // but this time:
   // 1) Each job yields a given "profit" if it runs, and you want to maximize
   //    the total profit of assigned jobs.
   // 2) You must be able to solve much larger models.
   // 3) You may not spend more than 10 seconds.
   // 4) Which also implies that you don't need to return the optimal
   //    solution: your solution will be scored by its quality, i.e. the
   //    total profit it yields (it will of course need to be a valid
   //    solution).
   vector<int> BestJobAssignment0(const vector<Resources>& jobs,
                                  const vector<double>& profits,
                                  const vector<Resources>& machines);
   
   #endif  // __JOB0_H

   Test: make job0
   
   TO SUBMIT: job0.cc (don't change the .h!)