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.

  • Fonction objective linéaire à minimiser: $c^\mathrm{T}x$ où $c$ contient les calories par aliment
In [6]:
x = cp.Variable(n) 

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

diet1 = cp.Minimize(cal*x)
  • 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 [7]:
# Constraints matrix
A = np.array(foods.drop(columns=["Food","Cal"])).T
b = np.array(nutr)[0,1:12]
In [8]:
A
Out[8]:
array([[ 20,   0, 140, ..., 210,  40,  40],
       [  2,   0,  16, ...,  23,   4,   4],
       [  1,   0,   6, ...,  15,   3,   1],
       ...,
       [  4, 160,   0, ...,   0,   0,   0],
       [ 30,   2,  20, ...,  60,  15,   0],
       [  0,   0,  15, ...,   0,   2,   0]])
In [9]:
b
Out[9]:
array([ 600,   65,   20,  300, 2400,  300,   50,  100,  100,  100,  100])
In [10]:
contrainte1 = x>= 0.0
contrainte2 = A*x - b == 0.0
  • Resolution par CVXR

Attention, utilisez le Solver "ECOS"

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

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

In [11]:
prob =  cp.Problem(diet1 , constraints = [contrainte1, contrainte2])
prob.solve(verbose=True,solver="ECOS")
ECOS 2.0.7 - (C) embotech GmbH, Zurich Switzerland, 2012-15. Web: www.embotech.com/ECOS

It     pcost       dcost      gap   pres   dres    k/t    mu     step   sigma     IR    |   BT
 0  +2.013e+03  +2.013e+03  +3e+03  7e-01  8e-02  1e+00  1e+01    ---    ---    1  1  - |  -  - 
 1  +1.933e+03  +1.938e+03  +2e+03  1e+00  1e-01  7e+00  8e+00  0.4808  4e-01   1  1  1 |  0  0
 2  +1.177e+03  +1.192e+03  +4e+02  6e-01  8e-02  2e+01  1e+00  0.8448  3e-02   1  1  1 |  0  0
 3  +1.190e+03  +1.195e+03  +5e+01  2e-01  1e-02  6e+00  2e-01  0.8924  1e-02   1  1  1 |  0  0
 4  +1.607e+03  +1.621e+03  +2e+01  5e-01  1e-02  1e+01  7e-02  0.7035  2e-01   1  1  1 |  0  0
 5  +1.983e+03  +2.054e+03  +3e+00  5e-01  1e-02  7e+01  1e-02  0.8444  6e-03   1  1  1 |  0  0
 6  +1.941e+03  +7.645e+03  +4e-02  5e-01  1e-02  6e+03  1e-04  0.9890  2e-03   1  1  1 |  0  0
 7  +1.941e+03  +5.161e+05  +5e-04  5e-01  1e-02  5e+05  2e-06  0.9890  1e-04   1  1  1 |  0  0
 8  +1.941e+03  +4.636e+07  +5e-06  5e-01  1e-02  5e+07  2e-08  0.9890  1e-04   3  2  2 |  0  0
 9  +1.941e+03  +4.175e+09  +6e-08  5e-01  1e-02  4e+09  2e-10  0.9890  1e-04   3  2  2 |  0  0

PRIMAL INFEASIBLE (within feastol=5.1e-10).
Runtime: 0.006550 seconds.

Out[11]:
inf
In [12]:
prob.status
Out[12]:
'infeasible'

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 [13]:
contrainte2a = A*x <= 1.0*b 
contrainte2b = A*x >= 0.8*b
In [14]:
prob2= cp.Problem(diet1 , constraints = [contrainte1, contrainte2a,contrainte2b])
prob2.solve(verbose=True,solver="ECOS")
ECOS 2.0.7 - (C) embotech GmbH, Zurich Switzerland, 2012-15. Web: www.embotech.com/ECOS

It     pcost       dcost      gap   pres   dres    k/t    mu     step   sigma     IR    |   BT
 0  +1.808e+03  +8.185e+02  +2e+04  2e-01  3e-01  1e+00  5e+01    ---    ---    1  1  - |  -  - 
 1  +1.736e+03  +1.219e+03  +8e+03  1e-01  1e-01  7e+00  3e+01  0.5884  2e-01   1  1  1 |  0  0
 2  +1.596e+03  +1.437e+03  +3e+03  3e-02  4e-02  6e+00  1e+01  0.8010  2e-01   1  1  1 |  0  0
 3  +1.293e+03  +1.005e+03  +3e+03  6e-02  8e-02  2e+01  9e+00  0.2964  6e-01   1  1  1 |  0  0
 4  +1.243e+03  +1.100e+03  +1e+03  3e-02  4e-02  1e+01  4e+00  0.5997  1e-01   1  1  1 |  0  0
 5  +1.329e+03  +1.216e+03  +1e+03  2e-02  3e-02  8e+00  4e+00  0.4499  7e-01   1  1  1 |  0  0
 6  +1.373e+03  +1.332e+03  +4e+02  9e-03  1e-02  3e+00  1e+00  0.6741  4e-03   1  1  1 |  0  0
 7  +1.398e+03  +1.378e+03  +2e+02  5e-03  5e-03  2e+00  6e-01  0.7476  3e-01   1  1  1 |  0  0
 8  +1.397e+03  +1.390e+03  +7e+01  2e-03  2e-03  5e-01  2e-01  0.6799  9e-02   1  1  1 |  0  0
 9  +1.400e+03  +1.397e+03  +4e+01  8e-04  9e-04  2e-01  1e-01  0.5746  2e-01   1  1  1 |  0  0
10  +1.400e+03  +1.397e+03  +4e+01  7e-04  9e-04  2e-01  1e-01  0.1143  6e-01   1  1  1 |  0  0
11  +1.398e+03  +1.396e+03  +2e+01  3e-04  4e-04  1e-01  5e-02  0.8303  3e-01   1  1  1 |  0  0
12  +1.398e+03  +1.397e+03  +5e+00  1e-04  1e-04  4e-02  2e-02  0.8814  3e-01   1  1  1 |  0  0
13  +1.397e+03  +1.397e+03  +1e-01  3e-06  3e-06  1e-03  4e-04  0.9774  4e-03   1  1  1 |  0  0
14  +1.397e+03  +1.397e+03  +2e-03  3e-08  4e-08  1e-05  5e-06  0.9890  1e-04   1  1  1 |  0  0
15  +1.397e+03  +1.397e+03  +2e-05  3e-10  4e-10  1e-07  5e-08  0.9890  1e-04   1  1  1 |  0  0
16  +1.397e+03  +1.397e+03  +2e-07  4e-12  5e-12  1e-09  6e-10  0.9890  1e-04   1  0  0 |  0  0

OPTIMAL (within feastol=4.6e-12, reltol=1.4e-10, abstol=2.0e-07).
Runtime: 0.013042 seconds.

