{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# The Diet Problem\n",
    "\n",
    "## Summary\n",
    "\n",
    "The goal of the Diet Problem is to select foods that satisfy daily nutritional requirements at minimum cost. This problem can be formulated as a linear program, for which constraints limit the number of calories and the amount of vitamins, minerals, fats, sodium, and cholesterol in the diet. Danzig (1990) notes that the diet problem was motivated by the US Army's desire to minimize the cost of feeding GIs in the field while still providing a healthy diet.\n",
    "\n",
    "## Problem Statement\n",
    "\n",
    "The Diet Problem can be formulated mathematically as a linear programming problem using the following model.  \n",
    "\n",
    "### Sets\n",
    "\n",
    " $F$ = set of foods  \n",
    " $N$ = set of nutrients\n",
    "\n",
    "### Parameters\n",
    "\n",
    " $c_i$ = cost per serving of food $i$, $\\forall i \\in F$  \n",
    " $a_{ij}$ = amount of nutrient $j$ in food $i$, $\\forall i \\in F, \\forall j \\in N$  \n",
    " $Nmin_j$ = minimum level of nutrient $j$, $\\forall j \\in N$  \n",
    " $Nmax_j$ = maximum level of nutrient $j$, $\\forall j \\in N$  \n",
    " $V_i$ = the volume per serving of food $i$, $\\forall i \\in F$  \n",
    " $Vmax$ = maximum volume of food consumed\n",
    " \n",
    "### Variables\n",
    " $x_i$ = number of servings of food $i$ to consume\n",
    "\n",
    "### Objective\n",
    "\n",
    "Minimize the total cost of the food  \n",
    " $\\min \\sum_{i \\in F} c_i x_i$\n",
    "\n",
    "### Constraints\n",
    "\n",
    "Limit nutrient consumption for each nutrient $j \\in N$.  \n",
    " $Nmin_j \\leq \\sum_{i \\in F} a_{ij} x_i \\leq Nmax_j$, $\\forall j \\in N$\n",
    "\n",
    "Limit the volume of food consumed  \n",
    " $\\sum_{i \\in F} V_i x_i \\leq Vmax$\n",
    " \n",
    "Consumption lower bound  \n",
    " $x_i \\geq 0$, $\\forall i \\in F$\n",
    "\n",
    "## Pyomo Formulation\n",
    "\n",
    "We begin by importing the Pyomo package and creating a model object:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "from pyomo.environ import *\n",
    "infinity = float('inf')\n",
    "\n",
    "model = AbstractModel()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The sets $F$ and $N$ are declared abstractly using the `Set` component:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# Foods\n",
    "model.F = Set()\n",
    "# Nutrients\n",
    "model.N = Set()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Similarly, the model parameters are defined abstractly using the `Param` component:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Cost of each food\n",
    "model.c    = Param(model.F, within=PositiveReals)\n",
    "# Amount of nutrient in each food\n",
    "model.a    = Param(model.F, model.N, within=NonNegativeReals)\n",
    "# Lower and upper bound on each nutrient\n",
    "model.Nmin = Param(model.N, within=NonNegativeReals, default=0.0)\n",
    "model.Nmax = Param(model.N, within=NonNegativeReals, default=infinity)\n",
    "# Volume per serving of food\n",
    "model.V    = Param(model.F, within=PositiveReals)\n",
    "# Maximum volume of food consumed\n",
    "model.Vmax = Param(within=PositiveReals)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The `within` option is used in these parameter declarations to define expected properties of the parameters.  This information is used to perform error checks on the data that is used to initialize the parameter components.\n",
    "\n",
    "The `Var` component is used to define the decision variables:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# Number of servings consumed of each food\n",
    "model.x = Var(model.F, within=NonNegativeIntegers)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The `within` option is used to restrict the domain of the decision variables to the non-negative reals. This eliminates the need for explicit bound constraints for variables.\n",
    "\n",
    "The `Objective` component is used to define the cost objective.  This component uses a rule function to construct the objective expression:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# Minimize the cost of food that is consumed\n",
    "def cost_rule(model):\n",
    "    return sum(model.c[i]*model.x[i] for i in model.F)\n",
    "model.cost = Objective(rule=cost_rule)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Similarly, rule functions are used to define constraint expressions in the `Constraint` component:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# Limit nutrient consumption for each nutrient\n",
    "def nutrient_rule(model, j):\n",
    "    value = sum(model.a[i,j]*model.x[i] for i in model.F)\n",
    "    return inequality(model.Nmin[j], value, model.Nmax[j])\n",
    "model.nutrient_limit = Constraint(model.N, rule=nutrient_rule)\n",
    "\n",
    "# Limit the volume of food consumed\n",
    "def volume_rule(model):\n",
    "    return sum(model.V[i]*model.x[i] for i in model.F) <= model.Vmax\n",
    "model.volume = Constraint(rule=volume_rule)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Putting these declarations all together gives the following model:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "from pyomo.environ import *\r\n",
      "infinity = float('inf')\r\n",
      "\r\n",
      "model = AbstractModel()\r\n",
      "\r\n",
      "# Foods\r\n",
      "model.F = Set()\r\n",
      "# Nutrients\r\n",
      "model.N = Set()\r\n",
      "\r\n",
      "# Cost of each food\r\n",
      "model.c    = Param(model.F, within=PositiveReals)\r\n",
      "# Amount of nutrient in each food\r\n",
      "model.a    = Param(model.F, model.N, within=NonNegativeReals)\r\n",
      "# Lower and upper bound on each nutrient\r\n",
      "model.Nmin = Param(model.N, within=NonNegativeReals, default=0.0)\r\n",
      "model.Nmax = Param(model.N, within=NonNegativeReals, default=infinity)\r\n",
      "# Volume per serving of food\r\n",
      "model.V    = Param(model.F, within=PositiveReals)\r\n",
      "# Maximum volume of food consumed\r\n",
      "model.Vmax = Param(within=PositiveReals)\r\n",
      "\r\n",
      "# Number of servings consumed of each food\r\n",
      "model.x = Var(model.F, within=NonNegativeIntegers)\r\n",
      "\r\n",
      "# Minimize the cost of food that is consumed\r\n",
      "def cost_rule(model):\r\n",
      "    return sum(model.c[i]*model.x[i] for i in model.F)\r\n",
      "model.cost = Objective(rule=cost_rule)\r\n",
      "\r\n",
      "# Limit nutrient consumption for each nutrient\r\n",
      "def nutrient_rule(model, j):\r\n",
      "    value = sum(model.a[i,j]*model.x[i] for i in model.F)\r\n",
      "    return inequality(model.Nmin[j], value, model.Nmax[j])\r\n",
      "model.nutrient_limit = Constraint(model.N, rule=nutrient_rule)\r\n",
      "\r\n",
      "# Limit the volume of food consumed\r\n",
      "def volume_rule(model):\r\n",
      "    return sum(model.V[i]*model.x[i] for i in model.F) <= model.Vmax\r\n",
      "model.volume = Constraint(rule=volume_rule)\r\n"
     ]
    }
   ],
   "source": [
    "!cat diet.py"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Model Data\n",
    "\n",
    "Since this is an abstract Pyomo model, the set and parameter values need to be provided to initialize the model.  The following data command file provides a synthetic data set:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "param:  F:                          c     V  :=\r\n",
      "  \"Cheeseburger\"                 1.84   4.0  \r\n",
      "  \"Ham Sandwich\"                 2.19   7.5  \r\n",
      "  \"Hamburger\"                    1.84   3.5  \r\n",
      "  \"Fish Sandwich\"                1.44   5.0  \r\n",
      "  \"Chicken Sandwich\"             2.29   7.3  \r\n",
      "  \"Fries\"                         .77   2.6  \r\n",
      "  \"Sausage Biscuit\"              1.29   4.1  \r\n",
      "  \"Lowfat Milk\"                   .60   8.0 \r\n",
      "  \"Orange Juice\"                  .72  12.0 ;\r\n",
      "\r\n",
      "param Vmax := 75.0;\r\n",
      "\r\n",
      "param:  N:       Nmin   Nmax :=\r\n",
      "        Cal      2000      .\r\n",
      "        Carbo     350    375\r\n",
      "        Protein    55      .\r\n",
      "        VitA      100      .\r\n",
      "        VitC      100      .\r\n",
      "        Calc      100      .\r\n",
      "        Iron      100      . ;\r\n",
      "\r\n",
      "param a:\r\n",
      "                               Cal  Carbo Protein   VitA   VitC  Calc  Iron :=\r\n",
      "  \"Cheeseburger\"               510     34     28     15      6    30    20\r\n",
      "  \"Ham Sandwich\"               370     35     24     15     10    20    20\r\n",
      "  \"Hamburger\"                  500     42     25      6      2    25    20\r\n",
      "  \"Fish Sandwich\"              370     38     14      2      0    15    10\r\n",
      "  \"Chicken Sandwich\"           400     42     31      8     15    15     8\r\n",
      "  \"Fries\"                      220     26      3      0     15     0     2\r\n",
      "  \"Sausage Biscuit\"            345     27     15      4      0    20    15\r\n",
      "  \"Lowfat Milk\"                110     12      9     10      4    30     0\r\n",
      "  \"Orange Juice\"                80     20      1      2    120     2     2 ;\r\n"
     ]
    }
   ],
   "source": [
    "!cat diet.dat"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Set data is defined with the `set` command, and parameter data is defined with the `param` command.\n",
    "\n",
    "This data set considers the problem of designing a daily diet with only food from a fast food chain.\n",
    "\n",
    "## Solution\n",
    "\n",
    "Pyomo includes a `pyomo` command that automates the construction and optimization of models.  The GLPK solver can be used in this simple example:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[    0.00] Setting up Pyomo environment\r\n",
      "[    0.00] Applying Pyomo preprocessing actions\r\n",
      "[    0.00] Creating model\r\n",
      "[    0.02] Applying solver\r\n",
      "[    0.06] Processing results\r\n",
      "    Number of solutions: 1\r\n",
      "    Solution Information\r\n",
      "      Gap: 0.0\r\n",
      "      Status: optimal\r\n",
      "      Function Value: 15.05\r\n",
      "    Solver results file: results.json\r\n",
      "[    0.06] Applying Pyomo postprocessing actions\r\n",
      "[    0.06] Pyomo Finished\r\n"
     ]
    }
   ],
   "source": [
    "!pyomo solve --solver=glpk diet.py diet.dat"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "By default, the optimization results are stored in the file `results.yml`:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "# ==========================================================\r\n",
      "# = Solver Results                                         =\r\n",
      "# ==========================================================\r\n",
      "# ----------------------------------------------------------\r\n",
      "#   Problem Information\r\n",
      "# ----------------------------------------------------------\r\n",
      "Problem: \r\n",
      "- Name: unknown\r\n",
      "  Lower bound: 15.05\r\n",
      "  Upper bound: 15.05\r\n",
      "  Number of objectives: 1\r\n",
      "  Number of constraints: 10\r\n",
      "  Number of variables: 10\r\n",
      "  Number of nonzeros: 77\r\n",
      "  Sense: minimize\r\n",
      "# ----------------------------------------------------------\r\n",
      "#   Solver Information\r\n",
      "# ----------------------------------------------------------\r\n",
      "Solver: \r\n",
      "- Status: ok\r\n",
      "  Termination condition: optimal\r\n",
      "  Statistics: \r\n",
      "    Branch and bound: \r\n",
      "      Number of bounded subproblems: 89\r\n",
      "      Number of created subproblems: 89\r\n",
      "  Error rc: 0\r\n",
      "  Time: 0.00977396965027\r\n",
      "# ----------------------------------------------------------\r\n",
      "#   Solution Information\r\n",
      "# ----------------------------------------------------------\r\n",
      "Solution: \r\n",
      "- number of solutions: 1\r\n",
      "  number of solutions displayed: 1\r\n",
      "- Gap: 0.0\r\n",
      "  Status: optimal\r\n",
      "  Message: None\r\n",
      "  Objective:\r\n",
      "    cost:\r\n",
      "      Value: 15.05\r\n",
      "  Variable:\r\n",
      "    x[Cheeseburger]:\r\n",
      "      Value: 4\r\n",
      "    x[Fries]:\r\n",
      "      Value: 5\r\n",
      "    x[Fish Sandwich]:\r\n",
      "      Value: 1\r\n",
      "    x[Lowfat Milk]:\r\n",
      "      Value: 4\r\n",
      "  Constraint: No values\r\n"
     ]
    }
   ],
   "source": [
    "!cat results.yml"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "This solution shows that for about $15 per day, a person can get by with 4 \n",
    "cheeseburgers, 5 fries, 1 fish sandwich and 4 milks."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## References\n",
    "\n",
    "* G.B. Dantzig. The Diet Problem, Interfaces 20(4), 1990, 43-47"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.6.1"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 1
}