introduction/02-lp-pyomo.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Problem Statement\n",
    "\n",
    "*Exercise 2.12 from Operations Research: Models and Methods by Jensen & Bard*\n",
    "\n",
    "Ten jobs are to be completed by three workers during the next week. Each worker has a 40-hour work week. The times for the workers to complete the jobs are shown in the table. The values in the cells assume that each job is completed by a single worker; however, jobs can be shared, with completion times being determined proportionally If no entry exists in a particular cell, it means that the corresponding job cannot be performed by the corresponding worker. Set up and solve an LP model that will determine the optimal assignment of workers to jobs. The goal is to minimize the total time required to complete all the jobs.\n",
    "\n",
    "| Workers \\ Tasks |  1 |  2 |  3 |  4 |  5 |  6 |  7 |  8 |  9 | 10 |\n",
    "|:---------------:|---:|---:|---:|---:|---:|---:|---:|---:|---:|---:|\n",
    "| A               |  - |  7 |  3 |  - |  - | 18 | 13 |  6 |  - |  9 |\n",
    "| B               | 12 |  5 |  - | 12 |  4 | 22 |  - | 17 | 13 |  - |\n",
    "| C               | 18 |  - |  6 |  8 | 10 |  - | 19 |  - |  8 | 15 |"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Import"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "import pandas as pd\n",
    "import pyomo.environ as pe\n",
    "import pyomo.opt as po"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Define Data"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "workers = {'A', 'B', 'C'}\n",
    "\n",
    "tasks = set(range(1, 11))\n",
    "\n",
    "c = {\n",
    "    ('A',  2):  7,\n",
    "    ('A',  3):  3,\n",
    "    ('A',  6): 18,\n",
    "    ('A',  7): 13,\n",
    "    ('A',  8):  6,\n",
    "    ('A', 10):  9,\n",
    "    ('B',  1): 12,\n",
    "    ('B',  2):  5,\n",
    "    ('B',  4): 12,\n",
    "    ('B',  5):  4,\n",
    "    ('B',  6): 22,\n",
    "    ('B',  8): 17,\n",
    "    ('B',  9): 13,\n",
    "    ('C',  1): 18,\n",
    "    ('C',  3):  6,\n",
    "    ('C',  4):  8,\n",
    "    ('C',  5): 10,\n",
    "    ('C',  7): 19,\n",
    "    ('C',  9):  8,\n",
    "    ('C', 10): 15,\n",
    "}\n",
    "\n",
    "max_hours = 40"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Model\n",
    "Define $W$ as the set of workers and $T$ as the sets of tasks. Also, define $c_{wt}$ as the number of hours worker $w$ requires to complete task $t$. (Note that we do not explicitly prohibit a worker from completiting as task; rather, we make the cost arbitrarily large if worker $w$ is unable to perform task $t$.) Let $x_{wt}$ be the proportion of task $t$ that is completed by worker $j$. Let $H$ be the max number of hours that any single worker may log in a week. We formulate as follows.\n",
    "\n",
    "\n",
    "$$\n",
    "\\begin{alignat*}{3}\n",
    "\\text{minimize  }  & \\sum_{w \\in W} \\sum_{t \\in T} c_{wt} x_{wt} && \\\\\n",
    "\\text{subject to  }\n",
    "& \\sum_{t \\in T} c_{wt} x_{wt} \\le H,\n",
    "&& \\qquad \\forall w \\in W \\\\\n",
    "& \\sum_{w \\in W} x_{wt} = 1\n",
    "&& \\qquad \\forall t \\in T \\\\\n",
    "& 0 \\le x_{wt} \\le 1,\n",
    "&& \\qquad \\forall w \\in W, \\forall t \\in T\n",
    "\\end{alignat*}\n",
    "$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Implement"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "model = pe.ConcreteModel()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "model.workers = pe.Set(initialize=workers)\n",
    "model.tasks = pe.Set(initialize=tasks)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "model.c = pe.Param(model.workers, model.tasks, initialize=c, default=1000)\n",
    "model.max_hours = pe.Param(initialize=max_hours)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "model.x = pe.Var(model.workers, model.tasks, domain=pe.Reals, bounds=(0, 1))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "expr = sum(model.c[w, t] * model.x[w, t]\n",
    "           for w in model.workers for t in model.tasks)\n",
    "model.objective = pe.Objective(sense=pe.minimize, expr=expr)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "model.tasks_done = pe.ConstraintList()\n",
    "for t in model.tasks:\n",
    "    lhs = sum(model.x[w, t] for w in model.workers)\n",
    "    rhs = 1\n",
    "    model.tasks_done.add(lhs == rhs)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "model.hour_limit = pe.ConstraintList()\n",
    "for w in model.workers:\n",
    "    lhs = sum(model.c[w, t] * model.x[w, t] for t in model.tasks)\n",
    "    rhs = model.max_hours\n",
    "    model.hour_limit.add(lhs <= rhs)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Solve and Postprocess"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "solver = po.SolverFactory('gurobi')\n",
    "results = solver.solve(model, tee=True)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "df = pd.DataFrame(index=pd.MultiIndex.from_tuples(model.x, names=['w', 't']))\n",
    "df['x'] = [pe.value(model.x[key]) for key in df.index]\n",
    "df['c'] = [model.c[key] for key in df.index]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "(df['c'] * df['x']).unstack('t')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "(df['c'] * df['x']).groupby('w').sum().to_frame()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "df['x'].groupby('t').sum().to_frame().T"
   ]
  }
 ],
 "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.10"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}