notebooks/lp/Linear_Blending_Problem.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Linear Blending Problem"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Problem Statement (Jenchura, 2017)\n",
    "\n",
    "A brewery receives an order for 100 gallons of 4% ABV (alchohol by volume) beer. The brewery has on hand beer A that is 4.5% ABV that cost \\$0.32 per gallon to make, and beer B that is 3.7% ABV and cost \\$0.25 per gallon. Water could also be used as a blending agent at a cost of \\$0.05 per gallon. Find the minimum cost blend that meets the customer requirements.\n",
    "\n",
    "### Solution\n",
    "\n",
    "We will use this problem as an opportunity to write a Python function that accepts data on raw materials and customer specifications to produce the lowest cost blend.\n",
    "\n",
    "#### Representing Problem Data as a Python Dictionary\n",
    "\n",
    "The first step is to represent the problem data in a generic manner that could, if needed, be extended to include additional blending components.  Here we use a dictionary of materials, each key denoting a blending agent. For each key there is a sub-dictionary containing attributes of each blending component."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "data = {\n",
    "    'A': {'abv': 0.045, 'cost': 0.32},\n",
    "    'B': {'abv': 0.037, 'cost': 0.25},\n",
    "    'W': {'abv': 0.000, 'cost': 0.05},\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Objective Function\n",
    "\n",
    "If we let subscript $c$ denote a blending component from the set of blending components $C$, and denote the volume of $c$ used in the blend as $x_c$, the cost of the blend is\n",
    "\n",
    "\\begin{align}\n",
    "\\mbox{cost} & = \\sum_{c\\in C} x_c P_c\n",
    "\\end{align}\n",
    "\n",
    "where $P_c$ is the price per unit volume of $c$. Using the Python data dictionary defined above, the price $P_c$ is given by `data[c]['cost']`.\n",
    "\n",
    "#### Volume Constraint\n",
    "\n",
    "The customer requirement is produce a total volume $V$. Assuming ideal solutions, the constraint is given by\n",
    "\n",
    "\\begin{align}\n",
    "V &  = \\sum_{c\\in C} x_c\n",
    "\\end{align}\n",
    "\n",
    "where $x_c$ denotes the volume of component $c$ used in the blend.\n",
    "\n",
    "#### Product Composition Constraint\n",
    "\n",
    "The product composition is specified as 4% alchohol by volume. Denoting this as $\\bar{A}$, the constraint may be written as\n",
    "\n",
    "\\begin{align}\n",
    "\\bar{A} & = \\frac{\\sum_{c\\in C}x_c A_c}{\\sum_{c\\in C} x_c}\n",
    "\\end{align}\n",
    "\n",
    "where $A_c$ is the alcohol by volume for component $c$. As written, this is a nonlinear constraint. Multiplying both sides of the equation by the denominator yields a linear constraint\n",
    "\n",
    "\\begin{align}\n",
    "\\bar{A}\\sum_{c\\in C} x_c & = \\sum_{c\\in C}x_c A_c\n",
    "\\end{align}\n",
    "\n",
    "A final form for this constraint can be given in either of two versions. In the first version we subtract the left-hand side from the right to give\n",
    "\n",
    "\\begin{align}\n",
    "0 & = \\sum_{c\\in C}x_c \\left(A_c - \\bar{A}\\right) & \\mbox{ Version 1 of the linear blending constraint}\n",
    "\\end{align}\n",
    "\n",
    "Alternatively, the summation on the left-hand side corresponds to total volume. Since that is known as part of the problem specification, the blending constraint could also be written as\n",
    "\n",
    "\\begin{align}\n",
    "\\bar{A}V & = \\sum_{c\\in C}x_c A_c  & \\mbox{ Version 2 of the linear blending constraint}\n",
    "\\end{align}\n",
    "\n",
    "Which should you use? Either will generally work well. The advantage of version 1 is that it is fully specified by a product requirement $\\bar{A}$, which is sometimes helpful in writing elegant Python code.\n",
    "\n",
    "#### Pyomo Model\n",
    "\n",
    "A Pyomo implementation of this blending model is shown in the next cell. The model is contained within a Python function so that it can be more easily reused for additional calculations, or eventually for use by the process operator.\n",
    "\n",
    "Note that the pyomo library has been imported with the prefix `pyomo`. This is good programming practive to avoid namespace collisions with problem data."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Optimal Blend\n",
      "   A : 37.5 gallons\n",
      "   B : 62.5 gallons\n",
      "   W : 0.0 gallons\n",
      "\n",
      "Volume =  100.0 gallons\n",
      "Cost = $ 27.625\n"
     ]
    }
   ],
   "source": [
    "import pyomo.environ as pyomo\n",
    "\n",
    "vol = 100\n",
    "abv = 0.040\n",
    "\n",
    "def beer_blend(vol, abv, data):\n",
    "    C = data.keys()\n",
    "    model = pyomo.ConcreteModel()\n",
    "    model.x = pyomo.Var(C, domain=pyomo.NonNegativeReals)\n",
    "    model.cost = pyomo.Objective(expr = sum(model.x[c]*data[c]['cost'] for c in C))\n",
    "    model.vol = pyomo.Constraint(expr = vol == sum(model.x[c] for c in C))\n",
    "    model.abv = pyomo.Constraint(expr = 0 == sum(model.x[c]*(data[c]['abv'] - abv) for c in C))\n",
    "\n",
    "    solver = pyomo.SolverFactory('glpk')\n",
    "    solver.solve(model)\n",
    "\n",
    "    print('Optimal Blend')\n",
    "    for c in data.keys():\n",
    "        print('  ', c, ':', model.x[c](), 'gallons')\n",
    "    print()\n",
    "    print('Volume = ', model.vol(), 'gallons')\n",
    "    print('Cost = $', model.cost())\n",
    "    \n",
    "beer_blend(vol, abv, data)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "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.4"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}