{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "d367a866",
   "metadata": {},
   "source": [
    "<!--NOTEBOOK_HEADER-->\n",
    "*This notebook contains material from [CBE60499](https://ndcbe.github.io/CBE60499);\n",
    "content is available [on Github](git@github.com:ndcbe/CBE60499.git).*\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "d2c237a2",
   "metadata": {},
   "source": [
    "<!--NAVIGATION-->\n",
    "< [5.0 Special Topics](https://ndcbe.github.io/CBE60499/05.00-Special-Topics.html) | [Contents](toc.html) | [Tag Index](tag_index.html) | [5.2 MINLP Algorithms](https://ndcbe.github.io/CBE60499/05.02-MINLP-Algorithms.html) ><p><a href=\"https://colab.research.google.com/github/ndcbe/CBE60499/blob/master/docs/05.01-MILP.ipynb\"> <img align=\"left\" src=\"https://colab.research.google.com/assets/colab-badge.svg\" alt=\"Open in Colab\" title=\"Open in Google Colaboratory\"></a><p><a href=\"https://ndcbe.github.io/CBE60499/05.01-MILP.ipynb\"> <img align=\"left\" src=\"https://img.shields.io/badge/Github-Download-blue.svg\" alt=\"Download\" title=\"Download Notebook\"></a>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "nbpages": {
     "level": 1,
     "link": "[5.1 Integer Programming with Simple Branch and Bound](https://ndcbe.github.io/CBE60499/05.01-MILP.html#5.1-Integer-Programming-with-Simple-Branch-and-Bound)",
     "section": "5.1 Integer Programming with Simple Branch and Bound"
    }
   },
   "source": [
    "# 5.1 Integer Programming with Simple Branch and Bound"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "nbpages": {
     "level": 1,
     "link": "[5.1 Integer Programming with Simple Branch and Bound](https://ndcbe.github.io/CBE60499/05.01-MILP.html#5.1-Integer-Programming-with-Simple-Branch-and-Bound)",
     "section": "5.1 Integer Programming with Simple Branch and Bound"
    }
   },
   "source": [
    "$$\\begin{align*}\n",
    "\\min \\quad & Z = x + y_1 + 3 y_2 + 2 y_3 \\\\\n",
    "\\mathrm{s.t.} \\quad & -x + 3 y_1 + 2 y_2 + y_3 \\leq 0 \\\\\n",
    " & -5 y_1 - 8 y_2 - 3 y_3 \\leq -9 \\\\\n",
    " & x \\geq 0, y \\in \\{0,1\\}^3\n",
    "\\end{align*}$$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "nbpages": {
     "level": 1,
     "link": "[5.1 Integer Programming with Simple Branch and Bound](https://ndcbe.github.io/CBE60499/05.01-MILP.html#5.1-Integer-Programming-with-Simple-Branch-and-Bound)",
     "section": "5.1 Integer Programming with Simple Branch and Bound"
    }
   },
   "outputs": [],
   "source": [
    "from pyomo.environ import *\n",
    "from pyomo.opt import SolverStatus, TerminationCondition\n",
    "\n",
    "def create_relaxation():\n",
    "    \n",
    "    ## Create Pyomo Model\n",
    "    m = ConcreteModel()\n",
    "    \n",
    "    ## Declare variables (all continous for now)\n",
    "    m.x = Var(domain=NonNegativeReals)\n",
    "    m.y1 = Var(bounds=(0,1))\n",
    "    m.y2 = Var(bounds=(0,1))\n",
    "    m.y3 = Var(bounds=(0,1))\n",
    "    \n",
    "    ## Declare constraints\n",
    "    def con1_rule(m):\n",
    "        return -1.0*m.x + 3.0*m.y1 + 2.0*m.y2 + m.y3 <= 0\n",
    "    m.con1 = Constraint(rule=con1_rule)\n",
    "    \n",
    "    def con2_rule(m):\n",
    "        return -5.0*m.y1 - 8.0*m.y2 - 3.0*m.y3 <= -9\n",
    "    m.con2 = Constraint(rule=con2_rule)\n",
    "    \n",
    "    ## Declare objective\n",
    "    def obj_rule(m):\n",
    "        return m.x + m.y1 + 3*m.y2 + 2*m.y3\n",
    "    \n",
    "    m.obj = Objective(rule=obj_rule,sense=minimize)\n",
    "    \n",
    "    return m\n",
    "\n",
    "def solve_print(m,verbose=False):\n",
    "    \n",
    "    # Solve the model\n",
    "    opt = SolverFactory('cbc')\n",
    "    results = opt.solve(m, tee=verbose)\n",
    "\n",
    "    if (results.solver.status == SolverStatus.ok) and (results.solver.termination_condition == TerminationCondition.optimal):\n",
    "        # Print solution when the solution is optimal\n",
    "        print(\"x = \",value(m.x))\n",
    "        print(\"y1 = \",value(m.y1))\n",
    "        print(\"y2 = \",value(m.y2))\n",
    "        print(\"y3 = \",value(m.y3))\n",
    "        print(\"Z = \",value(m.obj))\n",
    "    \n",
    "    elif (results.solver.termination_condition == TerminationCondition.infeasible):\n",
    "        print(\"Infeasible.\")\n",
    "        \n",
    "    else:\n",
    "        # Something else is wrong\n",
    "        print('Solver Status:',result.solver.status)\n",
    "    \n",
    "    # m.pprint()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "nbpages": {
     "level": 2,
     "link": "[5.1.1 Node 1 (Root)](https://ndcbe.github.io/CBE60499/05.01-MILP.html#5.1.1-Node-1-(Root))",
     "section": "5.1.1 Node 1 (Root)"
    }
   },
   "source": [
    "## 5.1.1 Node 1 (Root)\n",
    "Full LP relaxation."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "nbpages": {
     "level": 2,
     "link": "[5.1.1 Node 1 (Root)](https://ndcbe.github.io/CBE60499/05.01-MILP.html#5.1.1-Node-1-(Root))",
     "section": "5.1.1 Node 1 (Root)"
    },
    "scrolled": true
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "x =  2.6\n",
      "y1 =  0.2\n",
      "y2 =  1.0\n",
      "y3 =  0.0\n",
      "Z =  5.800000000000001\n"
     ]
    }
   ],
   "source": [
    "m = create_relaxation()\n",
    "solve_print(m,False)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "nbpages": {
     "level": 2,
     "link": "[5.1.2 Node 2](https://ndcbe.github.io/CBE60499/05.01-MILP.html#5.1.2-Node-2)",
     "section": "5.1.2 Node 2"
    }
   },
   "source": [
    "## 5.1.2 Node 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "nbpages": {
     "level": 2,
     "link": "[5.1.2 Node 2](https://ndcbe.github.io/CBE60499/05.01-MILP.html#5.1.2-Node-2)",
     "section": "5.1.2 Node 2"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "x =  2.3333333\n",
      "y1 =  0.0\n",
      "y2 =  1.0\n",
      "y3 =  0.33333333\n",
      "Z =  5.999999959999999\n"
     ]
    }
   ],
   "source": [
    "m = create_relaxation()\n",
    "m.y1.fix(0.0)\n",
    "solve_print(m,False)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "nbpages": {
     "level": 2,
     "link": "[5.1.3 Node 3](https://ndcbe.github.io/CBE60499/05.01-MILP.html#5.1.3-Node-3)",
     "section": "5.1.3 Node 3"
    }
   },
   "source": [
    "## 5.1.3 Node 3"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {
    "nbpages": {
     "level": 2,
     "link": "[5.1.3 Node 3](https://ndcbe.github.io/CBE60499/05.01-MILP.html#5.1.3-Node-3)",
     "section": "5.1.3 Node 3"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "x =  4.0\n",
      "y1 =  1.0\n",
      "y2 =  0.5\n",
      "y3 =  0.0\n",
      "Z =  6.5\n"
     ]
    }
   ],
   "source": [
    "m = create_relaxation()\n",
    "m.y1.fix(1.0)\n",
    "solve_print(m,False)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "nbpages": {
     "level": 2,
     "link": "[5.1.4 Node 4](https://ndcbe.github.io/CBE60499/05.01-MILP.html#5.1.4-Node-4)",
     "section": "5.1.4 Node 4"
    }
   },
   "source": [
    "## 5.1.4 Node 4"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {
    "nbpages": {
     "level": 2,
     "link": "[5.1.4 Node 4](https://ndcbe.github.io/CBE60499/05.01-MILP.html#5.1.4-Node-4)",
     "section": "5.1.4 Node 4"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "WARNING: Loading a SolverResults object with a warning status into\n",
      "    model.name=\"unknown\";\n",
      "      - termination condition: infeasible\n",
      "      - message from solver: <undefined>\n",
      "Infeasible.\n"
     ]
    }
   ],
   "source": [
    "m = create_relaxation()\n",
    "m.y1.fix(0.0)\n",
    "m.y3.fix(0.0)\n",
    "solve_print(m,False)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "nbpages": {
     "level": 2,
     "link": "[5.1.5 Node 5](https://ndcbe.github.io/CBE60499/05.01-MILP.html#5.1.5-Node-5)",
     "section": "5.1.5 Node 5"
    }
   },
   "source": [
    "## 5.1.5 Node 5"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {
    "nbpages": {
     "level": 2,
     "link": "[5.1.5 Node 5](https://ndcbe.github.io/CBE60499/05.01-MILP.html#5.1.5-Node-5)",
     "section": "5.1.5 Node 5"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "x =  2.5\n",
      "y1 =  0.0\n",
      "y2 =  0.75\n",
      "y3 =  1.0\n",
      "Z =  6.75\n"
     ]
    }
   ],
   "source": [
    "m = create_relaxation()\n",
    "m.y1.fix(0.0)\n",
    "m.y3.fix(1.0)\n",
    "solve_print(m,False)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "nbpages": {
     "level": 2,
     "link": "[5.1.6 Node 6](https://ndcbe.github.io/CBE60499/05.01-MILP.html#5.1.6-Node-6)",
     "section": "5.1.6 Node 6"
    }
   },
   "source": [
    "## 5.1.6 Node 6"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {
    "nbpages": {
     "level": 2,
     "link": "[5.1.6 Node 6](https://ndcbe.github.io/CBE60499/05.01-MILP.html#5.1.6-Node-6)",
     "section": "5.1.6 Node 6"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "WARNING: Loading a SolverResults object with a warning status into\n",
      "    model.name=\"unknown\";\n",
      "      - termination condition: infeasible\n",
      "      - message from solver: <undefined>\n",
      "Infeasible.\n"
     ]
    }
   ],
   "source": [
    "m = create_relaxation()\n",
    "m.y1.fix(1.0)\n",
    "m.y2.fix(0.0)\n",
    "solve_print(m,False)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "nbpages": {
     "level": 2,
     "link": "[5.1.7 Node 7](https://ndcbe.github.io/CBE60499/05.01-MILP.html#5.1.7-Node-7)",
     "section": "5.1.7 Node 7"
    }
   },
   "source": [
    "## 5.1.7 Node 7"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {
    "nbpages": {
     "level": 2,
     "link": "[5.1.7 Node 7](https://ndcbe.github.io/CBE60499/05.01-MILP.html#5.1.7-Node-7)",
     "section": "5.1.7 Node 7"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "x =  5.0\n",
      "y1 =  1.0\n",
      "y2 =  1.0\n",
      "y3 =  0.0\n",
      "Z =  9.0\n"
     ]
    }
   ],
   "source": [
    "m = create_relaxation()\n",
    "m.y1.fix(1.0)\n",
    "m.y2.fix(1.0)\n",
    "solve_print(m,False)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "nbpages": {
     "level": 2,
     "link": "[5.1.8 Node 8](https://ndcbe.github.io/CBE60499/05.01-MILP.html#5.1.8-Node-8)",
     "section": "5.1.8 Node 8"
    }
   },
   "source": [
    "## 5.1.8 Node 8"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {
    "nbpages": {
     "level": 2,
     "link": "[5.1.8 Node 8](https://ndcbe.github.io/CBE60499/05.01-MILP.html#5.1.8-Node-8)",
     "section": "5.1.8 Node 8"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "WARNING: Loading a SolverResults object with a warning status into\n",
      "    model.name=\"unknown\";\n",
      "      - termination condition: infeasible\n",
      "      - message from solver: <undefined>\n",
      "Infeasible.\n"
     ]
    }
   ],
   "source": [
    "m = create_relaxation()\n",
    "m.y1.fix(0.0)\n",
    "m.y3.fix(1.0)\n",
    "m.y2.fix(0.0)\n",
    "solve_print(m,False)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "nbpages": {
     "level": 2,
     "link": "[5.1.9 Node 9](https://ndcbe.github.io/CBE60499/05.01-MILP.html#5.1.9-Node-9)",
     "section": "5.1.9 Node 9"
    }
   },
   "source": [
    "## 5.1.9 Node 9"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {
    "nbpages": {
     "level": 2,
     "link": "[5.1.9 Node 9](https://ndcbe.github.io/CBE60499/05.01-MILP.html#5.1.9-Node-9)",
     "section": "5.1.9 Node 9"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "x =  3.0\n",
      "y1 =  0.0\n",
      "y2 =  1.0\n",
      "y3 =  1.0\n",
      "Z =  8.0\n"
     ]
    }
   ],
   "source": [
    "m = create_relaxation()\n",
    "m.y1.fix(0.0)\n",
    "m.y3.fix(1.0)\n",
    "m.y2.fix(1.0)\n",
    "solve_print(m,False)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "9ecec3c6",
   "metadata": {},
   "source": [
    "<!--NAVIGATION-->\n",
    "< [5.0 Special Topics](https://ndcbe.github.io/CBE60499/05.00-Special-Topics.html) | [Contents](toc.html) | [Tag Index](tag_index.html) | [5.2 MINLP Algorithms](https://ndcbe.github.io/CBE60499/05.02-MINLP-Algorithms.html) ><p><a href=\"https://colab.research.google.com/github/ndcbe/CBE60499/blob/master/docs/05.01-MILP.ipynb\"> <img align=\"left\" src=\"https://colab.research.google.com/assets/colab-badge.svg\" alt=\"Open in Colab\" title=\"Open in Google Colaboratory\"></a><p><a href=\"https://ndcbe.github.io/CBE60499/05.01-MILP.ipynb\"> <img align=\"left\" src=\"https://img.shields.io/badge/Github-Download-blue.svg\" alt=\"Download\" title=\"Download Notebook\"></a>"
   ]
  }
 ],
 "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.8.6"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}