Linear Program with Python

lp.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "unlimited-windows",
   "metadata": {},
   "source": [
    "# Linear Programming With Python\n",
    "\n",
    "\n",
    "## Problem\n",
    "\n",
    "Consider the following logic puzzle:\n",
    "\n",
    "Baker, Cooper, Fletcher, Miller, and Smith live on different floors\n",
    "of an apartment house that contains only five floors. Baker does not\n",
    "live on the top floor. Cooper does not live on the bottom\n",
    "floor. Fletcher does not live on either the top or the bottom\n",
    "floor. Miller lives on a higher floor than does Cooper. Smith does\n",
    "not live on a floor adjacent to Fletcher's. Fletcher does not live on\n",
    "a floor adjacent to Cooper's. Where does everyone live? \n",
    "\n",
    "> We really don't need a linear programm per se, as we don't need to optimize something.  But this can still be used to solve a set of linear equations.\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "opponent-maine",
   "metadata": {},
   "source": [
    "Read [this article](https://realpython.com/linear-programming-python/#linear-programming-python-implementation) for an overview of the `pulp` library."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "id": "sublime-still",
   "metadata": {},
   "outputs": [],
   "source": [
    "from pulp import LpMaximize, LpProblem, LpStatus, lpSum, LpVariable\n",
    "from itertools import combinations\n",
    "from fastcore.all import *"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "id": "mobile-connecticut",
   "metadata": {},
   "outputs": [],
   "source": [
    "model = LpProblem(name=\"floors\", sense=LpMaximize)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "id": "extreme-developer",
   "metadata": {},
   "outputs": [],
   "source": [
    "# Initialize the decision variables\n",
    "b = LpVariable(name=\"Baker\", lowBound=1, upBound=5, cat=int)\n",
    "c = LpVariable(name=\"Cooper\", lowBound=1, upBound=5, cat=int)\n",
    "f = LpVariable(name=\"Fletcher\", lowBound=1, upBound=5, cat=int)\n",
    "m = LpVariable(name=\"Miller\", lowBound=1, upBound=5, cat=int)\n",
    "s = LpVariable(name=\"Smith\", lowBound=1, upBound=5, cat=int)\n",
    "\n",
    "# simple rules\n",
    "model += (5-b >= 1, \"Baker does not live on the top floor.\")\n",
    "model += (c - 1 >= 1, \"Cooper does not live on the bottom floor.\")\n",
    "model += (f - 1 >= 1, \"Fletcher does not live on the bottom floor\")\n",
    "model += (5 - f >= 1, \"Fletcher does not live on the top floor\")\n",
    "model += (m - c >=1, \"Miller lives on a higher floor than does Cooper.\")"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "alternate-excerpt",
   "metadata": {},
   "source": [
    "You have to linearize absolute values as a linear constraint.  M is a large value, and `B` is a binary variable that test either the positive or negative case of the equality.  See [this](http://lpsolve.sourceforge.net/5.1/absolute.htm) for more insight."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "id": "earlier-liability",
   "metadata": {},
   "outputs": [],
   "source": [
    "@patch\n",
    "def abs_min(self:LpProblem, var1, var2, min_amt, name, M):\n",
    "    B = LpVariable(f'_{name}', cat = \"Binary\")\n",
    "    self += (var1 - var2) + (M * B) >= min_amt\n",
    "    self += (var2 - var1) + (M * (1-B)) >= min_amt"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "bearing-prime",
   "metadata": {},
   "source": [
    "A related problem is forcing each value to be unique.  We can use the absolute value constraint to enforce this, by saying the absolute value between each combination of variables is >= 1.  Using the absolute value is discussed in this [SO Answer](https://math.stackexchange.com/a/299187)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "id": "static-wichita",
   "metadata": {},
   "outputs": [],
   "source": [
    "@patch\n",
    "def unique(self:LpProblem, choices):\n",
    "    for v1, v2 in combinations(choices, 2):\n",
    "        self.abs_min(v1,v2,min_amt=1, name=f'Unique: {v1}-{v2}', M=10)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "id": "cloudy-marijuana",
   "metadata": {},
   "outputs": [],
   "source": [
    "# every value is unique\n",
    "model.unique(choices=[b,c,f,m,s])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "id": "collective-league",
   "metadata": {},
   "outputs": [],
   "source": [
    "# These are the adjacent rules\n",
    "model.abs_min(s,f, min_amt=2, name='Fletcher and Smith not adjacent', M=10)\n",
    "model.abs_min(c,f, min_amt=2, name='Fletcher and Cooper not adjacent', M=10)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "local-violence",
   "metadata": {},
   "source": [
    "You don't need an objective function if you just want to find any point in the valid region.   \n",
    "\n",
    "Otherwise, your objective function could be added like this:\n",
    "\n",
    "```py\n",
    "model += b + c + f + m + s\n",
    "```\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "id": "horizontal-mambo",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Baker: 3.0\n",
      "Cooper: 2.0\n",
      "Fletcher: 4.0\n",
      "Miller: 5.0\n",
      "Smith: 1.0\n"
     ]
    }
   ],
   "source": [
    "status = model.solve()\n",
    "for var in model.variables():\n",
    "    if not var.name.startswith('_'): print(f\"{var.name}: {var.value()}\")"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "private-extra",
   "metadata": {},
   "source": [
    "Solution `baker=3 cooper=2 fletcher=4 miller=5 smith=1`"
   ]
  }
 ],
 "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.3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}