French Flag Version française

TD 6: Programmation Linéaire

Reminders

Install or-tools


Exercise 1: Optimal Menu

  1. Finish implementing the function MenuMoinsCher() described in file menu.h and implemented in menu.cc ( Download the file menu.cc, read it and edit it: it contains additional information):
    #ifndef __MENU_H
    #define __MENU_H
    
    #include <vector>
    
    using std::vector;
    
    // We are solving the problem of the "least expensive menu".
    // Like what's written on the side of breakfast cereal boxes, we look at the
    // nutritional values of each of our ingredients: calories, proteins, lipids,
    // vitamins, etc.
    //
    // We know the daily recommended amounts of each of these "elements" (element =
    // vitamin, etc). We call them "DRA" (Daily Recommended Amount), and it is given
    // in the "dra" array.
    // For example, if one needs at least 2000 calories, 60g of protein, etc per day,
    // we'll get dra = [2000, 60, ...].
    //
    // We also have the list of all possible ingredients: potatoes, rice,
    // orange juice, chicken, etc.
    // We know the nutrional values of each ingredient in all elements: calories,
    // etc (for 1kg of this ingredient). For ingredient #i those values will be in
    // nutri_values_per_ingredient[i], in the same order as the "dra" array.
    // For example, say 1kg of potatoes amounts to 2500 calories, 10g of proteines,
    // etc; 1kg of rice amounts to 4000 calories, 13g of proteins, etc; and so on
    // for all other ingredients. "nutri_values_per_ingredient" would then be:
    // [[2500, 10, ...],  // 1kg of potatoes
    //  [4000, 13, ...],  // 1kg of rice
    //  ... ]             // .. other ingredients ..
    // 
    // Finally, the price (per kg) of each ingredient is in "price_per_ingredient".
    // Ingredients are listed in the same order as in "nutri_values_per_ingredient".
    // For example, if 1kg of potatoes costs $3.2, 1kg of rice costs $5.4, etc,
    // then price_per_ingredient = [3.2, 5.4, ...]. 
    //
    // The goal is to find the cheapest possible menu that covers *at least* the
    // DRA. I.e. we must find which ingredients to buy, and what quantity. It's ok
    // if we have too much of a given element (e.g. too much vitamin), it doesn't
    // matter. We only need to be ≥ DRA.
    //
    // This function must find this cheapest menu and return the quantity of each
    // ingredient in it, in the same order as "price_per_ingredient".
    // For example, if the cheapest menu is:
    // 0.3kg of potatoes patates, 0kg of rice, 0.2kg of orange juice, ...
    // Then the returned array would be: [0.3, 0, 0.2, ...].
    vector<double> MenuMoinsCher(const vector<double>& dra,
                                 const vector<vector<double>>& nutri_values_per_ingredient,
                                 const vector<double>& price_per_ingredient);
    
    #endif  // __MENU_H
    Test: make menu

    TO SUBMIT: menu.cc (do not modify menu.h!)


Exercise 2: Multi-commodity flow

  1. Complete the implementation of the function BestFlow() described in file flow.h and defined in flow.cc:
    #ifndef __FLOW_H
    #define __FLOW_H
    
    #include <vector>
    
    using std::vector;
    
    // The problem is the assignment of network traffic in a backbone network,
    // which is a weighted directed graph (each arc's weight is its bandwidth
    // capacity, in Gb/s).
    // The graph is given as its number of nodes N and the list of its
    // weighted arcs (from, to, capacity), where "from" and "to" are nodes
    // (i.e. integers between 0 and N-1, inclusive), and "capacity" is the
    // bandwidth in Gb/s.
    // A set of network traffic business demands is also given, as a list of
    // (source, destination, max bandwidth, price per Gb/s): each such demand
    // corresponds to what a client is willing to pay to send some traffic from
    // the node "source" to the node "destination", using our network. If we
    // do provide some bandwidth on our links to satisfy that demand (even
    // partially), the client will pay us the given price per Gb/s we give them,
    // up to the max bandwidth limit.
    //
    // Which business demands, and how much of which, should we fulfill?
    // How shall we route the corresponding traffic?
    struct BackboneArc {
      int from;  // A node
      int to;    // A node
      double capacity;  // >= 0
    };
    struct FlowDemand {
      int src;  // Source: a node
      int dst;  // Destination: a node
      double demand;  // >= 0
      double price;   // per unit of demand (max profit = demand * price)
    };
    struct FlowOnArc {
      int arc_index;  // Index in the "backbone" input argument.
      int demand_index;  // Index in the "demands" input argument.
      double flow;
    };
    vector<FlowOnArc> BestFlow(int num_nodes,
                               const vector<BackboneArc>& backbone,
                               const vector<FlowDemand>& demands);
    
    #endif  // __FLOW_H
    Test: make flow

    TO SUBMIT: flow.cc (do not modify flow.h!)