Out[14]:
1397.0487147820581
In [15]:
prob2.status
Out[15]:
'optimal'
In [16]:
x.value
Out[16]:
array([ 6.16117845e-12,  2.36008897e-01,  1.23342457e-11,  2.61398894e-12,
        1.19737829e-12,  8.57558589e-12,  5.07316521e-12,  3.34377195e-12,
        2.22466103e-12,  5.39549310e-12,  2.36453544e-12,  6.80724195e-12,
        4.09753446e-12,  6.24063698e-12,  3.21615511e-12,  9.23998511e-12,
        5.61732485e-12,  9.78024891e-13,  1.13548106e-12,  2.84695130e-12,
        3.58490781e-12,  7.66824862e-13,  9.44620369e-13,  1.23443315e-11,
       -3.08042357e-12, -2.44788719e-12, -1.97079899e-12,  1.68292412e-11,
       -2.78972580e-12, -3.28601264e-12, -2.76110842e-12, -2.28510982e-12,
       -2.39066464e-12, -2.32575630e-12,  2.23397346e-11,  8.52785222e-13,
       -3.73604475e-13, -5.60964726e-13,  4.42255061e-12,  3.07328765e-12,
       -3.17290065e-13,  5.12209773e-12,  7.67096922e-12,  3.69308368e+00,
       -2.16115030e-12, -2.26698406e-12, -2.09346141e-12,  2.86086311e-12,
        9.88093255e-13, -2.88492900e-12, -2.27386436e-12, -1.01962011e-12,
        3.20976010e+00,  3.20976010e+00,  3.20976010e+00,  1.26023122e-10,
        2.38440960e-11,  1.21931928e-11,  3.20976010e+00,  1.58348534e+00,
        1.24456183e+00,  1.46213427e+00,  1.76702209e+00,  2.25730697e-10,
        5.18715771e-11,  7.04098543e-11,  1.08489477e-10,  9.94889882e-12,
        3.78273761e-12,  1.09287991e-12, -2.47438080e-12, -1.64378167e-12,
       -7.62665371e-13,  3.09360337e+01,  4.99223167e-01, -3.34094672e-12,
       -3.14299712e-12,  5.48535119e-12,  1.24818967e+00,  3.40958813e-12,
       -3.17172306e-12, -3.31470730e-12, -3.12688367e-12, -2.94223562e-12,
       -2.98109971e-12, -2.96570312e-12, -2.84392558e-12, -3.09340034e-12,
       -3.05530883e-12, -3.01865850e-12, -2.60468197e-12, -2.63870263e-12,
       -2.54099929e-12,  7.38492958e-12,  1.21026941e-11,  7.47423651e-12,
        1.86086156e-11,  2.29388284e-11,  1.53428972e+00,  1.30787775e-11,
       -2.78972580e-12, -3.15509551e-12, -2.76110842e-12,  7.41277280e-12,
        1.05149451e-12,  1.98434111e-12,  4.06932771e-12,  8.10723777e-12,
        2.95547398e-11,  5.25857948e-12,  7.94005768e-12, -2.82541333e-12,
       -1.74873621e-12, -1.87461950e-12, -7.29080578e-13, -5.63334704e-13,
       -4.08347474e-13,  7.73905666e-13,  2.24530974e-13,  1.92720446e-10,
       -2.44203284e-12,  1.81956590e-11,  3.13811902e-12, -2.33762661e-12,
       -2.39026363e-12, -2.10153578e-12, -3.38853608e-12, -2.23590416e-12,
       -1.41946134e-12, -2.90592156e-12, -1.88748759e-12, -7.43514188e-13,
       -3.06107375e-12, -2.23590416e-12, -1.57499464e-12, -3.32608064e-12,
       -2.53799824e-12, -2.12037791e-12,  8.83549307e-13,  2.82058548e-12,
        6.30941164e-12, -1.92553632e-12, -1.34864002e-12, -1.45837785e-12,
       -7.37995517e-13, -2.20841898e-13,  2.90532986e-14, -1.54822085e-12,
       -1.57165278e-12, -9.46721275e-13,  2.12050661e+00,  1.58348534e+00,
        1.76702209e+00,  1.76702209e+00,  9.92161035e-11,  1.29875276e-11,
        2.32083249e-11,  6.78768684e-14, -4.18483099e-13, -5.88745834e-13,
        7.20017270e-13, -1.04299335e-12, -1.54405424e-12, -5.78534604e-13,
        2.06753046e-11, -3.89417699e-12, -3.85225573e-12, -3.34320328e-12,
       -1.13768519e-12, -1.06851264e-12, -5.31535695e-13,  1.41326251e-11,
        1.69482812e-11, -2.82347639e-12, -2.88761587e-12, -1.50879759e-12,
       -1.91006302e-12, -2.50086979e-12,  6.50124351e-12,  1.24956788e-12,
        1.69843299e-13,  2.91451355e-12,  1.00511808e-12,  1.02165928e-11,
       -9.51236100e-14,  1.10500952e-12,  2.38454223e-12, -1.92897446e-12,
       -1.84634730e-12, -1.29453848e-12, -8.24384250e-13, -8.13343322e-13,
        7.84355039e-13,  3.22429737e-11,  6.99316903e-11,  2.94864328e-11,
        1.22184730e-11,  1.10328082e-11, -1.75235858e-12, -2.10385855e-12,
       -1.87878897e-12, -1.48876547e-12, -1.74554855e-12, -6.78961383e-13,
       -1.59274261e-12, -9.85634500e-13, -1.48304601e-12, -1.75235858e-12,
       -2.10385855e-12, -1.88019946e-12,  2.35143578e-12,  2.06577132e-12,
        3.51179582e-12,  6.88341602e-13,  5.82842982e-13,  1.13465822e-12,
        3.40291600e-11,  1.03251125e-11,  1.00318333e-12,  2.45662133e-12,
        6.49558404e-12,  2.25302611e-11,  3.49419755e-12, -1.05482808e-13,
        3.45719026e-13,  5.98598067e-12,  1.56962102e-12,  2.49045463e-12,
        1.36320732e-11,  2.65808426e-12,  4.00041862e-12,  2.07352121e-12,
        3.67904259e-12,  3.19977575e-12,  5.93200470e-12,  4.80332377e-12,
        1.12937293e-11,  1.91002624e-12,  3.39589903e-12,  4.91230163e-12,
        3.11674939e-13,  1.00510192e-12,  7.36607768e-12,  7.26815555e-12,
        1.98941910e-09,  9.34357615e-12,  5.19198447e-12,  8.14805553e-12,
        3.09360337e+01,  5.78820839e-13,  7.15052312e-01,  3.50352438e-12,
        1.55302330e-12,  5.57352764e-12,  7.38486067e-12,  6.75602257e-12,
        1.08970082e-11,  2.85565960e-12,  4.25809695e-12,  2.44551606e-01,
        3.50684187e-12,  5.80119535e-12,  9.65076716e-12,  3.26152002e-12,
        1.54723575e+00,  4.53966292e-12, -3.60870951e-12, -2.98190711e-12,
       -4.49559738e-13, -2.08472276e-12, -3.01937725e-12,  4.01627088e-12,
        5.63402073e-12,  5.84311470e-12,  6.01089752e-11, -2.88743669e-13,
        1.86829930e-12,  7.55638585e-13, -2.98000732e-12, -2.35818477e-12,
       -1.29360567e-12,  3.61104412e-12,  1.42229007e-11,  3.11873769e-11,
       -2.42912786e-12, -1.23332836e-12, -1.71345665e-12, -3.61728142e-12,
       -3.42359662e-12, -3.20495823e-12,  1.87401986e-11, -3.41293093e-12,
        6.59933080e-11,  1.78138941e-11, -4.78883373e-13, -3.13953203e-12,
       -2.70424193e-12, -2.46903488e-12,  1.95902668e-11,  5.49513434e-02,
       -3.59583583e-12, -3.43476507e-12, -3.23316110e-12, -1.79923506e-13,
        4.64769621e-11])

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

