L7E2.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Assignment 7 - Exercise 1\n",
    "Bruno Kiyoshi Ynumaru - 201805995"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "collapsed": true,
    "jupyter": {
     "outputs_hidden": true,
     "source_hidden": true
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Uma empresa precisa atribuir 4 tarefas a 4 trabalhadores. O custo em desempenhar a tarefa é uma\n",
      "função das habilidades dos trabalhadores. A tabela abaixo resume o custo de cada atribuição. Cada\n",
      "tarefa precisa de apenas um trabalhador. O trabalhador 1 não pode executar a tarefa 3, e o trabalhador\n",
      "3 não pode executar a tarefa 4. Determine a atribuição ótima das tarefas.\n",
      "\n",
      "\n"
     ]
    }
   ],
   "source": [
    "prob_statement = \"\"\"Uma empresa precisa atribuir 4 tarefas a 4 trabalhadores. O custo em desempenhar a tarefa ´e uma\n",
    "fun¸c˜ao das habilidades dos trabalhadores. A tabela abaixo resume o custo de cada atribui¸c˜ao. Cada\n",
    "tarefa precisa de apenas um trabalhador. O trabalhador 1 n˜ao pode executar a tarefa 3, e o trabalhador\n",
    "3 n˜ao pode executar a tarefa 4. Determine a atribui¸c˜ao ´otima das tarefas.\n",
    "\n",
    "\"\"\"\n",
    "def fix_statement(str_statement):\n",
    "    list_replacements = [(\"¸c\", \"ç\"), \n",
    "                         (\"´a\", \"á\"),\n",
    "                         (\"´e\", \"é\"),\n",
    "                         (\"´ı\", \"í\"),\n",
    "                         (\"´o\", \"ó\"),\n",
    "                         (\"´u\", \"ú\"),\n",
    "                         (\"˜a\", \"ã\"),\n",
    "                         (\"˜o\", \"õ\"),\n",
    "                         (\"ˆe\", \"ê\"),\n",
    "                         (\"$\", \"\\\\\\$\")]\n",
    "    for replacement in list_replacements:\n",
    "        str_statement = str_statement.replace(replacement[0], replacement[1])\n",
    "    return str_statement\n",
    "prob_statement = fix_statement(prob_statement)\n",
    "print(prob_statement)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Uma empresa precisa atribuir 4 tarefas a 4 trabalhadores. O custo em desempenhar a tarefa é uma\n",
    "função das habilidades dos trabalhadores. A tabela abaixo resume o custo de cada atribuição. Cada\n",
    "tarefa precisa de apenas um trabalhador. O trabalhador 1 não pode executar a tarefa 3, e o trabalhador\n",
    "3 não pode executar a tarefa 4. Determine a atribuição ótima das tarefas.\n",
    "\n",
    "|Trabalhador| Tarefa 1 | Tarefa 2 | Tarefa 3 | Tarefa 4 |\n",
    "| --- | --- | --- | --- | --- |\n",
    "|1| \\\\$50| \\\\$50|-| \\\\$20|\n",
    "|2| \\\\$70 |\\\\$40 |\\\\$20 |\\\\$30 |\n",
    "|3| \\\\$90| \\\\$30| \\\\$50|-|\n",
    "|4| \\\\$70| \\\\$20| \\\\$60|\\\\$70|"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {},
   "outputs": [],
   "source": [
    "import gurobipy as gp\n",
    "from gurobipy import GRB, Model"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Create a new model\n",
    "m = Model(\"CELESC\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Create variables\n",
    "x1_T1 = m.addVar(lb=0, vtype=GRB.INTEGER, name=\"Worker 1 does Task 1\")\n",
    "x1_T2 = m.addVar(lb=0, vtype=GRB.INTEGER, name=\"Worker 1 does Task 2\")\n",
    "x1_T3 = m.addVar(lb=0, vtype=GRB.INTEGER, name=\"Worker 1 does Task 3\")\n",
    "x1_T4 = m.addVar(lb=0, vtype=GRB.INTEGER, name=\"Worker 1 does Task 4\")\n",
    "\n",
    "x2_T1 = m.addVar(lb=0, vtype=GRB.INTEGER, name=\"Worker 2 does Task 1\")\n",
    "x2_T2 = m.addVar(lb=0, vtype=GRB.INTEGER, name=\"Worker 2 does Task 2\")\n",
    "x2_T3 = m.addVar(lb=0, vtype=GRB.INTEGER, name=\"Worker 2 does Task 3\")\n",
    "x2_T4 = m.addVar(lb=0, vtype=GRB.INTEGER, name=\"Worker 2 does Task 4\")\n",
    "\n",
    "x3_T1 = m.addVar(lb=0, vtype=GRB.INTEGER, name=\"Worker 3 does Task 1\")\n",
    "x3_T2 = m.addVar(lb=0, vtype=GRB.INTEGER, name=\"Worker 3 does Task 2\")\n",
    "x3_T3 = m.addVar(lb=0, vtype=GRB.INTEGER, name=\"Worker 3 does Task 3\")\n",
    "x3_T4 = m.addVar(lb=0, vtype=GRB.INTEGER, name=\"Worker 3 does Task 4\")\n",
    "\n",
    "x4_T1 = m.addVar(lb=0, vtype=GRB.INTEGER, name=\"Worker 4 does Task 1\")\n",
    "x4_T2 = m.addVar(lb=0, vtype=GRB.INTEGER, name=\"Worker 4 does Task 2\")\n",
    "x4_T3 = m.addVar(lb=0, vtype=GRB.INTEGER, name=\"Worker 4 does Task 3\")\n",
    "x4_T4 = m.addVar(lb=0, vtype=GRB.INTEGER, name=\"Worker 4 does Task 4\")\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {},
   "outputs": [],
   "source": [
    "m.setObjective(x1_T1 * 50 + x1_T2 * 50 + x1_T3 * 999999999 + x1_T4 * 20 +\n",
    "               x2_T1 * 70 + x2_T2 * 40 + x2_T3 * 20 + x2_T4 * 30 +\n",
    "               x3_T1 * 90 + x3_T2 * 30 + x3_T3 * 50 + x3_T4 * 9999999999 +\n",
    "               x4_T1 * 70 + x4_T2 * 20 + x4_T3 * 60 + x4_T4 * 70,\n",
    "               GRB.MINIMIZE)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Gurobi Optimizer version 9.1.1 build v9.1.1rc0 (win64)\n",
      "Thread count: 4 physical cores, 8 logical processors, using up to 8 threads\n",
      "Optimize a model with 8 rows, 16 columns and 32 nonzeros\n",
      "Model fingerprint: 0x597825c0\n",
      "Variable types: 0 continuous, 16 integer (0 binary)\n",
      "Coefficient statistics:\n",
      "  Matrix range     [1e+00, 1e+00]\n",
      "  Objective range  [2e+01, 1e+10]\n",
      "  Bounds range     [0e+00, 0e+00]\n",
      "  RHS range        [1e+00, 1e+00]\n",
      "Warning: Model contains large objective coefficients\n",
      "         Consider reformulating model or setting NumericFocus parameter\n",
      "         to avoid numerical issues.\n",
      "Found heuristic solution: objective 230.0000000\n",
      "Presolve removed 0 rows and 2 columns\n",
      "Presolve time: 0.01s\n",
      "Presolved: 8 rows, 14 columns, 28 nonzeros\n",
      "Variable types: 0 continuous, 14 integer (14 binary)\n",
      "\n",
      "Root relaxation: objective 1.400000e+02, 7 iterations, 0.00 seconds\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     140.0000000  140.00000  0.00%     -    0s\n",
      "\n",
      "Explored 0 nodes (7 simplex iterations) in 0.05 seconds\n",
      "Thread count was 8 (of 8 available processors)\n",
      "\n",
      "Solution count 2: 140 230 \n",
      "\n",
      "Optimal solution found (tolerance 1.00e-04)\n",
      "Best objective 1.400000000000e+02, best bound 1.400000000000e+02, gap 0.0000%\n"
     ]
    }
   ],
   "source": [
    "# Add constraints\n",
    "m.addConstr(x1_T1 + x2_T1 + x3_T1 + x4_T1 == 1, 'One person must perform task 1')\n",
    "m.addConstr(x1_T2 + x2_T2 + x3_T2 + x4_T2 == 1, 'One person must perform task 2')\n",
    "m.addConstr(x1_T3 + x2_T3 + x3_T3 + x4_T3 == 1, 'One person must perform task 3')\n",
    "m.addConstr(x1_T4 + x2_T4 + x3_T4 + x4_T4 == 1, 'One person must perform task 4')\n",
    "\n",
    "m.addConstr(x1_T1 + x1_T2 + x1_T3 + x1_T4 == 1, 'Worker 1 can only perform 1 task')\n",
    "m.addConstr(x2_T1 + x2_T2 + x2_T3 + x2_T4 == 1, 'Worker 1 can only perform 1 task')\n",
    "m.addConstr(x3_T1 + x3_T2 + x3_T3 + x3_T4 == 1, 'Worker 1 can only perform 1 task')\n",
    "m.addConstr(x4_T1 + x4_T2 + x4_T3 + x4_T4 == 1, 'Worker 1 can only perform 1 task')\n",
    "m.optimize()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Worker 1 does Task 1, 0.0\n",
      "Worker 1 does Task 2, -0.0\n",
      "Worker 1 does Task 3, 0.0\n",
      "Worker 1 does Task 4, 1.0\n",
      "Worker 2 does Task 1, -0.0\n",
      "Worker 2 does Task 2, -0.0\n",
      "Worker 2 does Task 3, 1.0\n",
      "Worker 2 does Task 4, 0.0\n",
      "Worker 3 does Task 1, -0.0\n",
      "Worker 3 does Task 2, 1.0\n",
      "Worker 3 does Task 3, -0.0\n",
      "Worker 3 does Task 4, 0.0\n",
      "Worker 4 does Task 1, 1.0\n",
      "Worker 4 does Task 2, 0.0\n",
      "Worker 4 does Task 3, -0.0\n",
      "Worker 4 does Task 4, -0.0\n",
      "Obj: 140.0\n"
     ]
    }
   ],
   "source": [
    "for v in m.getVars():\n",
    "    print(f'{v.varName}, {v.x}')\n",
    "\n",
    "print(f'Obj: {m.objVal}')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.8.5"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}