Exercise Session 7: Linear and [Mixed] Integer Programming

Reminders

• Course Session 7 (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 td7  # Inside the installed ortools directory
cd td7
wget --no-cache http://fabien.viger.free.fr/oc/td7/test.tar.gz
tar xf test.tar.gz
make ortools_test

Exercise 2: Job assignment

1. You own a datacenter and you need to run a set of jobs on your machines.
   Implement in a new file job.cc the function BestJobAssignment() described in job.h.
   
   WARNING: since this model uses integer variables, you must use:
   • SAT_INTEGER_PROGRAMMING or CBC_MIXED_INTEGER_PROGRAMMING instead of GLOP_LINEAR_PROGRAMMING when you create the solver.
   • MakeBoolVar(..) or MakeIntVar(..) when creating an integer variable instead of MakeVar(..)

   #ifndef __JOB_H
   #define __JOB_H
   
   #include <vector>
   
   using std::vector;
   
   // We want to assign jobs to machines.
   // We have a set of heterogeneous machines, and the description of all jobs.
   // Each job usess a given quantity of CPU, RAM and Disk of the machine on
   // which it will run, and each machine has a given quantity of available
   // CPU, RAM and Disk.
   //
   // We want to maximize the number of jobs assigned to machines.
   //
   // This function returns an assignment of jobs to machine:
   // element #i will be the index of the machine that runs job #i,
   // or -1 if we've decided to not assign (i.e. not run) that job.
   struct Resources {
     double cpu;
     double ram;
     double disk;
   };
   vector<int> BestJobAssignment(const vector<Resources>& jobs,
                                 const vector<Resources>& machines);
   
   #endif  // __JOB_H

   Test: make job
   
   TO SUBMIT: job.cc (do not change job.h!)
   
   

Exercice 1: Multi-commodity flow, version 2

1. Recover exercise 2 from last week: flow.h, flow.cc.
   Download the new flow2.h (which #include flow.h), and rename flow.cc as flow2.cc, and modify it to fit flow2.h.

   #ifndef __FLOW2_H
   #define __FLOW2_H
   
   #include "flow.h"
   
   // Like BestFlow() in flow.h, but we add a penalty cost for "filling" the
   // backbone arcs too much: if the utilization ratio U of an arc (U is in
   // [0,1], U=0 means unused, U=1 means fully used, at capacity limit) is
   // greater than some constant x (for example x=0.9), we'll pay a penalty
   // cost proportional to (U - x).
   //
   // We still want to maximize profit, but taking the costs into account (as
   // negative profits).
   //
   // Example:
   // - A backbone with 4 arcs of capacities 1000, 300, 500, 100.
   // - A solution where the sums of flows on these 4 arcs are: 840, 300, 470, 90
   //   (those are the 'U' in the fomula above).
   // If max_free_utilization_ratio=0.9 (this is the 'x' in the formula above),
   // the arcs that are "over-utilized" are the second and third one. The first
   // one is below the threshold, and the last is exactly at the threshold.
   // The over-utilization coefficients of these arcs are: 0, 0.1, 0.04, 0
   // (these are the (U - x) in the formula above)).
   // If penalt_cost=100, the cost of this over-utilization is:
   // 0.1 * penalty_cost + 0.04 * penalty_cost = 14.
   //
   // HINTS:
   // One can mimic and even replace the original capacity constraints from
   // last week's flow.cc by introducing the "over-utilization" variables, and
   // adding them to the capacity constraints.
   vector<FlowOnArc> BestFlow2(int num_nodes, const vector<BackboneArc>& backbone,
                               const vector<FlowDemand>& demands,
                               double max_free_utilization_ratio,
                               double penalty_cost);
   
   #endif  // __FLOW2_H
   
   

   Test:

   wget ‐‐no-cache http://fabien.viger.free.fr/oc/td7/test.tar.gz
   tar xf test.tar.gz
   make flow2

   TO SUBMIT: flow2.cc (do not modify the .h files!)