{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Pyomo package in Python for optimization"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Here we illustrate the use of Pyomo for solving mathematical optimization models. There are other Python packages (such as [PuLP](https://pythonhosted.org/PuLP/)) that can be used for (integer) linear models, but here we stick to Pyomo because it can also be used to model *nonlinear* optimization models, which will be part of the next in class assignment.\n",
    "    \n",
    "Frans de Ruiter\n",
    "\n",
    "This example is taken from [here](http://pyomocontrib-simplemodel.readthedocs.io/en/latest/knapsack.html#knapsack-problem).\n",
    "\n",
    "More information about Pyomo can be found on the website: http://www.pyomo.org/documentation.\n",
    "\n",
    "---"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Installing pyomo\n",
    "\n",
    "You can install pyomo by running\n",
    "\n",
    "``pip install pyomo``\n",
    "\n",
    "or easier by using conda:\n",
    "\n",
    "``conda install -c conda-forge pyomo``.\n",
    "\n",
    "You also need the package glpk (and ipopt for the next in class assignment):\n",
    "\n",
    "``conda install -c conda-forge ipopt glpk``\n",
    "\n",
    "See the [Pyomo installation instructions](http://pyomo.readthedocs.io/en/latest/getting_started/index.html).\n",
    "\n",
    "We recommend using the coincbc solver instead of the glpk solver for the facility location problem, since it is much faster. \n",
    "On UNIX you can install the coincbc solver by: \n",
    "\n",
    "``conda install -c conda-forge coincbc``\n",
    "\n",
    "\n",
    "---"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### ! Installing CBC solver on Windows !\n",
    "\n",
    "*(instruction added 30/5/2018, see also solve command at the bottom of this file)*\n",
    "\n",
    "1. **Download and install** the coin cbc optimization solver (note this is an .exe file) via\n",
    "\n",
    "    ``https://www.coin-or.org/download/binary/OptimizationSuite/COIN-OR-1.8.0-win32-msvc12.exe``\n",
    "\n",
    "    Make sure you add cbc to your path (is done automatically via an option at the end of the installation process).\n",
    "    \n",
    "\n",
    "2. **Restart jupyter notebook** (if it was already open open) and run the rest of this script. If you run this script without restarting jupyter notebook, the script will not run because the path to the solver cannot be found.\n",
    "\n",
    "---"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Knapsack model formulation"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The Knapsack Problem considers the problem of selecting a set of items whose weight is not greater than a specified limit while maximizing the total value of the selected items. This problem is inspired by the challenge of filling a knapsack (or rucksack) with the most valuable items that can be carried.\n",
    "\n",
    "A common version of this problem is the 0-1 knapsack problem, where each item is distinct and can be selected once. Suppose there are n items with positive values v1,…,vn and weights w1,…,wn. Let x1,…,xn be decision variables that can take values 0 or 1. Let W be the weight capacity of the knapsack.\n",
    "\n",
    "The following optimization formulation represents this problem as an integer program:\n",
    "\\begin{equation*}\n",
    "\\begin{array}{ll}\n",
    "   \\max & \\sum _{i=1}^{n} v_{i} x_{i} \\\\\n",
    "   \\textrm{s.t.} & \\sum _{i=1}^{n} w_{i} x_{i}\\leq W \\\\\n",
    "                & x_{i}\\in \\{0,1\\}\n",
    "\\end{array}\n",
    "\\end{equation*}\n",
    "The following section illustrate how to model and solve this problem using the Pyomo package."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Importing packages"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "scrolled": true
   },
   "outputs": [],
   "source": [
    "import pyomo\n",
    "from pyomo.environ import *\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Input data"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "v = {'hammer':8, 'wrench':3, 'screwdriver':6, 'towel':11}\n",
    "w = {'hammer':5, 'wrench':7, 'screwdriver':4, 'towel':3}\n",
    "limit = 14\n",
    "items = list(sorted(v.keys()))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Model implementation"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Create model\n",
    "m = ConcreteModel()\n",
    "\n",
    "# Variables\n",
    "m.x = Var(items, within=Binary) # use within=NonNegativeReals for a variable that should be nonnegative and continuous\n",
    "\n",
    "# Objective\n",
    "m.value = Objective(expr=sum(v[i]*m.x[i] for i in items), sense=maximize)\n",
    "\n",
    "# Constraint\n",
    "m.weight = Constraint(expr=sum(w[i]*m.x[i] for i in items) <= limit)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "To add constraints in a loop, you can use something like the following:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [],
   "source": [
    "# m.constraintloop = ConstraintList()\n",
    "# for i in list_of_items:\n",
    "#     m.constraintloop.add(expr=sum(w[i]*m.x[i] for i in items) <= limit)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Solve and print solution"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Status = optimal\n",
      "x[hammer] = 1.000000\n",
      "x[screwdriver] = 1.000000\n",
      "x[towel] = 1.000000\n",
      "x[wrench] = 0.000000\n",
      "Objective = 25.000000\n"
     ]
    }
   ],
   "source": [
    "# Optimize\n",
    "solver = SolverFactory('cbc') # Use cbc solver\n",
    "#solver = SolverFactory('glpk') # glpk solver is not recommended\n",
    "\n",
    "# Set a time limit for 3600 seconds (1 hour). Cbc will find the optimal solutions within a minute, but glpk does not.\n",
    "solver.options['tmlim'] = 3600 \n",
    "\n",
    "status = solver.solve(m,tee=False,) # setting tee=True enables you to see the progress of the solver\n",
    "status = solver.solve(m)\n",
    "\n",
    "# Print the status of the solved LP\n",
    "print(\"Status = %s\" % status.solver.termination_condition)\n",
    "\n",
    "# Print the value of the variables at the optimum\n",
    "for i in items:\n",
    "    print(\"%s = %f\" % (m.x[i], value(m.x[i])))\n",
    "\n",
    "# Print the value of the objective\n",
    "print(\"Objective = %f\" % value(m.value))"
   ]
  },
  {
   "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.7.1"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}