In [17]:
base = nutr.drop(columns=["Cal"]).T
base.columns = ["1*b"]
In [18]:
base["computed"] = np.dot(A,x.value)
In [19]:
base["0.8*b"] = 0.8*b
In [20]:
base
Out[20]:
1*b computed 0.8*b
CalFat 600 480.000000 480.0
Fat 65 54.081051 52.0
SatFat 20 20.000000 16.0
Chol 300 240.000000 240.0
Sodium 2400 2200.662407 1920.0
Carbo 300 244.665407 240.0
Protein 50 50.000000 40.0
VitA 100 100.000000 80.0
VitC 100 80.000000 80.0
Calcium 100 80.000000 80.0
Iron 100 80.000000 80.0

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

In [21]:
xopt = x.value
In [22]:
np.dot(cal ,xopt)
Out[22]:
1397.0487147820577
In [23]:
for j in range(n):
    if xopt[j]>0.3:
        print("{} \t ({} cal) \t : \t {}".format(foods.iloc[j,0],foods.iloc[j,1],xopt[j]))
Chocolate_Chip_Cookie 1_cookie_(33_g)                      	 (160 cal) 	 : 	 3.6930836797788604
Coffee_(Large) 16_fl_oz_cup                                	 (0 cal) 	 : 	 3.2097600967356694
Coffee_(Medium) 16_fl_oz_cup                               	 (0 cal) 	 : 	 3.2097600967356694
Coffee_(Small) 12_fl_oz_cup                                	 (0 cal) 	 : 	 3.2097600967356694
Dasani_Water 16.9_fl_oz                                    	 (0 cal) 	 : 	 3.2097600967356694
Diet_Coke_(Child) 12_fl_oz_cup                             	 (0 cal) 	 : 	 1.5834853369668858
Diet_Coke_(Large) 30_fl_oz_cup                             	 (0 cal) 	 : 	 1.2445618254171356
Diet_Coke_(Medium) 21_fl_oz_cup                            	 (0 cal) 	 : 	 1.4621342658462242
Diet_Coke_(Small) 16_fl_oz_cup                             	 (0 cal) 	 : 	 1.7670220855252274
EQUAL_0_Calorie_Sweetener 1_pkg_(1.0_g)                    	 (0 cal) 	 : 	 30.936033669720565
Egg_McMuffin 4.8_oz_(135_g)                                	 (290 cal) 	 : 	 0.4992231668407163
Fat_Free_Chocolate_Milk_Jug 1_carton_(236_ml)              	 (130 cal) 	 : 	 1.248189670295582
Hamburger 3.5_oz_(100_g)                                   	 (250 cal) 	 : 	 1.5342897229643404
Iced_Tea_(Child) 12_fl_oz_cup                              	 (0 cal) 	 : 	 2.1205066117421785
Iced_Tea_(Large) 30_fl_oz_cup                              	 (0 cal) 	 : 	 1.5834853369668858
Iced_Tea_(Medium) 21_fl_oz                                 	 (0 cal) 	 : 	 1.7670220855252274
Iced_Tea_(Small) 16_fl_oz_cup                              	 (0 cal) 	 : 	 1.7670220855252274
SPLENDA_No_Calorie_Sweetener 1_pkg_(1.0_g)                 	 (0 cal) 	 : 	 30.936033669720565
Salt_Packet 1_pkg_(0.7_g)                                  	 (0 cal) 	 : 	 0.7150523116396528
Side_Salad 3.1_oz_(87_g)                                   	 (20 cal) 	 : 	 1.5472357496715023

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 [24]:
contrainte3a = x[73] == 0
contrainte3b = x[248] == 0
In [25]:
prob3= cp.Problem(diet1 , constraints = [contrainte1, contrainte2a,contrainte2b, contrainte3a, contrainte3b])
prob3.solve(verbose=True,solver="ECOS")
ECOS 2.0.7 - (C) embotech GmbH, Zurich Switzerland, 2012-15. Web: www.embotech.com/ECOS

It     pcost       dcost      gap   pres   dres    k/t    mu     step   sigma     IR    |   BT
 0  +1.808e+03  +8.182e+02  +2e+04  2e-01  3e-01  1e+00  5e+01    ---    ---    1  1  - |  -  - 
 1  +1.746e+03  +1.231e+03  +8e+03  1e-01  1e-01  7e+00  3e+01  0.5836  2e-01   1  1  1 |  0  0
 2  +1.620e+03  +1.463e+03  +3e+03  3e-02  4e-02  5e+00  1e+01  0.7975  3e-01   1  1  1 |  0  0
 3  +1.605e+03  +1.557e+03  +1e+03  1e-02  1e-02  3e+00  4e+00  0.8698  3e-01   1  1  1 |  0  0
 4  +1.595e+03  +1.578e+03  +4e+02  3e-03  4e-03  8e-01  1e+00  0.8209  2e-01   1  1  1 |  0  0
 5  +1.589e+03  +1.583e+03  +2e+02  1e-03  2e-03  3e-01  5e-01  0.6595  8e-02   1  1  1 |  0  0
 6  +1.586e+03  +1.584e+03  +7e+01  5e-04  7e-04  1e-01  2e-01  0.6479  1e-01   1  1  1 |  0  0
 7  +1.585e+03  +1.585e+03  +3e+01  2e-04  3e-04  4e-02  8e-02  0.7791  2e-01   1  1  1 |  0  0
 8  +1.585e+03  +1.585e+03  +2e+00  2e-05  2e-05  3e-03  7e-03  0.9606  5e-02   1  1  1 |  0  0
 9  +1.585e+03  +1.585e+03  +7e-01  5e-06  7e-06  9e-04  2e-03  0.7543  1e-01   1  1  1 |  0  0
10  +1.585e+03  +1.585e+03  +1e-02  7e-08  1e-07  1e-05  3e-05  0.9890  3e-03   1  1  1 |  0  0
11  +1.585e+03  +1.585e+03  +1e-04  8e-10  1e-09  1e-07  4e-07  0.9890  1e-04   1  1  1 |  0  0
12  +1.585e+03  +1.585e+03  +1e-06  9e-12  1e-11  1e-09  4e-09  0.9890  1e-04   1  0  0 |  0  0

OPTIMAL (within feastol=1.2e-11, reltol=8.2e-10, abstol=1.3e-06).
Runtime: 0.014980 seconds.

Out[25]:
1584.5315377055053
In [26]:
prob2.value
Out[26]:
1397.0487147820581
In [27]:
x.value[73]
Out[27]:
1.0655888912818066e-13
In [28]:
foods.iloc[73,0]
Out[28]:
'EQUAL_0_Calorie_Sweetener 1_pkg_(1.0_g)                   '

Contrainte suivante

In [29]:
contrainte4a = cp.sum(x) <= 10
contrainte4b = x <= 2.0
In [30]:
prob4= cp.Problem(diet1 , constraints = [contrainte1, contrainte2a,contrainte2b, contrainte3a, contrainte3b, contrainte4a, contrainte4b])
prob4.solve(verbose=True,solver="ECOS")
ECOS 2.0.7 - (C) embotech GmbH, Zurich Switzerland, 2012-15. Web: www.embotech.com/ECOS

It     pcost       dcost      gap   pres   dres    k/t    mu     step   sigma     IR    |   BT
 0  +1.832e+03  -8.810e+04  +1e+05  2e-01  7e-02  1e+00  2e+02    ---    ---    1  1  - |  -  - 
 1  +1.647e+03  -1.282e+04  +3e+04  3e-02  1e-02  2e+01  4e+01  0.8943  1e-01   1  1  1 |  0  0
 2  +1.648e+03  -4.603e+03  +1e+04  1e-02  5e-03  9e+00  2e+01  0.6298  1e-01   0  0  0 |  0  0
 3  +1.639e+03  -2.981e+02  +4e+03  3e-03  2e-03  4e+00  6e+00  0.8822  2e-01   0  0  0 |  0  0
 4  +1.630e+03  +9.231e+02  +1e+03  1e-03  6e-04  1e+00  2e+00  0.6739  8e-02   0  0  0 |  0  0
 5  +1.626e+03  +1.364e+03  +6e+02  4e-04  2e-04  5e-01  9e-01  0.6477  7e-02   1  0  1 |  0  0
 6  +1.623e+03  +1.560e+03  +2e+02  1e-04  7e-05  1e-01  2e-01  0.9890  3e-01   1  0  1 |  0  0
 7  +1.614e+03  +1.551e+03  +1e+02  1e-04  6e-05  1e-01  2e-01  0.2259  8e-01   1  1  1 |  0  0
 8  +1.611e+03  +1.571e+03  +9e+01  6e-05  4e-05  8e-02  1e-01  0.3810  9e-02   1  1  1 |  0  0
 9  +1.612e+03  +1.586e+03  +6e+01  4e-05  3e-05  5e-02  1e-01  0.9890  7e-01   1  1  1 |  0  0
10  +1.608e+03  +1.597e+03  +3e+01  2e-05  1e-05  2e-02  4e-02  0.6728  2e-01   1  1  1 |  0  0
11  +1.608e+03  +1.598e+03  +2e+01  1e-05  9e-06  2e-02  3e-02  0.3824  5e-01   1  1  1 |  0  0
12  +1.605e+03  +1.604e+03  +4e+00  2e-06  2e-06  3e-03  6e-03  0.9076  8e-02   1  1  1 |  0  0
13  +1.605e+03  +1.605e+03  +7e-02  5e-08  3e-08  5e-05  1e-04  0.9864  6e-03   1  1  0 |  0  0
14  +1.605e+03  +1.605e+03  +8e-04  5e-10  3e-10  6e-07  1e-06  0.9890  1e-04   1  0  0 |  0  0
15  +1.605e+03  +1.605e+03  +9e-06  6e-12  4e-12  7e-09  1e-08  0.9890  1e-04   1  0  0 |  0  0

OPTIMAL (within feastol=5.9e-12, reltol=5.6e-09, abstol=9.0e-06).
Runtime: 0.017991 seconds.

Out[30]:
1604.75223401161
In [31]:
np.sum(x.value)
Out[31]:
9.798971105793418

Contrainte suivante

In [32]:
dej = np.zeros(n)
dej[3:23] = 1.0
In [33]:
contrainte5 = dej*x >=1.0
In [34]:
prob4= cp.Problem(diet1 , constraints = [contrainte1, contrainte2a,contrainte2b, contrainte3a, contrainte3b, contrainte4a, contrainte4b, contrainte5])
prob4.solve(verbose=True,solver="ECOS")
ECOS 2.0.7 - (C) embotech GmbH, Zurich Switzerland, 2012-15. Web: www.embotech.com/ECOS

It     pcost       dcost      gap   pres   dres    k/t    mu     step   sigma     IR    |   BT
 0  +1.832e+03  -8.800e+04  +1e+05  2e-01  7e-02  1e+00  2e+02    ---    ---    1  1  - |  -  - 
 1  +1.649e+03  -1.372e+04  +3e+04  3e-02  1e-02  2e+01  5e+01  0.8864  1e-01   1  1  1 |  0  0
 2  +1.651e+03  -4.821e+03  +1e+04  1e-02  6e-03  9e+00  2e+01  0.6348  1e-01   0  0  0 |  0  0
 3  +1.642e+03  -5.917e+02  +4e+03  4e-03  2e-03  4e+00  7e+00  0.8023  2e-01   0  0  0 |  0  0
 4  +1.637e+03  +8.524e+02  +2e+03  1e-03  6e-04  2e+00  2e+00  0.7060  8e-02   0  0  0 |  0  0
 5  +1.634e+03  +1.331e+03  +6e+02  6e-04  2e-04  7e-01  9e-01  0.7119  1e-01   1  0  0 |  0  0
 6  +1.633e+03  +1.509e+03  +2e+02  2e-04  8e-05  3e-01  3e-01  0.6770  9e-02   1  0  0 |  0  0
 7  +1.633e+03  +1.580e+03  +8e+01  1e-04  3e-05  2e-01  1e-01  0.6623  5e-02   1  1  1 |  0  0
 8  +1.635e+03  +1.590e+03  +6e+01  1e-04  2e-05  1e-01  9e-02  0.3271  1e-01   1  1  1 |  0  0
 9  +1.647e+03  +1.613e+03  +5e+01  7e-05  2e-05  9e-02  8e-02  0.5772  8e-01   1  1  1 |  0  0
10  +1.650e+03  +1.640e+03  +1e+01  2e-05  5e-06  3e-02  2e-02  0.7609  1e-02   1  1  1 |  0  0
11  +1.651e+03  +1.651e+03  +1e+00  2e-06  5e-07  3e-03  2e-03  0.9255  3e-02   1  1  1 |  0  0
12  +1.652e+03  +1.652e+03  +1e-02  2e-08  5e-09  3e-05  2e-05  0.9890  1e-04   1  1  1 |  0  0
13  +1.652e+03  +1.652e+03  +2e-04  3e-10  6e-11  4e-07  2e-07  0.9890  1e-04   1  1  1 |  0  0
14  +1.652e+03  +1.652e+03  +2e-06  3e-12  7e-13  4e-09  3e-09  0.9890  1e-04   1  0  0 |  0  0

OPTIMAL (within feastol=3.0e-12, reltol=1.0e-09, abstol=1.7e-06).
Runtime: 0.024079 seconds.

Out[34]:
1651.6421331297972
In [35]:
xoptNew = x.value
In [36]:
for j in range(n):
    if xoptNew[j]>0.3:
        print("{} \t ({} cal) \t : \t {}".format(foods.iloc[j,0],foods.iloc[j,1],xoptNew[j]))
Baked_Hot_Apple_Pie 2.7_oz_(77_g)                          	 (250 cal) 	 : 	 0.9999999996684426
Chocolate_Chip_Cookie 1_cookie_(33_g)                      	 (160 cal) 	 : 	 1.0043893797538237
Coffee_(Large) 16_fl_oz_cup                                	 (0 cal) 	 : 	 0.3690274816713538
Coffee_(Medium) 16_fl_oz_cup                               	 (0 cal) 	 : 	 0.3690274816713538
Coffee_(Small) 12_fl_oz_cup                                	 (0 cal) 	 : 	 0.3690274816713538
Dasani_Water 16.9_fl_oz                                    	 (0 cal) 	 : 	 0.3690274816713538
Egg_McMuffin 4.8_oz_(135_g)                                	 (290 cal) 	 : 	 0.6330076555099001
Fat_Free_Chocolate_Milk_Jug 1_carton_(236_ml)              	 (130 cal) 	 : 	 0.6634884734114962
Hamburger 3.5_oz_(100_g)                                   	 (250 cal) 	 : 	 1.00654879227808
Hotcakes 5.3_oz_(151_g)                                    	 (350 cal) 	 : 	 1.7882217466289692
Side_Salad 3.1_oz_(87_g)                                   	 (20 cal) 	 : 	 1.7458167764864465

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 [37]:
y  = cp.Variable(n) 


efficace = cp.Minimize( np.ones(n) *  y)
In [38]:
contrainte = A*y >= b
In [39]:
problemEff = cp.Problem(efficace , constraints = [contrainte, y>=0])
problemEff.solve(verbose=True,solver="ECOS")
ECOS 2.0.7 - (C) embotech GmbH, Zurich Switzerland, 2012-15. Web: www.embotech.com/ECOS

It     pcost       dcost      gap   pres   dres    k/t    mu     step   sigma     IR    |   BT
 0  +5.441e+00  +2.937e+02  +1e+03  3e-01  3e+00  1e+00  4e+00    ---    ---    1  1  - |  -  - 
 1  +1.631e+01  +1.518e+02  +6e+02  2e-01  2e+00  3e+00  2e+00  0.6946  2e-01   1  1  1 |  0  0
 2  +1.260e+01  +1.164e+02  +5e+02  1e-01  1e+00  2e+00  2e+00  0.2432  6e-01   1  1  1 |  0  0
 3  +1.007e+01  +6.130e+01  +3e+02  5e-02  7e-01  1e+00  1e+00  0.4805  2e-01   1  1  1 |  0  0
 4  +7.483e+00  +2.498e+01  +2e+02  1e-02  3e-01  4e-01  5e-01  0.7136  3e-01   1  1  1 |  0  0
 5  +6.284e+00  +1.795e+01  +1e+02  7e-03  2e-01  3e-01  4e-01  0.4344  6e-01   1  1  1 |  0  0
 6  +5.663e+00  +1.067e+01  +7e+01  2e-03  8e-02  1e-01  2e-01  0.5264  1e-01   1  1  1 |  0  0
 7  +5.148e+00  +9.870e+00  +6e+01  2e-03  8e-02  8e-02  2e-01  0.4406  7e-01   1  1  1 |  0  0
 8  +4.206e+00  +5.930e+00  +2e+01  7e-04  3e-02  3e-02  7e-02  0.7410  1e-01   1  1  1 |  0  0
 9  +4.117e+00  +5.236e+00  +1e+01  4e-04  2e-02  9e-03  4e-02  0.8922  6e-01   1  1  1 |  0  0
10  +3.825e+00  +4.540e+00  +9e+00  3e-04  1e-02  5e-03  3e-02  0.4825  2e-01   1  1  1 |  0  0
11  +3.799e+00  +4.490e+00  +9e+00  3e-04  1e-02  5e-03  3e-02  0.0238  9e-01   1  1  1 |  0  0
12  +3.821e+00  +4.542e+00  +9e+00  2e-04  1e-02  5e-03  3e-02  0.0295  1e+00   1  1  1 |  0  0
13  +3.396e+00  +3.635e+00  +3e+00  7e-05  5e-03  1e-03  9e-03  0.9083  3e-01   1  1  1 |  0  0
14  +3.310e+00  +3.430e+00  +1e+00  4e-05  2e-03  5e-04  5e-03  0.5919  2e-01   1  1  1 |  0  0
15  +3.302e+00  +3.408e+00  +1e+00  3e-05  2e-03  5e-04  4e-03  0.4358  7e-01   1  1  1 |  0  0
16  +3.279e+00  +3.355e+00  +9e-01  2e-05  1e-03  3e-04  3e-03  0.4267  3e-01   1  1  1 |  0  0
17  +3.276e+00  +3.353e+00  +9e-01  2e-05  2e-03  4e-04  3e-03  0.0757  9e-01   1  1  1 |  0  0
18  +3.209e+00  +3.211e+00  +2e-02  6e-07  4e-05  9e-06  7e-05  0.9766  1e-03   1  1  1 |  0  0
19  +3.207e+00  +3.207e+00  +2e-04  6e-09  4e-07  1e-07  8e-07  0.9890  1e-04   1  0  0 |  0  0
20  +3.207e+00  +3.207e+00  +3e-06  7e-11  5e-09  1e-09  9e-09  0.9890  1e-04   1  0  0 |  0  0
21  +3.207e+00  +3.207e+00  +3e-08  8e-13  5e-11  1e-11  1e-10  0.9890  1e-04   1  0  0 |  0  0

OPTIMAL (within feastol=5.1e-11, reltol=9.5e-09, abstol=3.1e-08).
Runtime: 0.018243 seconds.

Out[39]:
3.2072772481674483
In [40]:
y.value
Out[40]:
array([ 1.01308411e-11,  1.38653699e-11,  1.77436332e-11,  2.64327771e-11,
        2.01666546e-11,  2.37661363e-11,  1.73222444e-11,  1.72739313e-11,
        1.43496844e-11,  1.93688092e-11,  1.47448989e-11,  1.71543525e-11,
        1.85965890e-11,  2.23346881e-11,  9.42474984e-12,  3.19438264e-11,
        2.51104509e-11,  1.55245788e-11,  1.51211436e-11,  2.27302417e+00,
        2.48285695e-10,  4.70011255e-11,  4.53223766e-11,  3.12916714e-11,
        9.09708304e-12,  7.84412433e-12,  6.66153174e-12,  1.69001017e-11,
        2.00342723e-11,  1.19142601e-11,  1.00756505e-11,  2.25193128e-11,
        1.56088756e-11,  1.17022159e-11,  1.81523623e-11,  1.03634031e-11,
        1.24173086e-11,  2.27259417e-11,  7.95757723e-12,  9.24421194e-12,
        1.08765417e-11,  1.30584524e-11,  1.30068395e-11,  7.80087390e-12,
        2.28641760e-11,  3.75175226e-11,  7.63654203e-11,  1.69057262e-11,
        2.79288857e-12,  7.29893577e-12,  5.91183756e-12,  4.38989286e-12,
       -1.47506476e-11, -1.47506476e-11, -1.47506476e-11, -7.00578998e-13,
        5.94903943e-12,  2.21202547e-11, -1.47506476e-11, -1.80862508e-12,
        7.32116674e-13, -8.83630135e-13, -3.23243633e-12,  1.63508206e-12,
        5.26199550e-12,  4.15862687e-12,  2.75583256e-12,  2.59377029e-11,
        2.74775808e-10,  2.83335923e-12,  7.30430169e-12,  6.03747196e-12,
        4.49832673e-12, -1.47327783e-11,  1.93690216e-11,  2.24682762e-11,
        8.16052560e-11,  1.49052354e-11,  1.41573048e-11,  1.35004110e-11,
        1.60789101e-11,  1.39661426e-11,  1.17904013e-11,  1.93263353e-11,
        1.50328216e-11,  1.32522122e-11,  1.37233751e-11,  1.73618241e-11,
        1.33690273e-11,  1.17123084e-11,  2.00561397e-11,  1.27804886e-11,
        1.00417032e-11,  2.66529750e-11,  2.39646672e-11,  7.55021367e-12,
       -3.42553126e-12,  1.74484269e-11,  1.59387209e-11,  7.86126466e-12,
        2.00342723e-11,  1.19142601e-11,  1.00756505e-11,  1.34415139e-11,
        2.02705071e-01,  3.48630767e-11,  1.93408146e-11, -2.33486812e-12,
        4.70414758e-12,  1.28882616e-11,  1.28288217e-11,  1.05140955e-11,
        4.78677491e-11,  2.07648418e-11,  1.70268254e-11,  4.24023659e-11,
        2.45378761e-11,  1.79193934e-11,  1.40537264e-11,  6.62317924e-12,
        5.02393634e-12,  1.84975635e-11,  1.68671177e-11,  1.73722866e-11,
        1.17393776e-11,  1.01389475e-11,  6.30082067e-12,  4.71680477e-12,
        3.27592182e-12,  6.38312876e-12,  4.54871221e-12,  3.02731531e-12,
        6.49189764e-12,  4.71680477e-12,  3.15567286e-12,  6.69447983e-12,
        4.87218252e-12,  3.39045155e-12,  6.31545572e-12,  4.68126738e-12,
        3.23294975e-12,  2.05779097e-11,  1.37618299e-11,  1.09900448e-11,
        2.44987717e-11,  1.45664038e-11,  1.11571388e-11,  2.02793480e-11,
        1.23441482e-11,  1.02585595e-11, -6.03065541e-12, -1.80862508e-12,
       -3.23243633e-12, -3.23243633e-12,  4.35769709e-12, -4.26176311e-13,
        3.91462179e-12,  1.17592562e-11,  1.90949192e-11,  1.13471451e-11,
        9.66327183e-12,  1.98129544e-11,  1.19282748e-11,  1.01799592e-11,
        1.45544973e-11,  1.55362783e-11,  1.25568116e-11,  1.02607586e-11,
        3.56849372e-11,  2.08866730e-11,  1.52982409e-11,  1.56993408e-11,
        2.20157182e-11,  2.45792777e-11,  3.78837360e-01,  2.13937852e-11,
        3.48458537e-11,  4.78227707e-11,  1.99404679e-11,  1.00592951e-11,
        1.48332418e-11,  9.74453011e-12,  1.06604793e-11,  1.12403950e-11,
        2.66009277e-11,  1.55350453e-11,  1.23748175e-11,  2.67319486e-11,
        1.74837087e-11,  1.37422880e-11,  2.78643033e-11,  1.84705490e-11,
        1.52942057e-11,  8.11057119e-12,  7.79010033e-12,  7.87641215e-12,
        7.99635895e-12,  8.41179432e-12,  1.96737088e-11,  1.38721858e-11,
        1.03028089e-11,  2.31801317e-11,  1.56130062e-11,  1.30510074e-11,
        1.95712691e-11,  1.49759682e-11,  1.03272630e-11,  1.96737088e-11,
        1.38721858e-11,  1.02832786e-11,  1.83826077e-11,  1.31390639e-11,
        9.81211083e-12,  1.91989232e-11,  1.37530450e-11,  1.04093285e-11,
        7.57093437e-12,  2.65722064e-12,  6.70372991e-12,  5.50181025e-12,
        4.14702091e-12,  2.87035664e-13,  8.04932652e-11,  1.85432191e-10,
        1.61396851e-10,  2.21057207e-11,  3.13190544e-11,  2.23157479e-11,
        2.25838043e-11,  2.99479386e-11,  2.22162803e-11,  2.28310996e-11,
        2.26451989e-11,  2.22185856e-11,  2.26961470e-11,  2.05236612e-11,
        2.10444227e-11,  2.64158732e-11,  2.61727902e-11,  1.04524516e-10,
        1.81680552e-09,  3.52710644e-01,  4.26586366e-11,  4.38882585e-11,
        5.60022514e-10,  3.33987343e-11,  1.28011005e-11,  1.27456376e-11,
       -1.47327783e-11,  9.37679406e-12,  6.95997634e-12,  1.83550971e-11,
        1.50594802e-11,  1.49360272e-11,  1.42366878e-11,  1.82944118e-11,
        1.77504902e-11,  1.48684841e-11,  1.44707385e-11,  1.68550011e-11,
        1.27521008e-11,  1.47351596e-11,  2.11861517e-11,  1.57732112e-11,
        9.24144209e-12,  7.68832612e-12,  1.09863716e-11,  1.32082348e-11,
        1.31464579e-11,  1.33085170e-11,  1.44553543e-11,  1.53945487e-11,
        1.47104470e-11,  1.66854394e-11,  8.36103314e-12,  1.44878685e-11,
        9.01383557e-12,  2.59381794e-12,  7.14296652e-12,  5.80595420e-12,
        4.12910182e-12,  3.56370857e-11,  2.67907849e-11,  2.60350729e-11,
        1.17493395e-11,  9.74839418e-12,  7.67062377e-12,  1.59562569e-11,
        2.25437785e-11,  8.10465173e-11, -3.37495550e-12,  8.60704088e-12,
       -6.97247093e-12,  5.75126677e-12,  2.60425807e-12,  5.81070911e-12,
        5.01265132e-12,  3.99583734e-12,  7.12003924e-12,  6.60124571e-12,
        1.58320237e-11,  2.23046553e-11,  3.64678488e-11,  6.71125223e-12,
        2.44922970e-12])
In [41]:
for j in range(n):
    if y.value[j]>0.3:
        print("{} \t ({} cal) \t : \t {}".format(foods.iloc[j,0],foods.iloc[j,1],y.value[j]))
Big_Breakfast_with_Hotcakes_(Large_Size_Biscuit) 15.3_oz_(434_g) 	 (1150 cal) 	 : 	 2.273024165714703
McFlurry_with_M&M'S_Candies_(16_fl_oz_cup) 16.2_oz_(460_g) 	 (930 cal) 	 : 	 0.37883735982826483
Premium_Southwest_Salad_with_Grilled_Chicken 11.8_oz_(335_g) 	 (290 cal) 	 : 	 0.35271064428563503

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

In [42]:
for i in range(len(b)):
    print("{} \t for {}".format(A.dot(y.value)[i],b[i]))
1361.9856303910965 	 for 600
151.7047681326478 	 for 65
53.74265185722111 	 for 20
1360.0914430177845 	 for 300
5464.794252713973 	 for 2400
343.2323206211901 	 for 300
98.92880472092085 	 for 50
100.00000000302231 	 for 100
100.0000000047785 	 for 100
100.00000000542161 	 for 100
100.00000000069555 	 for 100
In [43]:
problemEff.constraints[0].dual_value
Out[43]:
array([2.41411413e-14, 2.09469785e-13, 4.06955292e-13, 3.10180270e-14,
       5.42025090e-15, 3.13134343e-12, 2.30460188e-13, 3.24226155e-03,
       2.43902439e-03, 1.09171433e-02, 1.54743433e-02])

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 [44]:
x = cp.Variable(n,integer=True) 

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

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

Relaxing Constraints

Les problemes MIP (Mixed Integer Programs) sont en général beaucoup plus dur car trouver des points admissibles est difficile, relaxons les contraintes (violemment... ex: 0<=x<=2 et Ax>=b).

In [50]:
contrainte1a = x>=0
contrainte1b = x<=2
contrainte2b = A*x >= b
In [55]:
prob2= cp.Problem(diet1 , constraints = [contrainte1a, contrainte1b, contrainte2b])
#prob2.solve(verbose=True,solver="ECOS_BB")
In [52]:
x.value
Out[52]:
array([-6.88482693e-11,  2.00000000e+00, -2.35054104e-10, -3.59336718e-10,
       -3.79989176e-10, -1.66365346e-10, -1.94783651e-10, -1.88539093e-10,
       -1.96932166e-10, -2.07835190e-10, -1.87779835e-10, -1.61535647e-10,
       -2.48036352e-10, -2.97875481e-10, -9.89586288e-10, -3.68331955e-10,
       -4.05742231e-10, -4.05341231e-10, -4.05903941e-10, -4.02548244e-10,
       -3.89741335e-10, -4.10859775e-10, -4.06919618e-10, -4.15901689e-10,
       -2.10060635e-09, -1.81274493e-09, -2.34880543e-09, -1.02008092e-10,
       -1.47834953e-09, -1.71938512e-09, -1.37161273e-09, -1.29305929e-09,
       -1.30345816e-09, -1.36828886e-09, -1.05785686e-10, -6.28083726e-10,
       -7.09420639e-10, -6.35271050e-10, -3.11918483e-10, -4.36919024e-10,
       -7.15201271e-10, -2.88163192e-10, -2.11452080e-10,  2.00000000e+00,
       -1.22950952e-09, -1.26525502e-09, -1.17555116e-09, -8.46158861e-10,
       -3.27115252e-10,  3.88111091e-10,  2.07353585e-10, -1.56617215e-10,
        1.00000000e+00,  1.00000000e+00,  1.00000000e+00,  9.99999999e-01,
        2.79224668e-09, -3.74820437e-10,  1.00000000e+00,  1.00000000e+00,
        1.00000000e+00,  1.00000000e+00,  1.00000000e+00,  2.00000000e+00,
        1.51808620e-09,  1.79317144e-09,  2.14018264e-09, -1.93817190e-10,
       -6.34383713e-10, -5.32816834e-10, -1.44322197e-10,  1.06204105e-10,
       -6.31075257e-10,  2.00000000e+00,  9.99999999e-01, -1.59117852e-09,
       -1.42142532e-09, -1.11498479e-10, -2.70924988e-10, -5.50887225e-10,
       -1.38537501e-09, -1.46781551e-09, -1.38360688e-09, -1.28285424e-09,
       -1.26729237e-09, -1.35734722e-09, -1.31994914e-09, -1.37235998e-09,
       -1.43973304e-09, -1.55828417e-09, -1.38538976e-09, -1.59812106e-09,
       -1.26564070e-09, -9.29645992e-10, -8.97455222e-10, -8.55885288e-10,
        2.89675648e-11, -1.34680568e-10, -1.13432060e-10,  2.99540631e-11,
       -1.47834953e-09, -1.52218142e-09, -1.37161273e-09,  1.58708013e-10,
       -1.41512618e-10, -1.64094907e-10, -4.63509818e-11, -1.29671842e-09,
        6.92218175e-10, -3.03591711e-10, -2.27586490e-10, -1.45430428e-09,
       -1.14846524e-09, -1.29761062e-09, -1.08590439e-09, -1.49923593e-09,
       -1.64989724e-09, -1.48060092e-09, -1.23561697e-09,  7.08130126e-10,
       -1.51757844e-09,  2.00000000e+00, -4.28425119e-10, -1.26377489e-09,
       -1.51593948e-09, -1.25910789e-09, -1.70142941e-09, -1.47373262e-09,
       -1.23396836e-09, -9.56317112e-10, -1.29985104e-09, -9.77699473e-10,
       -1.10624759e-09, -1.47373262e-09, -1.55224754e-09, -1.37802289e-09,
       -1.63407714e-09, -1.78011832e-09, -6.38837061e-10, -7.94223174e-10,
       -6.21892061e-11, -1.26987373e-09, -1.37406565e-09, -1.21762218e-09,
       -1.51149396e-09, -1.56588959e-09, -1.31723324e-09, -1.47041230e-09,
       -1.32635428e-09, -1.31246101e-09,  1.00000000e+00,  1.00000000e+00,
        1.00000000e+00,  1.00000000e+00,  2.00000000e+00,  4.21422109e-11,
       -4.48130662e-10, -1.24962457e-09, -8.55773777e-10, -8.51665622e-10,
       -5.66489265e-10, -9.22448357e-10, -1.09712245e-09, -8.16932811e-10,
       -1.94462485e-10, -2.03203493e-09, -2.25550493e-09, -2.20915190e-09,
       -1.41518059e-09, -1.27127730e-09, -1.24623353e-09, -2.26992927e-10,
       -2.40121866e-10, -1.43371196e-09, -1.37788133e-09, -1.02620707e-09,
       -1.14823952e-09, -1.13801775e-09, -3.53858274e-10, -1.17003214e-09,
       -4.64841919e-10, -2.07121108e-10, -3.62969956e-10,  2.18217087e-11,
       -7.81546358e-10, -6.68971347e-10, -6.14063085e-10, -1.31993065e-09,
       -1.35479009e-09, -1.45180654e-09, -1.62141216e-09, -1.78038184e-09,
       -1.59826291e-09,  4.45497648e-10,  7.66355887e-10,  6.67410875e-10,
        3.78210907e-10,  2.50529349e-10, -1.81425244e-09, -1.82248512e-09,
       -1.72161650e-09, -1.53115069e-09, -1.61366749e-09, -1.33312513e-09,
       -1.79176092e-09, -1.60565619e-09, -1.49232360e-09, -1.81425244e-09,
       -1.82248512e-09, -1.84255454e-09, -8.71771713e-10, -6.40675743e-10,
       -3.44214283e-10, -1.06321712e-09, -8.54980293e-10, -8.35158304e-10,
        2.00000000e+00, -1.14290384e-10, -4.22528283e-10, -6.08045172e-10,
       -1.68770302e-10,  3.67599442e-10,  4.13678760e-10, -4.09588249e-10,
       -1.76992044e-10, -4.00723293e-10, -4.51524480e-10, -3.98198705e-10,
       -3.50895761e-10, -3.93300089e-10, -3.66922085e-10, -3.89307051e-10,
       -3.08699559e-10, -3.69915329e-10, -2.90511265e-10, -3.53286414e-10,
       -2.85750780e-10, -4.12721346e-10, -3.33685327e-10,  2.00000000e+00,
       -4.86249542e-10, -3.63643738e-10, -3.38788261e-10, -4.54240881e-10,
       -3.77844997e-10, -3.21955583e-10, -2.39776609e-10, -1.44502623e-10,
        2.00000000e+00, -1.13587054e-09,  2.00000000e+00, -2.88302618e-10,
       -2.94114416e-10, -2.04003000e-10, -1.96520621e-10, -2.95405554e-10,
       -2.58375553e-10, -3.19644226e-10, -2.53579206e-10,  2.77695089e-11,
       -2.43481915e-10, -1.43176517e-10, -2.74186976e-10, -2.35956417e-10,
        2.00000000e+00, -1.10617188e-09, -1.43955376e-09, -1.47792003e-09,
       -1.02833610e-09, -1.20283840e-09, -1.35351546e-09, -2.23220626e-10,
       -1.84102375e-10, -3.27061011e-10,  6.87992330e-10, -5.93530634e-10,
       -3.53548095e-10, -5.54819151e-10, -3.22742462e-10, -6.73845795e-11,
       -6.56770406e-10, -3.84968064e-10, -1.66821937e-10, -2.10066679e-10,
       -2.26934071e-09, -1.99411236e-09, -2.31366298e-09, -1.56928568e-09,
       -1.52255256e-09, -1.49972202e-09,  2.84281025e-11, -1.74223691e-09,
        2.25630145e-09,  5.81577230e-10, -1.66658709e-09, -1.91152788e-09,
       -1.52572137e-09, -2.13055686e-09,  6.11340862e-10,  2.72112900e-09,
       -1.63491691e-09, -1.54153140e-09, -1.48496888e-09, -1.45372977e-09,
        1.41566522e-09])
In [53]:
for j in range(n):
    if x.value[j]>0.5:
        print("{} \t ({} cal) \t : \t {}".format(foods.iloc[j,0],foods.iloc[j,1],x.value[j]))
Apple_Slices 1.2_oz_(34_g)                                 	 (15 cal) 	 : 	 1.9999999988336503
Chocolate_Chip_Cookie 1_cookie_(33_g)                      	 (160 cal) 	 : 	 1.999999997183577
Coffee_(Large) 16_fl_oz_cup                                	 (0 cal) 	 : 	 1.0000000000000002
Coffee_(Medium) 16_fl_oz_cup                               	 (0 cal) 	 : 	 1.0000000000000002
Coffee_(Small) 12_fl_oz_cup                                	 (0 cal) 	 : 	 1.0000000000000002
Coffee_Cream 0.4_fl_oz_(11_ml)                             	 (20 cal) 	 : 	 0.9999999991337636
Dasani_Water 16.9_fl_oz                                    	 (0 cal) 	 : 	 1.0000000000000002
Diet_Coke_(Child) 12_fl_oz_cup                             	 (0 cal) 	 : 	 1.0000000000000604
Diet_Coke_(Large) 30_fl_oz_cup                             	 (0 cal) 	 : 	 1.0000000000000997
Diet_Coke_(Medium) 21_fl_oz_cup                            	 (0 cal) 	 : 	 1.000000000000074
Diet_Coke_(Small) 16_fl_oz_cup                             	 (0 cal) 	 : 	 1.0000000000000426
Diet_Dr_Pepper_(Child) 12_fl_oz_cup                        	 (0 cal) 	 : 	 1.9999999975740448
EQUAL_0_Calorie_Sweetener 1_pkg_(1.0_g)                    	 (0 cal) 	 : 	 1.9999999950199208
Egg_McMuffin 4.8_oz_(135_g)                                	 (290 cal) 	 : 	 0.9999999991387903
Hotcakes 5.3_oz_(151_g)                                    	 (350 cal) 	 : 	 1.999999998663135
Iced_Tea_(Child) 12_fl_oz_cup                              	 (0 cal) 	 : 	 1.000000000000015
Iced_Tea_(Large) 30_fl_oz_cup                              	 (0 cal) 	 : 	 1.0000000000000604
Iced_Tea_(Medium) 21_fl_oz                                 	 (0 cal) 	 : 	 1.0000000000000426
Iced_Tea_(Small) 16_fl_oz_cup                              	 (0 cal) 	 : 	 1.0000000000000426
Ketchup_Packet 1_pkg_(10_g)                                	 (10 cal) 	 : 	 1.9999999980355472
Oatmeal_Raisin_Cookie 1_cookie_(33_g)                      	 (150 cal) 	 : 	 1.9999999972922602
Premium_Southwest_Salad_(without_chicken) 8.1_oz_(230_g)   	 (140 cal) 	 : 	 1.9999999985891157
SPLENDA_No_Calorie_Sweetener 1_pkg_(1.0_g)                 	 (0 cal) 	 : 	 1.9999999950199208
Salt_Packet 1_pkg_(0.7_g)                                  	 (0 cal) 	 : 	 1.9999999989068975
Side_Salad 3.1_oz_(87_g)                                   	 (20 cal) 	 : 	 1.9999999980395988