milp_tutorial/milp_tutorial_RAP_problem_003.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 a few packages as needed"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%pip install gurobipy\n",
    "%pip install names\n",
    "%pip install numpy"
   ]
  },
  {
   "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} = 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",
    "\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": false
   },
   "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"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Sample a Random Scenario"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {},
   "outputs": [],
   "source": [
    "import names\n",
    "import random\n",
    "import numpy as np\n",
    "from gurobipy import *\n",
    "from itertools import product\n",
    "\n",
    "def generate_scenario(num_resources=200, num_jobs=200, roles=None,\n",
    "                      score_mu=50, score_sigma=15, seed=10101):\n",
    "    random.seed(seed)\n",
    "    np.random.seed(seed)\n",
    "    if roles is None:\n",
    "        roles = {\"Architect\", \"BackEndEngineer\", \"FrontEndEngineer\",\n",
    "                     \"Tester\", \"DataScientist\", \"DataEngineer\"}\n",
    "    # P.D.F. of resource costs follows Benford's law, having support {1,2,...,9}\n",
    "    benford = [np.log10((i+1)/i) for i in range(1,10)]\n",
    "    # Sample resource names\n",
    "    resources = {names.get_full_name() for i in range(num_resources)}\n",
    "    # Sample job requirements, given that all roles are equally likely to be selected\n",
    "    req = np.random.multinomial(num_jobs, [1/len(roles)]*len(roles), size=1)[0]\n",
    "    jobs = set()\n",
    "    # Assign ID to each job position\n",
    "    for i, role in enumerate(roles):\n",
    "        jobs = jobs.union(set(map(''.join, zip([role]*req[i], [str(x).zfill(int(np.log10(num_jobs))+1) for x in range(1,req[i]+1)]))))\n",
    "    scores = {}\n",
    "    costs = {}\n",
    "    # Sample matching score and cost for each potential assignment\n",
    "    for pair in product(resources, jobs):\n",
    "        scores[pair] = int(np.clip(np.random.normal(score_mu, score_sigma), 0, 100))\n",
    "        costs[pair] = random.choices(list(range(1,10)), weights=benford, k=1)[0]\n",
    "    return resources, jobs, scores, costs "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {},
   "outputs": [],
   "source": [
    "res, job, ms, cst = generate_scenario(seed=11111)\n",
    "budget = 200"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Get a Greedy Solution"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {},
   "outputs": [],
   "source": [
    "def greedy_solve(resources, jobs, scores, costs, budget):\n",
    "    assign = set()\n",
    "    total_score = 0\n",
    "    remaining_budget = budget\n",
    "    while remaining_budget > 0 and len(scores.keys()) > 0:\n",
    "        selection = max(scores, key=scores.get)\n",
    "        assign.add(selection)\n",
    "        total_score += scores[selection]\n",
    "        remaining_budget -= costs[selection]\n",
    "        # Remove potential assignments related to the resource/job of new selection\n",
    "        res_filter = list(filter(lambda x: x[0] == selection[0], scores))\n",
    "        job_filter = list(filter(lambda x: x[1] == selection[1], scores))\n",
    "        blacklist = res_filter + job_filter\n",
    "        scores = {key: val for key,val in scores.items()\n",
    "                  if key not in blacklist\n",
    "                  and costs[key] <= remaining_budget}\n",
    "    print(\"Number of assignments: {0}\".format(len(assign)))\n",
    "    print(\"Total matching score: {0}\".format(total_score))\n",
    "    print(\"Budget consumed: {0}\".format(budget - remaining_budget))\n",
    "    \n",
    "    kpi = {}\n",
    "    kpi[\"n_assign\"] = len(assign)\n",
    "    kpi[\"total_ms\"] = total_score\n",
    "    kpi[\"budget_used\"] = budget - remaining_budget\n",
    "    return assign, kpi\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Number of assignments: 58\n",
      "Total matching score: 5589\n",
      "Budget consumed: 200\n"
     ]
    }
   ],
   "source": [
    "greedy_sol, kpi = greedy_solve(res, job, ms, cst, budget)\n",
    "\n",
    "# Greedy heuristic KPI's \n",
    "Greedy_assign = kpi[\"n_assign\"]\n",
    "Greedy_ms = kpi[\"total_ms\"]\n",
    "\n",
    "#print('Greedy number assignments: ', Greedy_assign)\n",
    "#print('Greedy total matching score: ',Greedy_ms)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Get Optimal Solution"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "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 401 rows, 40200 columns and 120200 nonzeros\n",
      "Model fingerprint: 0xcca97cf6\n",
      "Variable types: 200 continuous, 40000 integer (40000 binary)\n",
      "Coefficient statistics:\n",
      "  Matrix range     [1e+00, 9e+00]\n",
      "  Objective range  [1e+00, 1e+02]\n",
      "  Bounds range     [1e+00, 1e+00]\n",
      "  RHS range        [1e+00, 2e+02]\n",
      "Found heuristic solution: objective -20200.00000\n",
      "Presolve time: 0.22s\n",
      "Presolved: 401 rows, 40200 columns, 120200 nonzeros\n",
      "Variable types: 0 continuous, 40200 integer (40200 binary)\n",
      "Found heuristic solution: objective -14889.00000\n",
      "\n",
      "Root relaxation: objective 1.627500e+04, 647 iterations, 0.10 seconds (0.10 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               0    16275.000000 16275.0000  0.00%     -    0s\n",
      "\n",
      "Explored 1 nodes (647 simplex iterations) in 0.55 seconds (0.50 work units)\n",
      "Thread count was 8 (of 8 available processors)\n",
      "\n",
      "Solution count 3: 16275 -14889 -20200 \n",
      "\n",
      "Optimal solution found (tolerance 1.00e-04)\n",
      "Best objective 1.627500000000e+04, best bound 1.627500000000e+04, gap 0.0000%\n"
     ]
    }
   ],
   "source": [
    "m = Model(\"RAP\")\n",
    "assign = m.addVars(ms.keys(), vtype=GRB.BINARY, name=\"assign\")\n",
    "g = m.addVars(job, name=\"gap\")\n",
    "m.addConstrs((assign.sum(\"*\", j) + g[j]  == 1 for j in job), name=\"demand\")\n",
    "m.addConstrs((assign.sum(r, \"*\") <= 1 for r in res), name=\"supply\")\n",
    "m.addConstr(assign.prod(cst) <= budget, name=\"Budget\")\n",
    "m.setObjective(assign.prod(ms) -BIGM*g.sum(), GRB.MAXIMIZE)\n",
    "m.optimize()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1) assign[Addie Brown,DataScientist045]: 1.0\n",
      "2) assign[Mary Hackler,DataEngineer032]: 1.0\n",
      "3) assign[Gladys Worrell,BackEndEngineer004]: 1.0\n",
      "4) assign[Robert Ohara,Architect023]: 1.0\n",
      "5) assign[Antoine Bullard,Tester022]: 1.0\n",
      "6) assign[Frederick Farrell,DataEngineer017]: 1.0\n",
      "7) assign[Rita Hodge,DataScientist021]: 1.0\n",
      "8) assign[Denver Madrid,FrontEndEngineer006]: 1.0\n",
      "9) assign[Juan Ordonez,Tester027]: 1.0\n",
      "10) assign[John Copper,BackEndEngineer013]: 1.0\n",
      "11) assign[Terri Bartholomew,DataScientist023]: 1.0\n",
      "12) assign[Dennis Lee,DataEngineer030]: 1.0\n",
      "13) assign[Joey Sampson,Tester018]: 1.0\n",
      "14) assign[Leila Richardson,Architect024]: 1.0\n",
      "15) assign[William James,BackEndEngineer021]: 1.0\n",
      "16) assign[Antonio Hancock,FrontEndEngineer008]: 1.0\n",
      "17) assign[Courtney Heinandez,BackEndEngineer023]: 1.0\n",
      "18) assign[Don Ely,DataScientist009]: 1.0\n",
      "19) assign[Nicholas Beltrame,DataScientist043]: 1.0\n",
      "20) assign[Clara Lindgren,BackEndEngineer012]: 1.0\n",
      "21) assign[Michael Hodges,DataScientist034]: 1.0\n",
      "22) assign[Maria Beals,Architect017]: 1.0\n",
      "23) assign[Robin Ransome,BackEndEngineer011]: 1.0\n",
      "24) assign[Amanda Membreno,DataEngineer008]: 1.0\n",
      "25) assign[Susie Leonard,DataEngineer006]: 1.0\n",
      "26) assign[John Thomas,DataEngineer019]: 1.0\n",
      "27) assign[Jason Stjohn,DataScientist033]: 1.0\n",
      "28) assign[Marilyn Melanson,DataScientist025]: 1.0\n",
      "29) assign[Earl Rosen,Architect008]: 1.0\n",
      "30) assign[Edward Gray,Architect019]: 1.0\n",
      "31) assign[Ronald Marashio,FrontEndEngineer019]: 1.0\n",
      "32) assign[Monica Grubbs,DataScientist011]: 1.0\n",
      "33) assign[Karla Sanchez,FrontEndEngineer031]: 1.0\n",
      "34) assign[George Stalker,DataScientist017]: 1.0\n",
      "35) assign[Ann Holtzman,DataScientist001]: 1.0\n",
      "36) assign[Richard Latigo,DataEngineer029]: 1.0\n",
      "37) assign[Noel Connelly,FrontEndEngineer004]: 1.0\n",
      "38) assign[Stephanie Gardner,FrontEndEngineer026]: 1.0\n",
      "39) assign[Donald Green,DataScientist005]: 1.0\n",
      "40) assign[Christine Nichols,FrontEndEngineer027]: 1.0\n",
      "41) assign[Philip Mcalary,FrontEndEngineer030]: 1.0\n",
      "42) assign[Jeffrey Fetter,FrontEndEngineer005]: 1.0\n",
      "43) assign[Patrick Odell,DataScientist010]: 1.0\n",
      "44) assign[Karen Horton,FrontEndEngineer014]: 1.0\n",
      "45) assign[Clarence Morton,BackEndEngineer007]: 1.0\n",
      "46) assign[Derek Landon,FrontEndEngineer012]: 1.0\n",
      "47) assign[Michele Dess,Architect030]: 1.0\n",
      "48) assign[Joe Gantt,Tester021]: 1.0\n",
      "49) assign[Sharon Dean,DataScientist004]: 1.0\n",
      "50) assign[Gary Voris,FrontEndEngineer015]: 1.0\n",
      "51) assign[Nicole Hewitt,DataScientist035]: 1.0\n",
      "52) assign[Jessica Mata,Tester014]: 1.0\n",
      "53) assign[Travis Cole,Tester019]: 1.0\n",
      "54) assign[Jason Fields,DataScientist007]: 1.0\n",
      "55) assign[John Nester,Architect014]: 1.0\n",
      "56) assign[Barbara Geoghegan,Tester009]: 1.0\n",
      "57) assign[Kristin Wermers,Tester012]: 1.0\n",
      "58) assign[Debra Lemke,BackEndEngineer017]: 1.0\n",
      "59) assign[Blanca Thompson,BackEndEngineer019]: 1.0\n",
      "60) assign[Samuel Crews,Architect012]: 1.0\n",
      "61) assign[David Williams,DataEngineer007]: 1.0\n",
      "62) assign[Glen Thompson,DataScientist028]: 1.0\n",
      "63) assign[Roy Bednorz,DataEngineer009]: 1.0\n",
      "64) assign[Jerry Dragon,DataEngineer024]: 1.0\n",
      "65) assign[Paul Lowe,DataEngineer018]: 1.0\n",
      "66) assign[Catalina Anderson,BackEndEngineer009]: 1.0\n",
      "67) assign[James Bates,DataEngineer035]: 1.0\n",
      "68) assign[Ronald Mcconnell,Architect005]: 1.0\n",
      "69) assign[Joel Dodd,Architect010]: 1.0\n",
      "70) assign[Vallie Silvestri,FrontEndEngineer020]: 1.0\n",
      "71) assign[Michael Davis,DataEngineer013]: 1.0\n",
      "72) assign[Charles Bianco,Architect031]: 1.0\n",
      "73) assign[James Oneill,Architect011]: 1.0\n",
      "74) assign[Joyce Carrier,DataEngineer038]: 1.0\n",
      "75) assign[Jay Terry,DataScientist012]: 1.0\n",
      "76) assign[Paul Barron,DataEngineer010]: 1.0\n",
      "77) assign[Anita Smith,FrontEndEngineer022]: 1.0\n",
      "78) assign[Jenelle Giller,DataEngineer016]: 1.0\n",
      "79) assign[Patricia Maggard,FrontEndEngineer028]: 1.0\n",
      "80) assign[Johnny Mcmurray,Architect020]: 1.0\n",
      "81) assign[Jose Uong,DataEngineer033]: 1.0\n",
      "82) assign[Odell Deanda,Architect009]: 1.0\n",
      "83) assign[Elias Pinkston,Architect028]: 1.0\n",
      "84) assign[Quinton Manning,DataScientist031]: 1.0\n",
      "85) assign[Jason Langford,DataEngineer015]: 1.0\n",
      "86) assign[Shanon Moore,FrontEndEngineer013]: 1.0\n",
      "87) assign[Roy Bailey,DataEngineer001]: 1.0\n",
      "88) assign[Robert Douglas,DataScientist038]: 1.0\n",
      "89) assign[Kimberly Brown,Architect027]: 1.0\n",
      "90) assign[Stephanie George,FrontEndEngineer018]: 1.0\n",
      "91) assign[Jordan Ward,DataScientist030]: 1.0\n",
      "92) assign[Michael Kozlowski,Tester026]: 1.0\n",
      "93) assign[Carmella Sixon,DataEngineer022]: 1.0\n",
      "94) assign[Devorah Pierre,DataScientist032]: 1.0\n",
      "95) assign[Gertrude Knowles,Architect002]: 1.0\n",
      "96) assign[Eric Gonzalez,FrontEndEngineer010]: 1.0\n",
      "97) assign[John Walsh,BackEndEngineer001]: 1.0\n",
      "98) assign[Rebecca Klatt,Tester023]: 1.0\n",
      "99) assign[Lance Segura,BackEndEngineer010]: 1.0\n",
      "100) assign[Rufus Walker,BackEndEngineer016]: 1.0\n",
      "101) assign[Richard Jennings,Architect033]: 1.0\n",
      "102) assign[Elizabeth Johnston,Architect025]: 1.0\n",
      "103) assign[Rose Mcgregor,DataEngineer031]: 1.0\n",
      "104) assign[Mark Sangster,Tester024]: 1.0\n",
      "105) assign[Tammy Creighton,Architect016]: 1.0\n",
      "106) assign[Jeffrey Dixon,FrontEndEngineer002]: 1.0\n",
      "107) assign[Robert Hatton,Tester013]: 1.0\n",
      "108) assign[Charles Doering,Tester015]: 1.0\n",
      "109) assign[Lillian Biser,Tester002]: 1.0\n",
      "110) assign[Dominica Milner,Architect013]: 1.0\n",
      "111) assign[Alicia Glover,Architect007]: 1.0\n",
      "112) assign[Nichole Barlow,Tester004]: 1.0\n",
      "113) assign[Frances Lavender,DataScientist006]: 1.0\n",
      "114) assign[Martha Newport,BackEndEngineer005]: 1.0\n",
      "115) assign[Charles Thomas,FrontEndEngineer017]: 1.0\n",
      "116) assign[Linda Capp,DataScientist013]: 1.0\n",
      "117) assign[James Carter,Architect029]: 1.0\n",
      "118) assign[Zachary Curtis,Architect021]: 1.0\n",
      "119) assign[Teresa Spoon,BackEndEngineer002]: 1.0\n",
      "120) assign[Bianca Harris,DataEngineer012]: 1.0\n",
      "121) assign[Myles French,DataEngineer036]: 1.0\n",
      "122) assign[Gertrude Webb,DataScientist027]: 1.0\n",
      "123) assign[Geri Brooks,Tester008]: 1.0\n",
      "124) assign[Brad Love,Architect022]: 1.0\n",
      "125) assign[Tina Johnson,Tester017]: 1.0\n",
      "126) assign[Chad Day,DataEngineer025]: 1.0\n",
      "127) assign[Gracie Shockley,DataEngineer028]: 1.0\n",
      "128) assign[Elena Lee,DataScientist044]: 1.0\n",
      "129) assign[Leslie Swain,Architect004]: 1.0\n",
      "130) assign[Paul Hudson,DataScientist018]: 1.0\n",
      "131) assign[Karen Merchant,BackEndEngineer014]: 1.0\n",
      "132) assign[Joe Anderson,DataEngineer014]: 1.0\n",
      "133) assign[Heather Khan,FrontEndEngineer021]: 1.0\n",
      "134) assign[Jacob Schwartz,DataEngineer011]: 1.0\n",
      "135) assign[Terry Cunningham,BackEndEngineer018]: 1.0\n",
      "136) assign[Tracy Popielarczyk,DataScientist037]: 1.0\n",
      "137) assign[Shirley Begley,DataEngineer002]: 1.0\n",
      "138) assign[Florence Canada,Tester003]: 1.0\n",
      "139) assign[John Solis,Tester025]: 1.0\n",
      "140) assign[Autumn Phothirath,DataScientist002]: 1.0\n",
      "141) assign[Matthew Vaughn,DataScientist029]: 1.0\n",
      "142) assign[Heather Lewis,DataScientist042]: 1.0\n",
      "143) assign[Cordelia Kaylor,DataEngineer027]: 1.0\n",
      "144) assign[Harriet Vandenberge,Architect006]: 1.0\n",
      "145) assign[Kristie Cobb,DataScientist014]: 1.0\n",
      "146) assign[Heather Lindquist,FrontEndEngineer025]: 1.0\n",
      "147) assign[David Rogowski,Tester011]: 1.0\n",
      "148) assign[Daniel Stone,DataEngineer039]: 1.0\n",
      "149) assign[Christy Acree,DataScientist008]: 1.0\n",
      "150) assign[Jerry Collett,Tester007]: 1.0\n",
      "151) assign[William Jones,DataScientist020]: 1.0\n",
      "152) assign[Jessica Bentley,DataEngineer026]: 1.0\n",
      "153) assign[Crystal Douglas,FrontEndEngineer029]: 1.0\n",
      "154) assign[Tressie Vargas,BackEndEngineer015]: 1.0\n",
      "155) assign[Patricia Vaughn,DataScientist022]: 1.0\n",
      "156) assign[Suzie Levings,FrontEndEngineer007]: 1.0\n",
      "157) assign[Krystal Berardi,DataEngineer023]: 1.0\n",
      "158) assign[Laura Portes,DataScientist039]: 1.0\n",
      "159) assign[Shelia Rossi,Architect015]: 1.0\n",
      "160) assign[Michelle Garnand,DataScientist036]: 1.0\n",
      "161) assign[Douglas Mariani,BackEndEngineer006]: 1.0\n",
      "162) assign[Dora Catchings,Tester005]: 1.0\n",
      "163) assign[Kory Gonsalez,Tester010]: 1.0\n",
      "164) assign[Richard Williams,DataScientist026]: 1.0\n",
      "165) assign[David Miner,Tester020]: 1.0\n",
      "166) assign[Patrick Rogers,DataEngineer003]: 1.0\n",
      "167) assign[Jennifer Hogan,BackEndEngineer020]: 1.0\n",
      "168) assign[Lenore Torrence,FrontEndEngineer009]: 1.0\n",
      "169) assign[Patricia Summerlin,Architect026]: 1.0\n",
      "170) assign[Dorthey Hannah,Architect003]: 1.0\n",
      "171) assign[Kimberly Peterson,DataScientist040]: 1.0\n",
      "172) assign[Geraldine Vargas,FrontEndEngineer003]: 1.0\n",
      "173) assign[Melissa Maupin,FrontEndEngineer001]: 1.0\n",
      "174) assign[Joe Suarez,BackEndEngineer008]: 1.0\n",
      "175) assign[Paula Gonzales,FrontEndEngineer032]: 1.0\n",
      "176) assign[Jesus Hancock,FrontEndEngineer016]: 1.0\n",
      "177) assign[James Peters,DataScientist016]: 1.0\n",
      "178) assign[Luis Tamondong,FrontEndEngineer023]: 1.0\n",
      "179) assign[Charles Gomez,DataEngineer021]: 1.0\n",
      "180) assign[Benjamin Barber,DataEngineer020]: 1.0\n",
      "181) assign[Jennifer Wohner,DataEngineer004]: 1.0\n",
      "182) assign[Raymond Cole,DataScientist003]: 1.0\n",
      "183) assign[Missy Burke,DataScientist015]: 1.0\n",
      "184) assign[Donald Marx,FrontEndEngineer011]: 1.0\n",
      "185) assign[Thomas Kaufman,Tester006]: 1.0\n",
      "186) assign[Marita Buhmann,Architect001]: 1.0\n",
      "187) assign[Cory Arciniega,Architect034]: 1.0\n",
      "188) assign[Alisha Johnson,DataEngineer037]: 1.0\n",
      "189) assign[Mina Sheffield,DataScientist019]: 1.0\n",
      "190) assign[Mary Conner,Tester016]: 1.0\n",
      "191) assign[Terry Wilson,DataScientist024]: 1.0\n",
      "192) assign[Jennie James,Architect018]: 1.0\n",
      "193) assign[Johnny Walker,BackEndEngineer003]: 1.0\n",
      "194) assign[Lavon Cothran,FrontEndEngineer024]: 1.0\n",
      "195) assign[Sara Raymond,DataScientist041]: 1.0\n",
      "196) assign[Sean Elwell,Architect032]: 1.0\n",
      "197) assign[Kelly Buoy,BackEndEngineer022]: 1.0\n",
      "198) assign[Jonathan Younglas,Tester001]: 1.0\n",
      "199) assign[Salvatore Averill,DataEngineer005]: 1.0\n",
      "200) assign[Lorena Freeman,DataEngineer034]: 1.0\n",
      "Total matching score: 16275.0\n",
      "Optimal objective function value: 16275.0\n"
     ]
    }
   ],
   "source": [
    "def print_solution(model):\n",
    "    i = 1\n",
    "    total_ms = 0\n",
    "    for var in model.getVars():\n",
    "        if abs(var.x) > 1e-6:\n",
    "            print(\"{0}) {1}: {2}\".format(i, var.varName, var.x))\n",
    "            i += 1\n",
    "            if \"assign\" in var.varName:\n",
    "                total_ms += var.Obj\n",
    "    print('Total matching score: {0}'.format(total_ms))\n",
    "    print('Optimal objective function value: {0}'.format(model.objVal))\n",
    "    return None\n",
    "\n",
    "# display optimal values of decision variables\n",
    "print_solution(m)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Assignment ratio:  29.00 %\n",
      "Matching score ratio:  34.34 %\n"
     ]
    }
   ],
   "source": [
    "# comparing KPI's of greedy heuristic and Gurobi Optimizer\n",
    "Gurobi_assign = 0\n",
    "Gurobi_ms = 0\n",
    "for [r,j] in ms.keys():\n",
    "    if (abs(assign[r, j].x) > 1e-6):\n",
    "        Gurobi_assign = Gurobi_assign + assign[r, j].x\n",
    "        Gurobi_ms = Gurobi_ms + ms[r, j]*assign[r, j].x\n",
    "        \n",
    "#print('Gurobi total assignments: ', Gurobi_assign)\n",
    "#print('Gurobi total matching score: ', Gurobi_ms)\n",
    "\n",
    "#Ratio of Greedy assignments respect to Gurobi assignments\n",
    "assign_ratio = 100*Greedy_assign/Gurobi_assign\n",
    "ms_ratio = 100*Greedy_ms/Gurobi_ms\n",
    "\n",
    "print('Assignment ratio: ',\"%.2f\" % assign_ratio, '%')\n",
    "print('Matching score ratio: ',\"%.2f\" % ms_ratio, '%')"
   ]
  }
 ],
 "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
}