milp_tutorial/milp_tutorial_RAP_problem_002.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 only 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.\n",
    "\n",
    "**Math notation**\n",
    "\n",
    "$r \\in R$ means that a resource with index r is in the set (list) R.\n",
    "\n",
    "$j \\in J$ means that a job with index j is in the set (list) J."
   ]
  },
  {
   "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": [
    "The following “multidict” function describes the matching score associated with each possible combination of a resource and job.\n",
    "\n",
    "**Math notation**\n",
    "\n",
    "Let $ms_{r,\\;j}$ be the matching score of resource  $r \\in R$  with respect to job  $j \\in J$.\n",
    "\n",
    "Let $C_{r,\\;j}$ be the cost of assigning resource  $r \\in R$  to job  $j \\in J$.\n",
    "\n",
    "Let $B$ be the budget available."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [],
   "source": [
    "# matching score data\n",
    "combinations, ms, C = multidict({\n",
    "    ('Carlos', 'Tester'): [53, 1],\n",
    "    ('Carlos', 'JavaDeveloper'): [27, 1],\n",
    "    ('Carlos', 'Architect'): [13,1],\n",
    "    ('Joe', 'Tester'): [80, 2],\n",
    "    ('Joe', 'JavaDeveloper'): [47, 2],\n",
    "    ('Joe', 'Architect'): [67, 2],\n",
    "    ('Monika', 'Tester'): [53, 3] ,\n",
    "    ('Monika', 'JavaDeveloper'): [73, 3],\n",
    "    ('Monika', 'Architect'): [47, 3]\n",
    "})\n",
    "\n",
    "# Budget available\n",
    "#B = 6\n",
    "B=5"
   ]
  },
  {
   "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=1,2,3 and 𝑗=1,2,3.\n",
    "\n",
    "The “addVars()” method defines the decision variables of the model object “m”.  \n",
    "\n",
    "**Math notation**\n",
    "\n",
    "Let $x_{r,\\; j} = 1$ if resource $r \\in R$  is assigend to job $j \\in J$, and zero otherwise.\n",
    "\n",
    "Let $g_{j} = 1$ if job $j \\in J$ cannot be filled, and zero otherwise. This variable is a gap variable that indicates that a job cannot be filled.\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Create decision variables for the RAP model\n",
    "#x = m.addVars(combinations, name=\"assign\")\n",
    "x = m.addVars(combinations, vtype=GRB.BINARY, name=\"assign\")\n",
    "\n",
    "# Create gap variables for the RAP model\n",
    "g = m.addVars(J, name=\"gap\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 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} + g_{1} = 1$\n",
    "\n",
    "Constraint (Java-Developer=2): $x_{1,\\; 2} + x_{2,\\; 2} + x_{3,\\; 2} + g_{2} = 1$\n",
    "\n",
    "Constraint (Architect=3): $x_{1,\\; 3} + x_{2,\\; 3} + x_{3,\\; 3} + g_{3} = 1$\n",
    "\n",
    "The “addConstrs()” method defines the constraints of the model object “m”. \n",
    "\n",
    "**Math notation**\n",
    "\n",
    "For each job $j \\in J$, exactly one resouce must be assigned:\n",
    "\n",
    "$$\n",
    "\\sum_{r \\: \\in \\: R} x_{r,\\; j} + g_{j} = 1 \n",
    "$$\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [],
   "source": [
    "# create jobs  constraints\n",
    "jobs = m.addConstrs((x.sum('*',j) + g[j]  == 1 for j in J), 'job')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 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",
    "The “addConstrs()” method defines the constraints of the model object “m”. \n",
    "\n",
    "**Math notation**\n",
    "\n",
    "For each resource $r \\in R$, at most one job can be assigned:\n",
    "\n",
    "$$\n",
    "\\sum_{j \\: \\in \\: J} x_{r,\\; j} \\leq 1 \n",
    "$$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [],
   "source": [
    "# create resources constraints\n",
    "resources = m.addConstrs((x.sum(r,'*') <= 1 for r in R), 'resource')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Budget constraint\n",
    "\n",
    "The total cost of assigning resources to jobs should be less or equal than the budget available.\n",
    "\n",
    "$$\n",
    "\\sum_{r \\; \\in \\; R} \\sum_{j \\; \\in \\; J} C_{r, j}x_{r, j} \\leq B\n",
    "$$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [],
   "source": [
    "budget = m.addConstr((x.prod(C) <= B), 'budget')"
   ]
  },
  {
   "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”. \n",
    "\n",
    "**Math notation**\n",
    "\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} -BigM \\sum_{j \\in J} g_{j}\n",
    "$$\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Penalty for not filling a job position\n",
    "BIGM =101\n",
    "\n",
    "# The objective is to maximize total matching score of the assignments\n",
    "m.setObjective(x.prod(ms) -BIGM*g.sum(), GRB.MAXIMIZE)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [],
   "source": [
    "# save model for inspection\n",
    "m.write('RAP3.lp')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "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 7 rows, 12 columns and 30 nonzeros\n",
      "Model fingerprint: 0xa1231a12\n",
      "Variable types: 3 continuous, 9 integer (9 binary)\n",
      "Coefficient statistics:\n",
      "  Matrix range     [1e+00, 3e+00]\n",
      "  Objective range  [1e+01, 1e+02]\n",
      "  Bounds range     [1e+00, 1e+00]\n",
      "  RHS range        [1e+00, 5e+00]\n",
      "Presolve time: 0.00s\n",
      "Presolved: 7 rows, 12 columns, 30 nonzeros\n",
      "Variable types: 0 continuous, 12 integer (12 binary)\n",
      "Found heuristic solution: objective 52.0000000\n",
      "\n",
      "Root relaxation: objective 1.350000e+02, 4 iterations, 0.00 seconds (0.00 work units)\n",
      "\n",
      "    Nodes    |    Current Node    |     Objective Bounds      |     Work\n",
      " Expl Unexpl |  Obj  Depth IntInf | Incumbent    BestBd   Gap | It/Node Time\n",
      "\n",
      "     0     0  135.00000    0    2   52.00000  135.00000   160%     -    0s\n",
      "     0     0     cutoff    0        52.00000   52.00000  0.00%     -    0s\n",
      "\n",
      "Cutting planes:\n",
      "  Gomory: 1\n",
      "  GUB cover: 1\n",
      "  RLT: 1\n",
      "\n",
      "Explored 1 nodes (6 simplex iterations) in 0.04 seconds (0.00 work units)\n",
      "Thread count was 8 (of 8 available processors)\n",
      "\n",
      "Solution count 1: 52 \n",
      "\n",
      "Optimal solution found (tolerance 1.00e-04)\n",
      "Best objective 5.200000000000e+01, best bound 5.200000000000e+01, gap 0.0000%\n"
     ]
    }
   ],
   "source": [
    "# run optimization engine\n",
    "m.optimize()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "assign[Joe,Tester] 1.0\n",
      "assign[Monika,JavaDeveloper] 1.0\n",
      "gap[Architect] 1.0\n",
      "Optimal objective function value 52.0\n",
      "Total matching score:  153.0\n"
     ]
    }
   ],
   "source": [
    "# display optimal values of decision variables\n",
    "for v in m.getVars():\n",
    "\tif (abs(v.x) > 1e-6):\n",
    "\t\tprint(v.varName, v.x)\n",
    "\n",
    "# display optimal total matching score\n",
    "print('Optimal objective function value', m.objVal)   \n",
    "\n",
    "# Compute total matching score from assignment  variables\n",
    "total_matching_score = 0\n",
    "for [r, j] in combinations:\n",
    "    if (abs(x[r, j].x) > 1e-6):\n",
    "        total_matching_score = total_matching_score + ms[r, j]*x[r, j].x\n",
    "\n",
    "print('Total matching score: ', total_matching_score)  \n"
   ]
  }
 ],
 "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
}