milp_tutorial/milp_tutorial_RAP_problem_001.ipynb

{
 "cells": [
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Resource Assignment Problem formulation\n",
    "\n",
    "Consider three job positions: Tester, Java-Developer, and Architect.\n",
    "\n",
    "Consider three resources: Carlos, Joe, and Monika.\n",
    "\n",
    "## Data \n",
    "\n",
    "The ability to perform each of the jobs by each of the resources is illustrated by the following matching scores table:\n",
    "\n",
    "![Resource Allocation Problem Data Image](util/rap_data.png)\n",
    "\n",
    "\n",
    "**Assumption**: Only one resource can be assigned to a job, and at most one job can be assigned to a resource.\n",
    "\n",
    "## Problem statement\n",
    "\n",
    "Determine an assignment that ensures that each job is fulfilled and each resource is assigned to at most one job in order to maximize the total matching scores of the assignments.\n",
    "\n",
    "## Decision variables\n",
    "\n",
    "The decision variable $x_{r,\\; j} = 1$ represents that resource r is assigned to job j, and 0 otherwise, for  r=1,2,3 and 𝑗=1,2,3.\n",
    "\n",
    "## Constraints\n",
    "\n",
    "### Jobs constraints\n",
    "\n",
    "For each job 𝑗=1,2,3, exactly one resource from r=1,2,3 must be assigned.\n",
    "\n",
    "Constraint (Tester=1): $x_{1,\\; 1} + x_{2,\\; 1} + x_{3,\\; 1} = 1$\n",
    "\n",
    "Constraint (Java-Developer=2): $x_{1,\\; 2} + x_{2,\\; 2} + x_{3,\\; 2} = 1$\n",
    "\n",
    "Constraint (Architect=3): $x_{1,\\; 3} + x_{2,\\; 3} + x_{3,\\; 3} = 1$\n",
    "\n",
    "### Resources constraints\n",
    "\n",
    "For each resource = r=1,2,3, at most one job from r=1,2,3 can be assigned.\n",
    "\n",
    "Constraint (Carlos=1): $x_{1,\\; 1} + x_{1,\\; 2} + x_{1,\\; 3}  \\leq 1$\n",
    "\n",
    "Constraint (Joe=2): $x_{2,\\; 1} + x_{2,\\; 2} + x_{2,\\; 3}  \\leq 1$\n",
    "\n",
    "Constraint (Monika=3): $x_{2,\\; 1} + x_{2,\\; 2} + x_{2,\\; 3}  \\leq 1$\n",
    "\n",
    "## Objective function\n",
    "\n",
    "The objective function is to maximize the total matching score of the assignments while satisfying the jobs and resources constraints.\n",
    "\n",
    "$$\n",
    "Max \\; (53x_{1,\\; 1} + 80x_{2,\\; 1} + 53x_{3,\\; 1}) + (27x_{1,\\; 2} + 47x_{2,\\; 2} + 73x_{3,\\; 2})\n",
    "+ (13x_{1,\\; 3} + 67x_{2,\\; 3} + 47x_{3,\\; 3})\n",
    "$$\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "First, let's install gurobipy as needed"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%pip install gurobipy"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "# import gurobi library\n",
    "from gurobipy import *"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Data\n",
    "The list R contains the names of the three resources: Carlos, Joe, and Monika. \n",
    "\n",
    "The list J contains the names of the job positions: tester, java-developer, and architect"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [],
   "source": [
    "# resources and jobs sets\n",
    "R = ['Carlos', 'Joe', 'Monika']\n",
    "J = ['Tester', 'JavaDeveloper', 'Architect']"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "$r \\in R$ index and set of resources.\n",
    "\n",
    "$j \\in J$ index and set of Jobs."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The following “multidict” function describes the matching score associated with each possible combination of a resource and job"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [],
   "source": [
    "# matching score data\n",
    "combinations, ms = multidict({\n",
    "    ('Carlos', 'Tester'): 53,\n",
    "    ('Carlos', 'JavaDeveloper'): 27,\n",
    "    ('Carlos', 'Architect'): 13,\n",
    "    ('Joe', 'Tester'): 80,\n",
    "    ('Joe', 'JavaDeveloper'): 47,\n",
    "    ('Joe', 'Architect'): 67,\n",
    "    ('Monika', 'Tester'): 53,\n",
    "    ('Monika', 'JavaDeveloper'): 73,\n",
    "    ('Monika', 'Architect'): 47\n",
    "})"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The following function generates an empty model object “m” and takes the string “RAP” model name as its argument."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Declare and initialize model\n",
    "m = Model('RAP')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Decision variables\n",
    "\n",
    "The decision variable $x_{r,\\; j} = 1$ represents that resource r is assigned to job j, and 0 otherwise, for $r \\in R$ and $j \\in J $.\n",
    "\n",
    "The “addVars()” method defines the decision variables of the model object “m”.  "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Create decision variables for the RAP model\n",
    "x = m.addVars(combinations, name=\"assign\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Job constraints\n",
    "\n",
    "For each job 𝑗=1,2,3, exactly one resource from r=1,2,3 must be assigned.\n",
    "\n",
    "Constraint (Tester=1): $x_{1,\\; 1} + x_{2,\\; 1} + x_{3,\\; 1} = 1$\n",
    "\n",
    "Constraint (Java-Developer=2): $x_{1,\\; 2} + x_{2,\\; 2} + x_{3,\\; 2} = 1$\n",
    "\n",
    "Constraint (Architect=3): $x_{1,\\; 3} + x_{2,\\; 3} + x_{3,\\; 3} = 1$\n",
    "\n",
    "The “addConstrs()” method defines the constraints of the model object “m”. \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [],
   "source": [
    "# create jobs  constraints\n",
    "job = m.addConstrs((x.sum('*',j) == 1 for j in J), 'job')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Job constraints\n",
    "$$\n",
    "\\sum_{r \\: \\in \\: R} x_{r,\\; j} = 1 \\; \\; \\; \\forall \\; j \\in J\n",
    "$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Resource constraints\n",
    "\n",
    "For each resource = r=1,2,3, at most one job from r=1,2,3 can be assigned.\n",
    "\n",
    "Constraint (Carlos=1): $x_{1,\\; 1} + x_{1,\\; 2} + x_{1,\\; 3}  \\leq 1$\n",
    "\n",
    "Constraint (Joe=2): $x_{2,\\; 1} + x_{2,\\; 2} + x_{2,\\; 3}  \\leq 1$\n",
    "\n",
    "Constraint (Monika=3): $x_{3,\\; 1} + x_{3,\\; 2} + x_{3,\\; 3}  \\leq 1$\n",
    "\n",
    "The “addConstrs()” method defines the constraints of the model object “m”. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [],
   "source": [
    "# create resources constraints\n",
    "resource = m.addConstrs((x.sum(r,'*') <= 1 for r in R), 'resource')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Resource constraints\n",
    "$$\n",
    "\\sum_{j \\: \\in \\: J} x_{r,\\; j} \\leq 1 \\; \\; \\; \\forall \\; r \\in R\n",
    "$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Objective Function\n",
    "\n",
    "The objective function is to maximize the total matching score of the assignments.\n",
    "\n",
    "$$\n",
    "Max \\; (53x_{1,\\; 1} + 80x_{2,\\; 1} + 53x_{3,\\; 1}) + (27x_{1,\\; 2} + 47x_{2,\\; 2} + 73x_{3,\\; 2})\n",
    "+ (13x_{1,\\; 3} + 67x_{2,\\; 3} + 47x_{3,\\; 3})\n",
    "$$\n",
    "\n",
    "The “setObjective()” method defines the objective function of the model object “m”. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [],
   "source": [
    "# The objective is to maximize total matching score of the assignments\n",
    "m.setObjective(x.prod(ms), GRB.MAXIMIZE)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Objective function\n",
    "Notice that \n",
    "$$\n",
    "(53x_{1,\\; 1} + 80x_{2,\\; 1} + 53x_{3,\\; 1}) = \\sum_{r \\; \\in \\; R} ms_{r,1}x_{r,1} \\\\\n",
    "(27x_{1,\\; 2} + 47x_{2,\\; 2} + 73x_{3,\\; 2}) = \\sum_{r \\; \\in \\; R} ms_{r,2}x_{r,2} \\\\\n",
    "(13x_{1,\\; 3} + 67x_{2,\\; 3} + 47x_{3,\\; 3})  = \\sum_{r \\; \\in \\; R} ms_{r,3}x_{r,3}\n",
    "$$\n",
    "\n",
    "Hence, the objective function can be expressed as follows\n",
    "\n",
    "$$\n",
    "Max \\; \\sum_{j \\; \\in \\; J} \\sum_{r \\; \\in \\; R} ms_{r,j}x_{r,j}\n",
    "$$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [],
   "source": [
    "# save model for inspection\n",
    "m.write('RAP.lp')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {
    "scrolled": true
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Gurobi Optimizer version 10.0.0 build v10.0.0rc2 (mac64[x86])\n",
      "\n",
      "CPU model: Intel(R) Core(TM) i5-1038NG7 CPU @ 2.00GHz\n",
      "Thread count: 4 physical cores, 8 logical processors, using up to 8 threads\n",
      "\n",
      "Optimize a model with 6 rows, 9 columns and 18 nonzeros\n",
      "Model fingerprint: 0xb343b6eb\n",
      "Coefficient statistics:\n",
      "  Matrix range     [1e+00, 1e+00]\n",
      "  Objective range  [1e+01, 8e+01]\n",
      "  Bounds range     [0e+00, 0e+00]\n",
      "  RHS range        [1e+00, 1e+00]\n",
      "Presolve time: 0.01s\n",
      "Presolved: 6 rows, 9 columns, 18 nonzeros\n",
      "\n",
      "Iteration    Objective       Primal Inf.    Dual Inf.      Time\n",
      "       0    4.6000000e+32   1.800000e+31   4.600000e+02      0s\n",
      "       5    1.9300000e+02   0.000000e+00   0.000000e+00      0s\n",
      "\n",
      "Solved in 5 iterations and 0.01 seconds (0.00 work units)\n",
      "Optimal objective  1.930000000e+02\n"
     ]
    }
   ],
   "source": [
    "# run optimization engine\n",
    "m.optimize()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "assign[Carlos,Tester]: 1.0\n",
      "assign[Joe,Architect]: 1.0\n",
      "assign[Monika,JavaDeveloper]: 1.0\n",
      "Total matching score: 193.0\n"
     ]
    }
   ],
   "source": [
    "def print_solution(model):\n",
    "    for var in model.getVars():\n",
    "        if abs(var.x) > 1e-6:\n",
    "            print(\"{0}: {1}\".format(var.varName, var.x))\n",
    "    print('Total matching score: {0}'.format(model.objVal))\n",
    "    return None\n",
    "\n",
    "# display optimal values of decision variables\n",
    "print_solution(m)   \n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## New scenario\n",
    "Consider a new resource by the name of Ada that has a matching score of 100% for all the job positions.\n",
    "\n",
    "## Constraints\n",
    "\n",
    "### Jobs constraints\n",
    "\n",
    "For each job 𝑗=1,2,3, exactly one resource from r=1,2,3,4 must be assigned.\n",
    "\n",
    "Constraint (Tester=1): $x_{1,\\; 1} + x_{2,\\; 1} + x_{3,\\; 1} + x_{4,\\; 1} = 1$\n",
    "\n",
    "Constraint (Java-Developer=2): $x_{1,\\; 2} + x_{2,\\; 2} + x_{3,\\; 2} + x_{4,\\; 2} = 1$\n",
    "\n",
    "Constraint (Architect=3): $x_{1,\\; 3} + x_{2,\\; 3} + x_{3,\\; 3} + x_{4,\\; 3}= 1$\n",
    "\n",
    "### Resources constraints\n",
    "\n",
    "For each resource r=4, at most one job from r=1,2,3 can be assigned.\n",
    "\n",
    "Constraint (Ada=1): $x_{4,\\; 1} + x_{4,\\; 2} + x_{4,\\; 3}  \\leq 1$\n",
    "\n",
    "\n",
    "## Objective function\n",
    "\n",
    "The objective function is to maximize the total matching score of the assignments while satisfying the jobs and resources constraints.\n",
    "\n",
    "$$\n",
    "Max \\; (53x_{1,\\; 1} + 80x_{2,\\; 1} + 53x_{3,\\; 1} + 100x_{4, \\; 1}) \n",
    "+ (27x_{1,\\; 2} + 47x_{2,\\; 2} + 73x_{3,\\; 2} + 100x_{4, \\; 2})\n",
    "+ (13x_{1,\\; 3} + 67x_{2,\\; 3} + 47x_{3,\\; 3} + 100x_{4, \\; 3})\n",
    "$$\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "<gurobi.Constr *Awaiting Model Update*>"
      ]
     },
     "execution_count": 13,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "new_scores = {('Ada','Tester'):100, ('Ada','JavaDeveloper'):100, ('Ada','Architect'):100}\n",
    "\n",
    "for key, val in new_scores.items():\n",
    "    r, j = key\n",
    "    x[key] = m.addVar(obj=val,\n",
    "                           name='assign[{0},{1}]'.format(r,j),\n",
    "                           column=Column([1], [m.getConstrByName('job[{0}]'.format(j))]))\n",
    "m.addConstr(x.sum('Ada','*') <= 1, name=\"resources[Ada]\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Gurobi Optimizer version 10.0.0 build v10.0.0rc2 (mac64[x86])\n",
      "\n",
      "CPU model: Intel(R) Core(TM) i5-1038NG7 CPU @ 2.00GHz\n",
      "Thread count: 4 physical cores, 8 logical processors, using up to 8 threads\n",
      "\n",
      "Optimize a model with 7 rows, 12 columns and 24 nonzeros\n",
      "Coefficient statistics:\n",
      "  Matrix range     [1e+00, 1e+00]\n",
      "  Objective range  [1e+01, 1e+02]\n",
      "  Bounds range     [0e+00, 0e+00]\n",
      "  RHS range        [1e+00, 1e+00]\n",
      "Iteration    Objective       Primal Inf.    Dual Inf.      Time\n",
      "       0    1.4100000e+32   9.000000e+30   1.410000e+02      0s\n",
      "       2    2.5300000e+02   0.000000e+00   0.000000e+00      0s\n",
      "\n",
      "Solved in 2 iterations and 0.01 seconds (0.00 work units)\n",
      "Optimal objective  2.530000000e+02\n",
      "assign[Joe,Tester]: 1.0\n",
      "assign[Monika,JavaDeveloper]: 1.0\n",
      "assign[Ada,Architect]: 1.0\n",
      "Total matching score: 253.0\n"
     ]
    }
   ],
   "source": [
    "# reoptimize\n",
    "m.optimize()\n",
    "# display optimal values of decision variables\n",
    "print_solution(m)"
   ]
  }
 ],
 "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.9.2"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}