milp_tutorial/introduction_to_modeling.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Introduction to Mathematical Optimization Modeling\n",
    "\n",
    "## Objective and Prerequisites\n",
    "\n",
    "Are you looking to learn the basics of mathematical optimization modeling? If so, then this is a great place to start. In this tutorial, we’ll walk you through the process of building a mathematical optimization model and solving a mathematical optimization problem. We’ll begin by giving you an overview of the key components of a simple mathematical optimization problem, then show you how to create a mathematical optimization model (or, to be more precise, a mixed-integer programming or MIP model) of the problem using using the Gurobi Python API, and then demonstrate how you can automatically generate an optimal solution using the Gurobi Optimizer.\n",
    "\n",
    "This modeling tutorial is at the introductory level, where we assume that you know Python and that you have a background on a discipline that uses quantitative methods.\n",
    "\n",
    "You may find it helpful to refer to the [documentation](https://www.gurobi.com/resources/?category-filter=documentation) \n",
    "of the Gurobi Python API. This notebook is explained in detail in our series of tutorial videos on mixed-integer linear programming. You can watch these videos by clicking\n",
    "[here](https://www.gurobi.com/resource/tutorial-mixed-integer-linear-programming/)\n",
    "\n",
    "**Download the Repository** <br />\n",
    "You can download the repository containing this and other examples by clicking [here](https://github.com/Gurobi/modeling-examples/archive/master.zip). \n",
    "\n",
    "## Problem description\n",
    "\n",
    "Consider a consulting company that has three open positions: Tester, Java Developer, and Architect. The three top candidates (resources) for the positions are: Carlos, Joe, and Monika. The consulting company administered competency tests to each candidate in order to assess their ability to perform each of the jobs. The results of these tests are called *matching scores*. Assume that only one candidate can be assigned to a job, and at most one job can be assigned to a candidate.\n",
    "\n",
    "The problem is to determine an assignment of resources and jobs such that each job is fulfilled, each resource is assigned to at most one job, and the total matching scores of the assignments is maximized.\n",
    "\n",
    "\n",
    "## Mathematical optimization \n",
    "\n",
    "Mathematical optimization (which is also known as mathematical programming) is a declarative approach where the modeler formulates an  optimization problem that captures the key features of a complex decision problem. The Gurobi Optimizer solves the mathematical optimization problem using state-of-the-art mathematics and computer science.\n",
    "\n",
    "A mathematical optimization model has five components:\n",
    "\n",
    "* Sets\n",
    "* Parameters\n",
    "* Decision variables\n",
    "* Constraints\n",
    "* Objective function(s)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "%pip install gurobipy"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The following Python code imports the Gurobi callable library and imports the ``GRB`` class into the main namespace."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "import gurobipy as gp\n",
    "from gurobipy import GRB"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Resource Assignment Problem\n",
    "### 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",
    "$r \\in R$: index and set of resources. The resource $r$ belongs to the set of resources $R$.\n",
    "\n",
    "$j \\in J$: index and set of jobs. The job $j$ belongs to the set of jobs $J$."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Resource and job sets\n",
    "R = ['Carlos', 'Joe', 'Monika']\n",
    "J = ['Tester', 'JavaDeveloper', 'Architect']"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The ability of each resource to perform each of the jobs is listed in the following matching scores table:\n",
    "\n",
    "![scores](util/matching_score_data.PNG)\n",
    "\n",
    "For each resource $r$ and job $j$, there is a corresponding matching score $s$. The matching score $s$ can only take values between 0 and 100. That is, $s_{r,j} \\in [0, 100]$ for all resources $r \\in R$ and jobs $j \\in J$. \n",
    "\n",
    "We use the Gurobi Python ``multidict`` function to initialize one or more dictionaries with a single statement. The function takes a dictionary as its argument. The keys represent the possible combinations of resources and jobs.\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Matching score data\n",
    "combinations, scores = gp.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 constructor creates an empty ``Model`` object “m”. We specify the model name by passing the string \"RAP\" as an argument. The ``Model`` object “m” holds a single optimization problem. It consists of a set of variables, a set of constraints, and the objective function."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Declare and initialize model\n",
    "m = gp.Model('RAP')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Decision variables\n",
    "\n",
    "To solve this assignment problem, we need to identify which resource is assigned to which job. We introduce a decision variable for each possible assignment of resources to jobs. Therefore, we have 9 decision variables.\n",
    "\n",
    "To simplify the mathematical notation of the model formulation, we define the following indices for resources and jobs:\n",
    "\n",
    "![variables](util/decision_variables.PNG)\n",
    "\n",
    "For example, $x_{2,1}$ is the decision variable associated with assigning the resource Joe to the job Tester. Therefore, decision variable $x_{r,j}$ equals 1 if resource $r \\in R$  is assigned to job $j \\in J$, and 0 otherwise.\n",
    "\n",
    "The ``Model.addVars()`` method creates the decision variables for a ``Model`` object.\n",
    "This method returns a Gurobi ``tupledict`` object that contains the newly created variables. We supply the ``combinations`` object as the first argument to specify the variable indices. The ``name`` keyword is used to specify a name for the newly created decision variables. By default, variables are assumed to be non-negative."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "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",
    "We now discuss the constraints associated with the jobs. These constraints need to ensure that each job is filled by exactly one resource.\n",
    "\n",
    "The job constraint for the Tester position requires that resource 1 (Carlos), resource 2 (Joe), or resource 3 (Monika) is assigned to this job. This corresponds to the following constraint.\n",
    "\n",
    "Constraint (Tester=1)\n",
    "\n",
    "$$\n",
    "x_{1,1} + x_{2,1} + x_{3,1} = 1\n",
    "$$\n",
    "\n",
    "Similarly, the constraints for the Java Developer and Architect positions can be defined as follows.\n",
    "\n",
    "Constraint (Java Developer = 2)\n",
    "\n",
    "$$\n",
    "x_{1,2} + x_{2,2} + x_{3,2} = 1\n",
    "$$\n",
    "\n",
    "Constraint (Architect = 3)\n",
    "\n",
    "$$\n",
    "x_{1,3} + x_{2,3} + x_{3,3} = 1\n",
    "$$\n",
    "\n",
    "The job constraints are defined by the columns of the following table.\n",
    "\n",
    "![jobs](util/jobs_constraints.PNG)\n",
    "\n",
    "In general, the constraint for the job Tester can defined as follows.\n",
    "\n",
    "$$\n",
    "x_{1,1} + x_{2,1} + x_{3,1} = \\sum_{r=1}^{3 } x_{r,1} =  \\sum_{r \\in R} x_{r,1} = 1\n",
    "$$\n",
    "\n",
    "All of the job constraints can be defined in a similarly succinct manner. For each job $j \\in J$, take the summation of the decision variables over all the resources. We can write the corresponding job constraint as follows.\n",
    "\n",
    "$$\n",
    "\\sum_{r \\in R} x_{r,j} = 1\n",
    "$$\n",
    "\n",
    "The ``Model.addConstrs()`` method of the Gurobi/Python API defines the job constraints of the ``Model`` object “m”. This method returns a Gurobi ``tupledict`` object that contains the job constraints. \n",
    "The first argument of this method, \"x.sum(‘*’, j)\", is the sum method and defines the LHS of the jobs constraints as follows:\n",
    "For each job $j$ in the set of jobs $J$, take the summation of the decision variables over all the resources. The $==$  defines an equality constraint, and the number \"1\" is the RHS of the constraints.\n",
    "These constraints are saying that exactly one resource should be assigned to each job.\n",
    "The second argument is the name of this type of constraints.\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Create job constraints\n",
    "jobs = m.addConstrs((x.sum('*',j) == 1 for j in J), name='job')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Resource constraints\n",
    "\n",
    "The constraints for the resources need to ensure that at most one job is assigned to each resource. That is, it is possible that not all the resources are assigned.\n",
    "\n",
    "For example, we want a constraint that requires Carlos to be assigned to at most one of the jobs: either job 1 (Tester), job 2 (Java Developer ), or job 3 (Architect). We can write this constraint as follows.\n",
    "\n",
    "Constraint (Carlos=1)\n",
    "\n",
    "$$\n",
    "x_{1, 1} + x_{1, 2} + x_{1, 3}  \\leq 1.\n",
    "$$\n",
    "\n",
    "This constraint is less or equal than 1 to allow the possibility that Carlos is not assigned to any job. Similarly, the constraints for the resources Joe and Monika can be defined as follows:\n",
    "\n",
    "Constraint (Joe=2) \n",
    "\n",
    "$$\n",
    "x_{2, 1} + x_{2, 2} + x_{2, 3}  \\leq 1.\n",
    "$$\n",
    "\n",
    "Constraint (Monika=3)\n",
    "\n",
    "$$\n",
    "x_{3, 1} + x_{3, 2} + x_{3, 3}  \\leq 1.\n",
    "$$\n",
    "\n",
    "Observe that the resource constraints are defined by the rows of the following table.\n",
    "\n",
    "![resources](util/resource_constraints.PNG)\n",
    "\n",
    "The constraint for the resource Carlos can be defined as follows.\n",
    "\n",
    "$$\n",
    "x_{1, 1} + x_{1, 2} + x_{1, 3} = \\sum_{j=1}^{3 } x_{1,j} = \\sum_{j \\in J} x_{1,j} \\leq 1.\n",
    "$$\n",
    "\n",
    "Again, each of these constraints can be written in a succinct manner. For each resource $r \\in R$, take the summation of the decision variables over all the jobs. We can write the corresponding resource constraint as follows.\n",
    "\n",
    "$$\n",
    "\\sum_{j \\in J} x_{r,j} \\leq  1.\n",
    "$$\n",
    "\n",
    "The ``Model.addConstrs()`` method of the Gurobi/Python API defines the resource constraints of the ``Model`` object “m”. \n",
    "The first argument of this method, \"x.sum(r, ‘*’)\", is the sum method and defines the LHS of the resource constraints as follows: For each resource $r$ in the set of resources $R$, take the summation of the decision variables over all the jobs.\n",
    "The $<=$  defines a less or equal constraints, and the number “1” is the RHS of the constraints.\n",
    "These constraints are saying that each resource can be assigned to at most 1 job.\n",
    "The second argument is the name of this type of constraints.\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Create resource constraints\n",
    "resources = m.addConstrs((x.sum(r,'*') <= 1 for r in R), name='resource')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Objective function\n",
    "\n",
    "The objective function is to maximize the total matching score of the assignments that satisfy the job and resource constraints. \n",
    "\n",
    "For the Tester job, the matching score is $53x_{1,1}$, if resource Carlos is assigned, or $80x_{2,1}$, if resource Joe is assigned, or $53x_{3,1}$, if resource Monika is assigned.\n",
    "Consequently, the matching score for the Tester job is as follows, where only one term in this summation will be nonzero.\n",
    "\n",
    "$$\n",
    "53x_{1,1} + 80x_{2,1} + 53x_{3,1}. \n",
    "$$\n",
    "\n",
    "Similarly, the matching scores for the Java Developer and Architect jobs are defined as follows. The matching score for the Java Developer job is:\n",
    "\n",
    "$$\n",
    "27x_{1, 2} + 47x_{2, 2} + 73x_{3, 2}.\n",
    "$$\n",
    "\n",
    "The matching score for the Architect job is:\n",
    "\n",
    "$$\n",
    "13x_{1, 3} + 67x_{2, 3} + 47x_{3, 3}.\n",
    "$$\n",
    "\n",
    "The total matching score is the summation of each cell in the following table.\n",
    "\n",
    "![objfcn](util/objective_function.PNG)\n",
    "\n",
    "The goal is to  maximize the total matching score of the assignments. Therefore, the objective function is defined as follows.\n",
    "\n",
    "\\begin{equation}\n",
    "\\text{Maximize} \\quad (53x_{1,1} + 80x_{2,1} + 53x_{3,1}) \\; +\n",
    "\\end{equation}\n",
    "\n",
    "\\begin{equation}\n",
    "\\quad (27x_{1, 2} + 47x_{2, 2} + 73x_{3, 2}) \\; +\n",
    "\\end{equation}\n",
    "\n",
    "\\begin{equation}\n",
    "\\quad (13x_{1, 3} + 67x_{2, 3} + 47x_{3, 3}).\n",
    "\\end{equation}\n",
    "\n",
    "Each term in parenthesis in the objective function can be expressed as follows.\n",
    "\n",
    "\\begin{equation}\n",
    "(53x_{1,1} + 80x_{2,1} + 53x_{3,1}) = \\sum_{r \\in R} s_{r,1}x_{r,1}.\n",
    "\\end{equation}\n",
    "\n",
    "\\begin{equation}\n",
    "(27x_{1, 2} + 47x_{2, 2} + 73x_{3, 2}) = \\sum_{r \\in R} s_{r,2}x_{r,2}.\n",
    "\\end{equation}\n",
    "\n",
    "\\begin{equation}\n",
    "(13x_{1, 3} + 67x_{2, 3} + 47x_{3, 3}) = \\sum_{r \\in R} s_{r,3}x_{r,3}.\n",
    "\\end{equation}\n",
    "\n",
    "Hence, the objective function can be concisely written as:\n",
    "\n",
    "\\begin{equation}\n",
    "\\text{Maximize} \\quad \\sum_{j \\in J} \\sum_{r \\in R} s_{r,j}x_{r,j}.\n",
    "\\end{equation}\n",
    "\n",
    "The ``Model.setObjective()`` method of the Gurobi/Python API defines the objective function of the ``Model`` object “m”. The objective expression is specified in the first argument of this method.\n",
    "Notice that both the matching score parameters “score” and the assignment decision variables “x” are defined over the “combinations” keys. Therefore, we use the method “x.prod(score)” to obtain the summation of the elementwise multiplication of the \"score\" matrix and the \"x\" variable matrix.\n",
    "The second argument, ``GRB.MAXIMIZE``, is the optimization \"sense.\" In this case, we want to *maximize* the total matching scores of all assignments."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Objective: maximize total matching score of all assignments\n",
    "m.setObjective(x.prod(scores), GRB.MAXIMIZE)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We use the “write()” method of the Gurobi/Python API to write the model formulation to a file named \"RAP.lp\"."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Save model for inspection\n",
    "m.write('RAP.lp')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "![RAP](util/RAP_lp.PNG)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We use the “optimize( )” method of the Gurobi/Python API to solve the problem we have defined for the model object “m”."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {
    "scrolled": true
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Gurobi Optimizer version 10.0.2 build v10.0.2rc0 (win64)\n",
      "\n",
      "CPU model: 11th Gen Intel(R) Core(TM) i7-1165G7 @ 2.80GHz, instruction set [SSE2|AVX|AVX2|AVX512]\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": "markdown",
   "metadata": {},
   "source": [
    "The ``Model.getVars()`` method of the Gurobi/Python API \n",
    "retrieves a list of all variables in the Model object “m”. The ``.x`` variable attribute is used to query solution values and the ``.varName`` attribute is used to query the name of the decision variables.  "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "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": [
    "# Display optimal values of decision variables\n",
    "for v in m.getVars():\n",
    "    if v.x > 1e-6:\n",
    "        print(v.varName, v.x)\n",
    "\n",
    "# Display optimal total matching score\n",
    "print('Total matching score: ', m.objVal)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The optimal assignment is to assign:\n",
    "\n",
    "* Carlos to the Tester job, with a matching score of 53\n",
    "* Joe to the Architect job, with a matching score of 67\n",
    "* Monika to the Java Developer job, with a matching score of 73.\n",
    "\n",
    "The maximum total matching score is 193."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Resource Assignment Problem with a budget constraint\n",
    "\n",
    "Now, assume there is a fixed cost $C_{r,j}$ associated with assigning a resource $r \\in R$ to job $j \\in J$. Assume also that there is a limited budget $B$ that can be used for job assignments.\n",
    "\n",
    "The cost of assigning Carlos, Joe, or Monika to any of the jobs is $\\$1,000$ , $\\$2,000$ , and $\\$3,000$  respectively. The available budget is $\\$5,000$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Data\n",
    "\n",
    "The list $R$ contains the names of the three resources: Carlos, Joe, and Monika.\n",
    "The list $J$ contains the names of the job positions: Tester, Java Developer, and Architect.\n",
    "\n",
    "The Gurobi Python ``multidict`` function initialize two dictionaries: \n",
    "* \"scores\" defines the matching scores for each resource and job combination.\n",
    "* \"costs\" defines the fixed cost associated of assigning a resource to a job.\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Resource and job sets\n",
    "R = ['Carlos', 'Joe', 'Monika']\n",
    "J = ['Tester', 'JavaDeveloper', 'Architect']\n",
    "\n",
    "# Matching score data\n",
    "# Cost is given in thousands of dollars\n",
    "combinations, scores, costs = gp.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",
    "# Available budget (thousands of dollars)\n",
    "budget = 5"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The following constructor creates an empty ``Model`` object “m”. The ``Model`` object “m” holds a single optimization problem. It consists of a set of variables, a set of constraints, and the objective function."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Declare and initialize model\n",
    "m = gp.Model('RAP2')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Decision variables\n",
    "\n",
    "The decision variable $x_{r,j}$ is 1 if $r \\in R$ is assigned to job $j \\in J$, and 0 otherwise.\n",
    "\n",
    "The ``Model.addVars()`` method defines the decision variables for the model object “m”.  \n",
    "\n",
    "Because there is a budget constraint, it is possible that not all of the jobs will be filled. To account for this, we define a new decision variable that indicates whether or not a job is filled.\n",
    "\n",
    "Let $g_{j}$ be equal 1 if job $j \\in J$ is not filled, and 0 otherwise. This variable is a gap variable that indicates that a job cannot be filled.\n",
    "\n",
    "***Remark:*** For the previous formulation of the RAP, we defined the assignment variables as non-negative and continuous which is the default value of the ``vtype`` argument of the ``Model.addVars()`` method.\n",
    "However, in this extension of the RAP, because of the budget constraint we added to the model, we need to explicitly define these variables as binary. The ``vtype=GRB.BINARY`` argument of the ``Model.addVars()`` method defines the assignment variables as binary."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Create decision variables for the RAP model\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": [
    "### Job constraints\n",
    "\n",
    "Since we have a limited budget to assign resources to jobs, it is possible that not all the jobs can be filled. For the job constraints, there are two possibilities either a resource is assigned to fill the job, or this job cannot be filled and we need to declare a gap. This latter possibility is captured by the decision variable $g_j$. Therefore, the job constraints are written as follows. \n",
    "\n",
    "For each job $j \\in J$, exactly one resource must be assigned to the job, or the corresponding $g_j$ variable must be set to 1:\n",
    "\n",
    "$$\n",
    "\\sum_{r \\: \\in \\: R} x_{r,\\; j} + g_{j} = 1.\n",
    "$$\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Create job constraints\n",
    "jobs = m.addConstrs((x.sum('*',j) + g[j]  == 1 for j in J), name='job')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Resource constraints\n",
    "\n",
    "The constraints for the resources need to ensure that at most one job is assigned to each resource. That is, it is possible that not all the resources are assigned. Therefore, the resource constraints are written as follows.\n",
    "\n",
    "For each resource $r \\in R$, at most one job can be assigned to the resource:\n",
    "\n",
    "$$\n",
    "\\sum_{j \\: \\in \\: J} x_{r,\\; j} \\leq 1.\n",
    "$$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Create resource constraints\n",
    "resources = m.addConstrs((x.sum(r,'*') <= 1 for r in R), name='resource')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Budget constraint\n",
    "\n",
    "This constraint ensures that the cost of assigning resources to fill job requirements do not exceed the budget available. The costs of assignment and budget are in thousands of dollars.\n",
    "\n",
    "The cost of filling the Tester job is $1x_{1,1}$, if resource Carlos is assigned, or $2x_{2,1}$, if resource Joe is assigned, or $3x_{3,1}$, if resource Monika is assigned.\n",
    "Consequently, the cost of filling the Tester job is as follows, where at most one term in this summation will be nonzero.\n",
    "\n",
    "$$\n",
    "1x_{1,1} + 2x_{2,1} + 3x_{3,1}. \n",
    "$$\n",
    "\n",
    "Similarly, the cost of filling the Java Developer and Architect jobs are defined as follows. The cost of filling the Java Developer job is:\n",
    "\n",
    "$$\n",
    "1x_{1, 2} + 2x_{2, 2} + 3x_{3, 2}.\n",
    "$$\n",
    "\n",
    "The cost of filling the Architect job is:\n",
    "\n",
    "$$\n",
    "1x_{1, 3} + 2x_{2, 3} + 3x_{3, 3}.\n",
    "$$\n",
    "\n",
    "Hence, the total cost of filling the jobs should be less or equal than the budget available.\n",
    "\n",
    "\\begin{equation}\n",
    "(1x_{1,1} + 2x_{2,1} + 3x_{3,1}) \\; +\n",
    "\\end{equation}\n",
    "\n",
    "\\begin{equation}\n",
    "(1x_{1, 2} + 2x_{2, 2} + 3x_{3, 2}) \\; +\n",
    "\\end{equation}\n",
    "\n",
    "\\begin{equation}\n",
    "(1x_{1, 3} + 2x_{2, 3} + 3x_{3, 3}) \\leq 5\n",
    "\\end{equation}\n",
    "\n",
    "Each term in parenthesis in the budget constraint can be expressed as follows.\n",
    "\n",
    "\\begin{equation}\n",
    "(1x_{1,1} + 2x_{2,1} + 3x_{3,1}) = \\sum_{r \\in R} C_{r,1}x_{r,1}.\n",
    "\\end{equation}\n",
    "\n",
    "\\begin{equation}\n",
    "(1x_{1, 2} + 2x_{2, 2} + 3x_{3, 2}) = \\sum_{r \\in R} C_{r,2}x_{r,2}.\n",
    "\\end{equation}\n",
    "\n",
    "\\begin{equation}\n",
    "(1x_{1, 3} + 2x_{2, 3} + 3x_{3, 3}) = \\sum_{r \\in R} C_{r,3}x_{r,3}.\n",
    "\\end{equation}\n",
    "\n",
    "Therefore, the budget constraint can be concisely written as:\n",
    "\n",
    "\\begin{equation}\n",
    "\\sum_{j \\in J} \\sum_{r \\in R} C_{r,j}x_{r,j} \\leq B.\n",
    "\\end{equation}\n",
    "\n",
    "The ``Model.addConstr()`` method of the Gurobi/Python API defines the budget constraint of the ``Model`` object “m”. \n",
    "The first argument of this method, \"x.prod(costs)\", is the prod method and defines the LHS of the budget constraint. The $<=$ defines a less or equal constraint, and the budget amount available is the RHS of the constraint.\n",
    "This constraint is saying that the total cost of assigning resources to fill jobs requirements cannot exceed the budget available.\n",
    "The second argument is the name of this constraint."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {},
   "outputs": [],
   "source": [
    "budget = m.addConstr((x.prod(costs) <= budget), name='budget')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Objective function\n",
    "\n",
    "The objective function is similar to the RAP. The first term in the objective is the total matching score of the assignments. In this extension of the RAP, it is possible that not all jobs are filled; however, we want to heavily penalize this possibility. For this purpose, we have a second term in the objective function that takes the summation of the gap variables over all the jobs and multiply it by a big penalty $M$.\n",
    "\n",
    "Observe that the maximum value of a matching score is 100, and the value that we give to $M$ is 101. The rationale behind the value of $M$ is that having gaps heavily deteriorates the total matching scores value.\n",
    "\n",
    "Consequently, the objective function is to maximize the total matching score of the assignments minus the penalty associated of having gap variables with a value equal to 1.\n",
    "\n",
    "$$\n",
    "\\max \\; \\sum_{j \\; \\in \\; J} \\sum_{r \\; \\in \\; R} s_{r,j}x_{r,j} -M \\sum_{j \\in J} g_{j}\n",
    "$$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Penalty for not filling a job position\n",
    "M = 101"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Objective: maximize total matching score of assignments\n",
    "# Unfilled jobs are heavily penalized\n",
    "m.setObjective(x.prod(scores) - M*g.sum(), GRB.MAXIMIZE)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "metadata": {
    "scrolled": true
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Gurobi Optimizer version 10.0.2 build v10.0.2rc0 (win64)\n",
      "\n",
      "CPU model: 11th Gen Intel(R) Core(TM) i7-1165G7 @ 2.80GHz, instruction set [SSE2|AVX|AVX2|AVX512]\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.03 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": "markdown",
   "metadata": {},
   "source": [
    "The definition of the objective function includes the penalty of no filling jobs. However, we are interested in the optimal total matching score value when not all the jobs are filled. For this purpose, we need to compute the total matching score value using the matching score values $s_{r,j}$ and the assignment decision variables $x_{r,j}$."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "assign[Joe,Tester] 1.0\n",
      "assign[Monika,JavaDeveloper] 1.0\n",
      "Total matching score:  153.0\n"
     ]
    }
   ],
   "source": [
    "# Compute total matching score from assignment variables\n",
    "total_matching_score = 0\n",
    "for r, j in combinations:\n",
    "    if x[r, j].x > 1e-6:\n",
    "        print(x[r, j].varName, x[r, j].x) \n",
    "        total_matching_score += scores[r, j]*x[r, j].x\n",
    "\n",
    "print('Total matching score: ', total_matching_score)  "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Analysis"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Recall that the budget is $\\$5,000$, and the total  cost associated of allocating the three resources is $\\$6,000$. This means that there is not enough budget to allocate the three resources we have. Consequently, the Gurobi Optimizer must choose two resources to fill the jobs demand, leave one job unfilled, and maximize the total matching scores. Notice that the two top matching scores are 80% (Joe for the Tester job) and 73% (Monika for the Java Developer job). Also, notice that the lowest score is 13% (Carlos for the Architect job). Assigning Joe to the Tester job, Monika to the Java Developer job, and nobody to the Architect job costs $\\$5,000$  and yields a total matching score of 153. This is the optimal solution found by the Gurobi Optimizer."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Freeing default Gurobi environment\n"
     ]
    }
   ],
   "source": [
    "m.dispose()\n",
    "gp.disposeDefaultEnv()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Copyright © 2020 Gurobi Optimization, LLC"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3 (ipykernel)",
   "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.7"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}