04: Google_OR_tools_Assignment_Problem.ipynb

{
  "nbformat": 4,
  "nbformat_minor": 0,
  "metadata": {
    "colab": {
      "name": "04_Google_OR-tools_Assignment Problem.ipynb",
      "provenance": [],
      "authorship_tag": "ABX9TyNeEVSieLMtD3EO6ZG/hcuD",
      "include_colab_link": true
    },
    "kernelspec": {
      "name": "python3",
      "display_name": "Python 3"
    },
    "language_info": {
      "name": "python"
    }
  },
  "cells": [
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "view-in-github",
        "colab_type": "text"
      },
      "source": [
        "<a href=\"https://colab.research.google.com/github/gulabpatel/LinearProgramming/blob/main/04%3A%20Google_OR_tools_Assignment_Problem.ipynb\" target=\"_parent\"><img src=\"https://colab.research.google.com/assets/colab-badge.svg\" alt=\"Open In Colab\"/></a>"
      ]
    },
    {
      "cell_type": "markdown",
      "source": [
        "In the example there are five workers (numbered 0-4) and four tasks (numbered 0-3). Note that there is one more worker than in the example in the Overview.\n",
        "\n",
        "The costs of assigning workers to tasks are shown in the following table.\n",
        "\n",
        "Worker\tTask 0\tTask 1\tTask 2\tTask 3<br>\n",
        "  0   \t90   \t80  \t75  \t70<br>\n",
        "  1\t    35  \t85  \t55  \t65<br>\n",
        "  2\t    125 \t95  \t90  \t95<br>\n",
        "  3\t    45  \t110 \t95\t  115<br>\n",
        "  4\t    50\t  100  \t90\t  100\n",
        "\n",
        "\n",
        "  The problem is to assign each worker to at most one task, with no two workers performing the same task, while minimizing the total cost. Since there are more workers than tasks, one worker will not be assigned a task."
      ],
      "metadata": {
        "id": "ko1xLlYK8nox"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "# !python -m pip install --upgrade --user -q ortools\n",
        "!pip install ortools"
      ],
      "metadata": {
        "id": "ZFFzolG08B_L"
      },
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "source": [
        "from ortools.linear_solver import pywraplp"
      ],
      "metadata": {
        "id": "vYsJ4xJp9Z0G"
      },
      "execution_count": 2,
      "outputs": []
    },
    {
      "cell_type": "code",
      "source": [
        "costs = [\n",
        "    [90, 80, 75, 70],\n",
        "    [35, 85, 55, 65],\n",
        "    [125, 95, 90, 95],\n",
        "    [45, 110, 95, 115],\n",
        "    [50, 100, 90, 100],\n",
        "]\n",
        "num_workers = len(costs)\n",
        "num_tasks = len(costs[0])"
      ],
      "metadata": {
        "id": "_D476QIt8E3c"
      },
      "execution_count": 3,
      "outputs": []
    },
    {
      "cell_type": "code",
      "source": [
        "# Create the mip solver with the SCIP backend.\n",
        "solver = pywraplp.Solver.CreateSolver('SCIP')"
      ],
      "metadata": {
        "id": "ZSZ1kyYU8UL2"
      },
      "execution_count": 4,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "source": [
        "##Create the variables"
      ],
      "metadata": {
        "id": "itrOlj1y-LTW"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "# x[i, j] is an array of 0-1 variables, which will be 1\n",
        "# if worker i is assigned to task j.\n",
        "x = {}\n",
        "for i in range(num_workers):\n",
        "    for j in range(num_tasks):\n",
        "        x[i, j] = solver.IntVar(0, 1, '')\n",
        "# x"
      ],
      "metadata": {
        "id": "Npu1agdK8eCC"
      },
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "source": [
        "##Create the constraints"
      ],
      "metadata": {
        "id": "Z5V9k7JI-N20"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "# Each worker is assigned to at most 1 task.\n",
        "for i in range(num_workers):\n",
        "    solver.Add(solver.Sum([x[i, j] for j in range(num_tasks)]) <= 1)\n",
        "\n",
        "# Each task is assigned to exactly one worker.\n",
        "for j in range(num_tasks):\n",
        "    solver.Add(solver.Sum([x[i, j] for i in range(num_workers)]) == 1)"
      ],
      "metadata": {
        "id": "YT-D5xchBn1B"
      },
      "execution_count": 7,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "source": [
        "#Create the objective function"
      ],
      "metadata": {
        "id": "p_gafodA-Zbw"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "objective_terms = []\n",
        "for i in range(num_workers):\n",
        "    for j in range(num_tasks):\n",
        "        objective_terms.append(costs[i][j] * x[i, j])\n",
        "solver.Minimize(solver.Sum(objective_terms))"
      ],
      "metadata": {
        "id": "TiGQl9xl37kB"
      },
      "execution_count": 11,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "source": [
        "#Invoke the solver"
      ],
      "metadata": {
        "id": "EsLhHvDq-kJN"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "status = solver.Solve()"
      ],
      "metadata": {
        "id": "P59hkxWm-oGl"
      },
      "execution_count": 12,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "source": [
        "#Print the solution"
      ],
      "metadata": {
        "id": "ibGfJ1S4-pF8"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "if status == pywraplp.Solver.OPTIMAL or status == pywraplp.Solver.FEASIBLE:\n",
        "    print(f'Total cost = {solver.Objective().Value()}\\n')\n",
        "    for i in range(num_workers):\n",
        "        for j in range(num_tasks):\n",
        "            # Test if x[i,j] is 1 (with tolerance for floating point arithmetic).\n",
        "            if x[i, j].solution_value() > 0.5:\n",
        "                print(f'Worker {i} assigned to task {j}.' +\n",
        "                      f' Cost: {costs[i][j]}')\n",
        "else:\n",
        "    print('No solution found.')"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "Lxk9jUuX-soP",
        "outputId": "b530563a-e358-46f0-e5c2-ece7bb991e54"
      },
      "execution_count": 16,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "Total cost = 265.0\n",
            "\n",
            "Worker 0 assigned to task 3. Cost: 70\n",
            "Worker 1 assigned to task 2. Cost: 55\n",
            "Worker 2 assigned to task 1. Cost: 95\n",
            "Worker 3 assigned to task 0. Cost: 45\n"
          ]
        }
      ]
    },
    {
      "cell_type": "markdown",
      "source": [
        "#CP SAT solution"
      ],
      "metadata": {
        "id": "amRLD8IL-_Te"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "from ortools.sat.python import cp_model\n",
        "\n",
        "def main():\n",
        "    # Data\n",
        "    costs = [\n",
        "        [90, 80, 75, 70],\n",
        "        [35, 85, 55, 65],\n",
        "        [125, 95, 90, 95],\n",
        "        [45, 110, 95, 115],\n",
        "        [50, 100, 90, 100],\n",
        "    ]\n",
        "    num_workers = len(costs)\n",
        "    num_tasks = len(costs[0])\n",
        "\n",
        "    # Model\n",
        "    model = cp_model.CpModel()\n",
        "\n",
        "    # Variables\n",
        "    x = []\n",
        "    for i in range(num_workers):\n",
        "        t = []\n",
        "        for j in range(num_tasks):\n",
        "            t.append(model.NewBoolVar(f'x[{i},{j}]'))\n",
        "        x.append(t)\n",
        "\n",
        "    # Constraints\n",
        "    # Each worker is assigned to at most one task.\n",
        "    for i in range(num_workers):\n",
        "        model.AddAtMostOne(x[i][j] for j in range(num_tasks))\n",
        "\n",
        "    # Each task is assigned to exactly one worker.\n",
        "    for j in range(num_tasks):\n",
        "        model.AddExactlyOne(x[i][j] for i in range(num_workers))\n",
        "\n",
        "    # Objective\n",
        "    objective_terms = []\n",
        "    for i in range(num_workers):\n",
        "        for j in range(num_tasks):\n",
        "            objective_terms.append(costs[i][j] * x[i][j])\n",
        "    model.Minimize(sum(objective_terms))\n",
        "\n",
        "    # Solve\n",
        "    solver = cp_model.CpSolver()\n",
        "    status = solver.Solve(model)\n",
        "\n",
        "    # Print solution.\n",
        "    if status == cp_model.OPTIMAL or status == cp_model.FEASIBLE:\n",
        "        print(f'Total cost = {solver.ObjectiveValue()}')\n",
        "        print()\n",
        "        for i in range(num_workers):\n",
        "            for j in range(num_tasks):\n",
        "                if solver.BooleanValue(x[i][j]):\n",
        "                    print(\n",
        "                        f'Worker {i} assigned to task {j} Cost = {costs[i][j]}')\n",
        "    else:\n",
        "        print('No solution found.')\n",
        "\n",
        "\n",
        "if __name__ == '__main__':\n",
        "    main()"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "9fARlJA2-5rF",
        "outputId": "3db3d0b8-ca6b-49d4-ed16-0b6eb2ef810d"
      },
      "execution_count": 17,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "Total cost = 265.0\n",
            "\n",
            "Worker 0 assigned to task 3 Cost = 70\n",
            "Worker 1 assigned to task 2 Cost = 55\n",
            "Worker 2 assigned to task 1 Cost = 95\n",
            "Worker 3 assigned to task 0 Cost = 45\n"
          ]
        }
      ]
    }
  ]
}