Introduction à la Recherche Opérationelle


M1 Statistique Science des Données (SSD)
Anatoli Juditsky
Franck Iutzeler
2017/2018

1. Récupération des données

a. Menu

In [1]:
foods=read.table("data/food.dat", header=T) #  calories, graisses,  vitamines, protéines, ...

n = nrow(foods) # nombre d'aliments

# Printing
foods
n
FoodQuantityCalCalFatFatSatFatCholSodiumCarboProteinVitAVitCCalciumIron
1%_Low_Fat_Milk_Jug 1_carton_(236_ml) 100 20 2 1 10 125 12 8 10 4 30 0
Apple_Slices 1.2_oz_(34_g) 15 0 0 0 0 0 4 0 0 160 2 0
BBQ_Ranch_Burger 4.1_oz_(116_g) 350 140 16 6 45 680 37 16 4 0 20 15
Bacon,_Egg_&_Cheese_Bagel 7_oz_(199_g) 630 290 32 11 275 1490 57 30 20 15 20 20
Bacon,_Egg_&_Cheese_Bagel_with_Egg_Whites 7.2_oz_(203_g) 580 230 26 9 60 1490 55 30 10 15 20 15
Bacon,_Egg_&_Cheese_Biscuit_(Large_Size_Biscuit) 5.8_oz_(164_g) 520 270 30 14 250 1410 43 19 15 8 20 20
Bacon,_Egg_&_Cheese_Biscuit_(Regular_Size_Biscuit) 5.3_oz_(150_g) 460 230 26 13 250 1300 38 19 10 8 15 15
Bacon,_Egg_&_Cheese_Biscuit_with_Egg_Whites_(Large_Biscuit) 5.9_oz_(167_g) 470 220 25 12 35 1420 42 20 6 8 15 15
Bacon,_Egg_&_Cheese_Biscuit_with_Egg_Whites_(RegularBiscuit)5.4_oz_(153_g) 410 180 20 11 35 1300 36 20 2 8 15 10
Bacon,_Egg_&_Cheese_McGriddles 6.1_oz_(174_g) 460 190 21 9 250 1250 48 19 10 10 20 15
Bacon,_Egg_&_Cheese_McGriddles_with_Egg_Whites 6.3_oz_(178_g) 400 140 15 7 35 1250 47 20 2 10 15 10
Bacon_Buffalo_Ranch_McChicken 5.6_oz_(159_g) 420 180 20 4 50 1250 41 20 2 10 15 15
Bacon_Cheddar_McChicken 6_oz_(171_g) 480 220 24 7 65 1260 43 22 4 10 20 15
Bacon_McDouble 5.8_oz_(165_g) 460 210 24 10 85 1120 34 28 6 10 20 20
Baked_Hot_Apple_Pie 2.7_oz_(77_g) 250 110 13 7 0 170 32 2 4 25 2 6
Big_Breakfast_(Large_Size_Biscuit) 10_oz_(283_g) 800 470 52 18 555 1680 56 28 15 2 15 30
Big_Breakfast_(Regular_Size_Biscuit) 9.5_oz_(269_g) 740 430 48 17 555 1560 51 28 15 2 15 25
Big_Breakfast_with_Egg_Whites_(Large_Size_Biscuit) 10.1_oz_(286_g) 690 370 41 14 35 1700 55 26 4 2 10 15
Big_Breakfast_with_Egg_Whites_(Regular_Size_Biscuit) 9.6_oz_(272_g) 640 330 37 14 35 1590 50 26 0 2 10 15
Big_Breakfast_with_Hotcakes_(Large_Size_Biscuit) 15.3_oz_(434_g) 1150 540 60 20 575 2260 116 36 15 2 30 40
Big_Breakfast_with_Hotcakes_(Regular_Size_Biscuit) 14.8_oz_(420_g) 1090 510 56 19 575 2150 111 36 15 2 25 40
Big_Breakfast_with_Hotcakes_and_Egg_Whites_(Large_Biscuit) 15.4_oz_(437_g) 1050 450 50 16 55 2290 115 35 4 2 25 30
Big_Breakfast_with_Hotcakes_and_Egg_Whites_(Regular_Biscuit)14.9_oz_(423_g) 990 410 46 16 55 2170 110 35 0 2 25 30
Big_Mac 7.6_oz_(215_g) 550 260 29 10 75 970 46 25 4 2 25 25
Blueberry_Pomegranate_Smoothie_(Large) 22_fl_oz_cup 340 10 1 0 5 65 79 4 0 4 10 2
Blueberry_Pomegranate_Smoothie_(Medium) 16_fl_oz_cup 260 5 1 0 5 50 62 3 0 4 8 2
Blueberry_Pomegranate_Smoothie_(Small) 12_fl_oz_cup 220 5 0 0 5 40 50 2 0 2 6 2
Buffalo_Ranch_McChicken 5.1_oz_(145_g) 350 130 15 3 35 980 40 14 2 2 15 15
Caramel_Latte_(Large) 20_fl_oz_cup 430 120 14 8 40 180 62 15 15 0 50 2
Caramel_Latte_(Medium) 16_fl_oz_cup 340 90 10 6 30 140 50 11 10 0 35 0
Spicy_Chicken_McBites_Shareable_Size 10_oz_(284_g) 910 500 55 10 120 1990 61 46 15 4 10 10
Spicy_Chicken_McBites_Snack_Size 3_oz_(85_g) 270 150 17 3 35 600 18 14 4 0 2 2
Sprite_(Child) 12_fl_oz_cup 100 0 0 0 0 25 27 0 0 0 0 0
Sprite_(Large) 30_fl_oz_cup 280 0 0 0 0 60 74 0 0 0 0 0
Sprite_(Medium) 21_fl_oz_cup 200 0 0 0 0 45 54 0 0 0 0 0
Sprite_(Small) 16_fl_oz_cup 140 0 0 0 0 30 37 0 0 0 0 0
Steak,_Egg_&_Cheese_Bagel 8.6_oz_(243_g) 680 320 35 13 300 1520 57 33 20 4 25 25
Steak_&_Egg_Biscuit_(Regular_Biscuit) 7.1_oz_(201_g) 540 290 32 16 280 1470 38 25 10 2 20 25
Steak_&_Egg_McMuffin 6.5_oz_(184_g) 420 200 23 9 300 950 31 26 10 2 30 20
Strawberry_Banana_Smoothie_(Large) 22_fl_oz_cup 330 10 1 0 5 80 74 5 0 45 10 4
Strawberry_Banana_Smoothie_(Medium) 16_fl_oz_cup 250 5 1 0 5 60 58 4 0 35 8 4
Strawberry_Banana_Smoothie_(Small) 12_fl_oz_cup 210 5 0 0 5 50 47 3 0 30 8 2
Strawberry_McCafe_Shake_(12_fl_oz_cup)12_fl_oz 550 150 16 10 60 160 90 12 20 0 40 0
Strawberry_McCafe_Shake_(16_fl_oz_cup)16_fl_oz 690 180 20 13 75 210 114 15 25 0 50 0
Strawberry_McCafe_Shake_(22_fl_oz_cup)22_fl_oz 850 210 24 15 90 260 140 18 30 0 70 0
Strawberry_Preserves 0.5_oz_(14_g) 35 0 0 0 0 0 9 0 0 4 0 0
Strawberry_Sundae 6.3_oz_(178_g) 280 60 6 4 25 85 49 6 8 4 20 0
Sugar_Packet 1_pkg_(4.0_g) 15 0 0 0 0 0 4 0 0 0 0 0
Sweet_'N_Sour_Sauce 1_pkg_(28_g) 50 0 0 0 0 150 12 0 2 0 0 0
Sweet_Tea_(Child) 12_fl_oz_cup 110 0 0 0 0 5 27 0 0 0 0 0
Sweet_Tea_(Large) 30_fl_oz_cup 220 0 0 0 0 10 54 1 0 0 0 0
Sweet_Tea_(Medium) 21_fl_oz_cup 180 0 0 0 0 10 45 1 0 0 0 0
Sweet_Tea_(Small) 16_fl_oz_cup 150 0 0 0 0 10 36 1 0 0 0 0
Tangy_Barbeque_Sauce 1_pkg_(28_g) 50 0 0 0 0 260 12 0 2 0 0 0
Tartar_Sauce_Cup 1_oz_(28_g) 140 130 15 2 10 150 0 0 0 0 2 2
Vanilla_McCafe_Shake_(12_fl_oz_cup) 12_fl_oz 530 140 15 10 60 160 86 11 20 0 40 0
Vanilla_McCafe_Shake_(16_fl_oz_cup) 16_fl_oz 660 170 19 12 75 200 109 14 25 0 50 0
Vanilla_McCafe_Shake_(22_fl_oz_cup) 22_fl_oz 820 210 23 15 90 260 135 18 30 0 60 0
Vanilla_Reduced_Fat_Ice_Cream_Cone 3.7_oz_(105_g) 170 40 4 3 15 70 27 5 6 0 15 2
Whipped_Margarine_(1_pat) 1_pkg_(6_g) 40 40 4 1 0 55 0 0 4 0 0 0
305

