Introduction à la Recherche Opérationelle


M2 Statistique Science des Données (SSD)
Anatoli Juditsky
Franck Iutzeler
Version Py2019

1. Récupération des données

a. Menu

In [1]:
import cvxpy as cp
import pandas as pd
import numpy as np
In [2]:
foods = pd.read_csv("data/food.dat",sep='\t')
n,p = foods.shape 
In [3]:
foods
Out[3]:
Food Cal CalFat Fat SatFat Chol Sodium Carbo Protein VitA VitC Calcium Iron
0 1%_Low_Fat_Milk_Jug 1_carton_(236_ml) ... 100 20 2 1 10 125 12 8 10 4 30 0
1 Apple_Slices 1.2_oz_(34_g) ... 15 0 0 0 0 0 4 0 0 160 2 0
2 BBQ_Ranch_Burger 4.1_oz_(116_g) ... 350 140 16 6 45 680 37 16 4 0 20 15
3 Bacon,_Egg_&_Cheese_Bagel 7_oz_(199_g) ... 630 290 32 11 275 1490 57 30 20 15 20 20
4 Bacon,_Egg_&_Cheese_Bagel_with_Egg_Whites 7.2_... 580 230 26 9 60 1490 55 30 10 15 20 15
... ... ... ... ... ... ... ... ... ... ... ... ... ...
300 Vanilla_McCafe_Shake_(12_fl_oz_cup) 12_fl_oz ... 530 140 15 10 60 160 86 11 20 0 40 0
301 Vanilla_McCafe_Shake_(16_fl_oz_cup) 16_fl_oz ... 660 170 19 12 75 200 109 14 25 0 50 0
302 Vanilla_McCafe_Shake_(22_fl_oz_cup) 22_fl_oz ... 820 210 23 15 90 260 135 18 30 0 60 0
303 Vanilla_Reduced_Fat_Ice_Cream_Cone 3.7_oz_(105... 170 40 4 3 15 70 27 5 6 0 15 2
304 Whipped_Margarine_(1_pat) 1_pkg_(6_g) ... 40 40 4 1 0 55 0 0 4 0 0 0

305 rows × 13 columns

In [4]:
n
Out[4]:
305

2. Alimentation idéale

In [5]:
nutr = pd.read_csv("data/nutr_ideal.dat",sep=' ')
nutr
Out[5]:
Cal CalFat Fat SatFat Chol Sodium Carbo Protein VitA VitC Calcium Iron
0 2500 600 65 20 300 2400 300 50 100 100 100 100

a. Combinaisons pour une alimentation pauvre en calories

Pour commencer, nous allons essayer de trouver une stratégie $x$ en résolvant un problème diet1 de minimisation des calories, sous contrainte de rester idéal vis à vis des autres nutriments (CalFat, Fat, VitA, etc.)

Question: Implementer les fonctions et contraintes suivantes, puis résoudre le problème. Qu'observez-vous sur la solution?

  • Fonction objective linéaire à minimiser: $c^\mathrm{T}x$ où $c$ contient les calories par aliment
In [ ]:
 
  • Contrainte à vérifier: $x$ est positif (par de quantités négatives d'aliments) et $Ax=b$ où $A$ contient les valeurs des nutriments par aliment et $b$ contient les valeurs idéales (sans les calories)
In [ ]:
 
  • Resolution par CVXPY

Attention, utilisez le Solver "ECOS"

    prob.solve(verbose=True,solver="ECOS")

le solveur par défaut peut donner de fausses informations...

In [ ]:
 

b. Relaxation des contraintes

Le problème précedent n'avait pas de point faisable avec les contraintes imposées. Afin d'obtenir des points faisable, nous allons remplacer la contrainte $$ Ax = b$$ par les deux contraintes de type boite $$ Ax \geq 0.8 b ~~ \text{ et } ~~ Ax \leq b $$ ainsi les contraintes de nutriments sont satisfaites entre 80 et 100% et le problème devient faisable.

Question: Définir les deux contraintes de boite et resoudre le problème. Vérifier qu'il est faisable.

In [ ]:
 

Question: Affichez les valeur des nutriments pour la solution obtenue et la comparer à 80% et 100% des valeurs prescrites.

In [ ]:
 

Question: Donner le nombre de calories totales et les aliments pour lesquelles la quantité est supérieure à 0.3.

In [ ]:
 

On remarque que la solution n'est pas pratique!

c. D'autres contraintes

On va imposer:

  • pas de EQUAL_0_Calorie_Sweetener 1_pkg_(1.0_g) (item $73$) ni de SPLENDA_No_Calorie_Sweetener 1_pkg_(1.0_g) : 30.9360336697206 (item $248$) car c'est pas très bon
  • pas plus de 10 unités dans le menu, pas plus de 2 unités par item
  • au moins un petit déjeuner (items 3 à 22)

Relacher au besoin les contraintes de nutrition...

Question : Implémenter ces contraintes une par une et regarder la valeur optimale de la fonction (le nombre de calories). Cette valeur augmente-t-elle ou diminue-t-elle ? Pourquoi ?

In [ ]:
 

Contrainte suivante

In [ ]:
 

Contrainte suivante

In [ ]:
 

3. D'autres problèmes

Beaucoup d'autres problèmes de ce genre existent. Ci-dessous vous trouverez un nouveau problème mais vous êtes également invités à inventer vos propres problèmes et chercher si ils sont solvables par CVXPY !

Question : Quels sont les aliments à choisir pour obtenir au moins les nutriments recommendés en un minimum d'unités ?

In [ ]:
 

Question : Quels nutriments sont les plus dur à obtenir (on pourra regarder la valeur de la variable duale) ?

In [ ]:
 

4. Programmation entière

Les solutions obtenues précédemment sont des solutions continues, alors que l'on commande généralement un nombre entier d'items. Les problèmes d'optimisation avec variables entières appellés (Mixed) Integer Programs, se résolvent avec des méthodes et des solveurs différents. CVXPY appellant différents solveurs nativement, cette opération est transparente ici.

Retour sur le problème 2b

Les différences pour la programmation en nombre entier:

In [6]:
x = cp.Variable(n,integer=True) 

cal = np.array(foods["Cal"]) # calories

diet1 = cp.Minimize(cal*x)
In [7]:
# Constraints matrix
A = np.array(foods.drop(columns=["Food","Cal"])).T
b = np.array(nutr)[0,1:12]
In [8]:
contrainte1 = x>=0
In [9]:
contrainte2a = A*x <= 1.0*b 
contrainte2b = A*x >= 0.8*b
In [10]:
prob2= cp.Problem(diet1 , constraints = [contrainte1, contrainte2a,contrainte2b])
#prob2.solve(verbose=True,solver="ECOS_BB")
In [ ]:
prob.status

Relaxing Constraints

Les problemes MIP (Mixed Integer Programs) sont en général beaucoup plus dur car trouver des points admissibles est difficile.

Question : Relaxoez les contraintes (ex: 0<=x<=2 et Ax>=b) et observez la solution.

In [12]:
contrainte1a = x>=0
contrainte1b = x<=2
contrainte2b = A*x >= b
In [13]:
prob2= cp.Problem(diet1 , constraints = [contrainte1a, contrainte1b, contrainte2b])
#prob2.solve(verbose=True,solver="ECOS_BB")
In [ ]: