Diet Problem (LP)

This problem is taken from Prof. Eli Olinick’s Operations Research Models course Mathematical Programming Examples.

The goal is to choose a minimum-cost diet that satisfies the minimum recommended daily allowance (RDA), using the following data:

Nutrient / Cost	Milk (per gallon)	Cheese (per lb)	Apples (per lb)	Minimum RDA
Protein	40	20	10	80
Vitamin A	5	40	30	60
Vitamin B	20	30	40	50
Vitamin C	30	50	60	30
Cost	$1.00	$2.50	$0.75

Declare Program Elements

# !pip install gana # uncomment and run to install Gana, if not in environment
from gana import Prg, I, V, P, inf

p = Prg()
p.item = I('milk', 'cheese', 'apples', tag='food item')
p.x = V(p.item, tag='amount of food item to intake')
p.protein = P(p.item, _=[40, 20, 10])
p.vitA = P(p.item, _=[5, 40, 30])
p.vitB = P(p.item, _=[20, 30, 40])
p.vitC = P(p.item, _=[30, 50, 60])
p.cost = P(p.item, _=[1, 2.5, 3 / 4])

Declare Constraints

Non-descriptive print will use the names as provided by the user

p.cons_protein = sum(p.protein(i) * p.x(i) for i in p.item) >= 80
p.cons_protein.show()

\[\displaystyle [0]\text{ }{\mathrm{{\mathrm{{\mathrm{protein}}}}}}_{{milk}} \cdot {\mathbf{{\mathbf{{\mathbf{{\mathbf{x}}}}}}}}_{{milk}} - {\mathrm{{\mathrm{protein}}}}_{{cheese}} \cdot {\mathbf{{\mathbf{{\mathbf{x}}}}}}_{{cheese}} - {\mathrm{{\mathrm{protein}}}}_{{apples}} \cdot {\mathbf{{\mathbf{{\mathbf{x}}}}}}_{{apples}} + 80 \leq 0\]

Descriptive print will display the values

p.cons_vitA = sum(p.vitA(i) * p.x(i) for i in p.item) >= 60
p.cons_protein.show(True)

\[\displaystyle [0]\text{ }-40.0 \cdot {\mathbf{x}}_{{milk}} - 20.0 \cdot {\mathbf{x}}_{{cheese}} - 10.0 \cdot {\mathbf{x}}_{{apples}} + 80.0 \leq 0\]

p.cons_vitB = sum(p.vitB(i) * p.x(i) for i in p.item) >= 50
p.cons_vitC = sum(p.vitC(i) * p.x(i) for i in p.item) >= 30

Declare Objective

p.obj_cost = inf(sum(p.cost(i) * p.x(i) for i in p.item))

Display Program

The entire program can also be displayed descriptively and non-descriptively.

The program is always in the canonical form

p.show()

Mathematical Program for prog

Index Sets

\[\displaystyle {item} = \{ {{milk}, {cheese}, {apples}} \}\]

Objective

\[\displaystyle min \hspace{0.2cm} 1.0 \cdot {\mathbf{x}}_{{milk}} + 2.5 \cdot {\mathbf{x}}_{{cheese}} + 0.75 \cdot {\mathbf{x}}_{{apples}}\]

s.t.

Inequality Constraint Sets

\[\displaystyle [0]\text{ }{\mathrm{{\mathrm{{\mathrm{protein}}}}}}_{{milk}} \cdot {\mathbf{{\mathbf{{\mathbf{{\mathbf{x}}}}}}}}_{{milk}} - {\mathrm{{\mathrm{protein}}}}_{{cheese}} \cdot {\mathbf{{\mathbf{{\mathbf{x}}}}}}_{{cheese}} - {\mathrm{{\mathrm{protein}}}}_{{apples}} \cdot {\mathbf{{\mathbf{{\mathbf{x}}}}}}_{{apples}} + 80 \leq 0\]

\[\displaystyle [1]\text{ }{\mathrm{{\mathrm{{\mathrm{vitA}}}}}}_{{milk}} \cdot {\mathbf{{\mathbf{{\mathbf{{\mathbf{x}}}}}}}}_{{milk}} - {\mathrm{{\mathrm{vitA}}}}_{{cheese}} \cdot {\mathbf{{\mathbf{{\mathbf{x}}}}}}_{{cheese}} - {\mathrm{{\mathrm{vitA}}}}_{{apples}} \cdot {\mathbf{{\mathbf{{\mathbf{x}}}}}}_{{apples}} + 60 \leq 0\]

\[\displaystyle [2]\text{ }{\mathrm{{\mathrm{{\mathrm{vitB}}}}}}_{{milk}} \cdot {\mathbf{{\mathbf{{\mathbf{{\mathbf{x}}}}}}}}_{{milk}} - {\mathrm{{\mathrm{vitB}}}}_{{cheese}} \cdot {\mathbf{{\mathbf{{\mathbf{x}}}}}}_{{cheese}} - {\mathrm{{\mathrm{vitB}}}}_{{apples}} \cdot {\mathbf{{\mathbf{{\mathbf{x}}}}}}_{{apples}} + 50 \leq 0\]

\[\displaystyle [3]\text{ }{\mathrm{{\mathrm{{\mathrm{vitC}}}}}}_{{milk}} \cdot {\mathbf{{\mathbf{{\mathbf{{\mathbf{x}}}}}}}}_{{milk}} - {\mathrm{{\mathrm{vitC}}}}_{{cheese}} \cdot {\mathbf{{\mathbf{{\mathbf{x}}}}}}_{{cheese}} - {\mathrm{{\mathrm{vitC}}}}_{{apples}} \cdot {\mathbf{{\mathbf{{\mathbf{x}}}}}}_{{apples}} + 30 \leq 0\]

Functions

\[\displaystyle [0]\text{ }1.0 \cdot {\mathbf{x}}_{{milk}} + 2.5 \cdot {\mathbf{x}}_{{cheese}} + 0.75 \cdot {\mathbf{x}}_{{apples}}\]

p.show(True)

Mathematical Program for prog

Index Sets

\[\displaystyle {item} = \{ {{milk}, {cheese}, {apples}} \}\]

Objective

\[\displaystyle min \hspace{0.2cm} 1.0 \cdot {\mathbf{x}}_{{milk}} + 2.5 \cdot {\mathbf{x}}_{{cheese}} + 0.75 \cdot {\mathbf{x}}_{{apples}}\]

s.t.

Inequality Constraints

\[\displaystyle [0]\text{ }-40.0 \cdot {\mathbf{x}}_{{milk}} - 20.0 \cdot {\mathbf{x}}_{{cheese}} - 10.0 \cdot {\mathbf{x}}_{{apples}} + 80.0 \leq 0\]

\[\displaystyle [1]\text{ }-5.0 \cdot {\mathbf{x}}_{{milk}} - 40.0 \cdot {\mathbf{x}}_{{cheese}} - 30.0 \cdot {\mathbf{x}}_{{apples}} + 60.0 \leq 0\]

\[\displaystyle [2]\text{ }-20.0 \cdot {\mathbf{x}}_{{milk}} - 30.0 \cdot {\mathbf{x}}_{{cheese}} - 40.0 \cdot {\mathbf{x}}_{{apples}} + 50.0 \leq 0\]

\[\displaystyle [3]\text{ }-30.0 \cdot {\mathbf{x}}_{{milk}} - 50.0 \cdot {\mathbf{x}}_{{cheese}} - 60.0 \cdot {\mathbf{x}}_{{apples}} + 30.0 \leq 0\]

Exporting

The program can be exported as a .mps file

p.mps()

📝  Generated prog.mps                                                       ⏱ 0.0006 s

Solving

The solution can be obtained using state-of-the-art solvers.

Note that the program is first exported in the .mps format and then sent to the solver

p.opt(using='gurobi')

📝  Generated prog.mps                                                       ⏱ 0.0005 s

Set parameter Username
Academic license - for non-commercial use only - expires 2026-08-01
Read MPS format model from file prog.mps
Reading time = 0.00 seconds
PROG: 4 rows, 3 columns, 12 nonzeros

📝  Generated gurobipy model. See .formulation                               ⏱ 0.0062 s

Gurobi Optimizer version 12.0.3 build v12.0.3rc0 (win64 - Windows 11.0 (26100.2))

CPU model: 13th Gen Intel(R) Core(TM) i7-13700, instruction set [SSE2|AVX|AVX2]
Thread count: 16 physical cores, 24 logical processors, using up to 24 threads

Optimize a model with 4 rows, 3 columns and 12 nonzeros
Model fingerprint: 0x7c6539af
Coefficient statistics:
  Matrix range     [5e+00, 6e+01]
  Objective range  [8e-01, 3e+00]
  Bounds range     [0e+00, 0e+00]
  RHS range        [3e+01, 8e+01]
Presolve time: 0.00s
Presolved: 4 rows, 3 columns, 12 nonzeros

Iteration    Objective       Primal Inf.    Dual Inf.      Time
       0    0.0000000e+00   2.750000e+01   0.000000e+00      0s
       2    2.8695652e+00   0.000000e+00   0.000000e+00      0s

Solved in 2 iterations and 0.00 seconds (0.00 work units)
Optimal objective  2.869565217e+00

📝  Generated Solution object for prog. See .solution                        ⏱ 0.0000 s
✅  prog optimized using gurobi. Display using .output()                     ⏱ 0.0123 s

Display Solution

The values of the variables as well as the constrain slacks are denoted for inequality constraints

p.output()

Solution for prog

Objective

\[\displaystyle min \hspace{0.2cm} 1.0 \cdot {\mathbf{x}}_{{milk}} + 2.5 \cdot {\mathbf{x}}_{{cheese}} + 0.75 \cdot {\mathbf{x}}_{{apples}}=2.869565217391304\]

Variables

\[\displaystyle {\mathbf{x}}_{{milk}}=1.5652173913043477\]

\[\displaystyle {\mathbf{x}}_{{cheese}}=0.0\]

\[\displaystyle {\mathbf{x}}_{{apples}}=1.7391304347826089\]

The values attained by individual variables can also be displayed

p.x.output()

\[\displaystyle {\mathbf{x}}_{{milk}}=1.5652173913043477\]

\[\displaystyle {\mathbf{x}}_{{cheese}}=0.0\]

\[\displaystyle {\mathbf{x}}_{{apples}}=1.7391304347826089\]

even at an index

p.x(p.milk).output()

\[\displaystyle {\mathbf{x}}_{{milk}}=1.5652173913043477\]

or accessed.

I get that this is a little wierd (referring to the [0]), I will fix this.

p.x(p.milk)[0]._

[x[0]]

Matrix Form

Left Hand Side parameters

p.A

[[-40.0, -20.0, -10.0],
 [-5.0, -40.0, -30.0],
 [-20.0, -30.0, -40.0],
 [-30.0, -50.0, -60.0]]

Right Hand Side paremeters

p.B

[-80.0, -60.0, -50.0, -30.0]

Objective cost vector

p.C

[1.0, 2.5, 0.75]

LHS parameters for less than equal constraints

p.G

[[-40.0, -20.0, -10.0],
 [-5.0, -40.0, -30.0],
 [-20.0, -30.0, -40.0],
 [-30.0, -50.0, -60.0]]

LHS parameters for equality constraints. There are no equality constraints in this program

p.H

[]