2. Alimentation idéale

In [2]:
nutr=read.table("data/nutr_ideal.dat", header=T)
nutr
CalCalFatFatSatFatCholSodiumCarboProteinVitAVitCCalciumIron
2500600 65 20 300 2400300 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.)

In [3]:
library(CVXR)
Attaching package: ‘CVXR’

The following object is masked from ‘package:stats’:

    power

Question: Implementer les fonctions et contraintes suivantes, puis résoudre le problème.

  • 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
In [ ]:

In [ ]:

  • Resolution par CVXR
In [ ]:

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 [ ]:

In [ ]:

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 [ ]:

In [ ]:

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 $74$) ni de SPLENDA_No_Calorie_Sweetener 1_pkg_(1.0_g) : 30.9360336697206 (item $249$) 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 4 à 23)

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 [ ]:

In [ ]:

In [ ]:

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 CVXR !

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

In [ ]:

In [ ]:

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

In [ ]:

In [ ]:

4. Programmation entière avec RMosek

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, comme RMosek.

 a. Installation

Pour l'installation sous Linux:

  • téléchargez et décrompressez Mosek (https://www.mosek.com/) dans votre home
  • demandez une license académique avec votre email universitaire https://license.mosek.com/academic/ et copier le fichier recu dans le répertoire mosek de votre home
  • executez export PATH=$PATH:/home/[USER]/mosek/8/tools/platform/linux64x86/bin où [USER] est votre nom d'utilisateur.
  • Sous R, exécutez install.packages("Rmosek", type="source", repos="http://download.mosek.com/R/8", configure.vars="PKG_MOSEKHOME=/home/[USER]/mosek/8/tools/platform/linux64x86 PKG_MOSEKLIB=mosek64")

b. Retour sur le problème 2b

En RMosek, celui se code de la manière suivante

In [4]:
require(Rmosek)
require(Matrix)
Loading required package: Rmosek
Loading required package: Matrix
In [5]:
dietM = list()
dietM$sense = "min" # we want to minimize ...
dietM$c = as.numeric(unlist(foods[3])) # ... a linear objective: the calories of selected items
In [6]:
# Constraints matrix
A = t(as.matrix(foods[4:14]))
dietM$A = Matrix(A,sparse=TRUE)

# Lower and upper constraints limits
blc = 0.8*as.matrix(nutr[2:12])
buc = 1.0*as.matrix(nutr[2:12])
dietM$bc = rbind(blc, buc);

# Box constraints limits
blx = rep(0,n); bux = rep(Inf,n); 
dietM$bx = rbind(blx, bux);
In [7]:
res = mosek(dietM, list(verbose=0))

res$sol$itr$prosta
xM = res$sol$itr$xx
'PRIMAL_AND_DUAL_FEASIBLE'
In [8]:
for (j in 1:n){
if (xM[j]>0.1){
print( paste(j,foods[j,1],foods[j,2],": ",xM[j]))
}
}
[1] "2 Apple_Slices 1.2_oz_(34_g) :  0.236008829423503"
[1] "44 Chocolate_Chip_Cookie 1_cookie_(33_g) :  3.69309226644752"
[1] "61 Diet_Coke_(Large) 30_fl_oz_cup :  15.7620988922317"
[1] "74 EQUAL_0_Calorie_Sweetener 1_pkg_(1.0_g) :  62.1365500388856"
[1] "75 Egg_McMuffin 4.8_oz_(135_g) :  0.499224588360876"
[1] "79 Fat_Free_Chocolate_Milk_Jug 1_carton_(236_ml) :  1.24818937672678"
[1] "99 Hamburger 3.5_oz_(100_g) :  1.53427764933197"
[1] "260 Sausage_Burrito 3.9_oz_(111_g) :  0.244543125363525"
[1] "265 Side_Salad 3.1_oz_(87_g) :  1.54723638775475"

c. Integer programming

Voici comment ajouter la contrainte d'optimisation en nombres entiers.

In [9]:
dietM$intsub=c(1:n)
In [10]:
res = mosek(dietM, list(verbose=0))

res$sol$int$prosta
xM = res$sol$int$xx
'PRIMAL_INFEASIBLE'

Question : Resoudre le problème de faisabilité puis observer la solution.

In [ ]:

In [ ]: