integer_programming_ortools.ipynb

integer_programming_ortools.ipynb

{
  "cells": [
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "view-in-github",
        "colab_type": "text"
      },
      "source": [
        "<a href=\"https://colab.research.google.com/gist/leobarone/de9b7af6b4c8e5925c086f14057561ce/integer_programming_ortools.ipynb\" target=\"_parent\"><img src=\"https://colab.research.google.com/assets/colab-badge.svg\" alt=\"Open In Colab\"/></a>"
      ]
    },
    {
      "cell_type": "markdown",
      "id": "9510ed90-06ad-4994-b19c-43a55aebeaaf",
      "metadata": {
        "id": "9510ed90-06ad-4994-b19c-43a55aebeaaf"
      },
      "source": [
        "Import linear solver \"pywraplp\" from ortools."
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "id": "7a44f423-076b-4330-ba53-285663172d8d",
      "metadata": {
        "id": "7a44f423-076b-4330-ba53-285663172d8d"
      },
      "outputs": [],
      "source": [
        "from ortools.linear_solver import pywraplp"
      ]
    },
    {
      "cell_type": "markdown",
      "id": "11d31099-e41c-4b40-a243-f443270e89b7",
      "metadata": {
        "id": "11d31099-e41c-4b40-a243-f443270e89b7"
      },
      "source": [
        "Create a solver object."
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "id": "8db3eac1-8248-47f8-ad94-3c2094bb9e5e",
      "metadata": {
        "id": "8db3eac1-8248-47f8-ad94-3c2094bb9e5e"
      },
      "outputs": [],
      "source": [
        "# Create the solver with the SCIP backend.\n",
        "solver = pywraplp.Solver.CreateSolver('SCIP')"
      ]
    },
    {
      "cell_type": "markdown",
      "id": "6cc8f1df-ff65-4bc2-ac19-eac7d726c8ca",
      "metadata": {
        "id": "6cc8f1df-ff65-4bc2-ac19-eac7d726c8ca"
      },
      "source": [
        "Define a variable for infinity."
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "id": "c721638b-61c3-4291-bc7b-dd15647e73eb",
      "metadata": {
        "tags": [],
        "id": "c721638b-61c3-4291-bc7b-dd15647e73eb"
      },
      "outputs": [],
      "source": [
        "inf = solver.infinity()"
      ]
    },
    {
      "cell_type": "markdown",
      "id": "a6965075-669b-4dc8-9439-075ef2860282",
      "metadata": {
        "id": "a6965075-669b-4dc8-9439-075ef2860282"
      },
      "source": [
        "Define the 10 variables of the problem, $x_1$, $x_2$, $x_3$, $x_4$, $x_5$, $y_1$, $y_2$, $y_3$, $y_4$, $y_5$ as non-negative real numbers."
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "id": "d41d879d-c1f5-48dd-b0c2-b5c235aa862c",
      "metadata": {
        "id": "d41d879d-c1f5-48dd-b0c2-b5c235aa862c"
      },
      "outputs": [],
      "source": [
        "# Create the variables x1, x2 and x3.\n",
        "x1 = solver.IntVar(0., inf, 'x1')\n",
        "x2 = solver.IntVar(0., inf, 'x2')\n",
        "x3 = solver.IntVar(0., inf, 'x3')\n",
        "x4 = solver.IntVar(0., inf, 'x4')\n",
        "x5 = solver.IntVar(0., inf, 'x5')\n",
        "y1 = solver.IntVar(0., inf, 'y1')\n",
        "y2 = solver.IntVar(0., inf, 'y2')\n",
        "y3 = solver.IntVar(0., inf, 'y3')\n",
        "y4 = solver.IntVar(0., inf, 'y4')\n",
        "y5 = solver.IntVar(0., inf, 'y5')"
      ]
    },
    {
      "cell_type": "markdown",
      "id": "03bd6b68-ab72-4b3b-a724-a666c267161d",
      "metadata": {
        "id": "03bd6b68-ab72-4b3b-a724-a666c267161d"
      },
      "source": [
        "Write the seven linear constraints of the problem:\n",
        "\n",
        "$x_1 - 1500 * y_1 <= 0$\n",
        "\n",
        "$x_2 - 2250 * y_2 <= 0$\n",
        "\n",
        "$x_3 - 666.667 * y_3 <= 0$\n",
        "\n",
        "$x_4 - 1000 * y_4 <= 0$\n",
        "\n",
        "$x_5 - 500 * y_5 <= 0$\n",
        "\n",
        "$2 * x_1 + 1 * x_2 + 6 * x_3 + 4 * x_4 + 8 * x_5 <= 4000$\n",
        "\n",
        "$3 * x_1 + 2.5 * x_2 + 4 * x_3 + 4.5 * x_4 + 5.5 * x_5 <= 4500$"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "id": "3112f4d6-b96d-4768-8b70-2e1ca7cddf58",
      "metadata": {
        "id": "3112f4d6-b96d-4768-8b70-2e1ca7cddf58",
        "outputId": "f8733f67-5d36-4447-e68b-8b3be6b66ab6"
      },
      "outputs": [
        {
          "data": {
            "text/plain": [
              "<ortools.linear_solver.pywraplp.Constraint; proxy of <Swig Object of type 'operations_research::MPConstraint *' at 0x7f7739020c90> >"
            ]
          },
          "execution_count": 22,
          "metadata": {},
          "output_type": "execute_result"
        }
      ],
      "source": [
        "solver.Add(x1 - 1500 * y1 <= 0)\n",
        "solver.Add(x2 - 2250 * y2 <= 0)\n",
        "solver.Add(x3 - 666.667 * y3 <= 0)\n",
        "solver.Add(x4 - 1000 * y4 <= 0)\n",
        "solver.Add(x5 - 500 * y5 <= 0)\n",
        "solver.Add(2 * x1 + 1 * x2 + 6 * x3 + 4 * x4 + 8 * x5 <= 4000)\n",
        "solver.Add(3 * x1 + 2.5 * x2 + 4 * x3 + 4.5 * x4 + 5.5 * x5 <= 4500)"
      ]
    },
    {
      "cell_type": "markdown",
      "id": "b8a70178-0ee5-4079-be25-0d89b2dc382e",
      "metadata": {
        "id": "b8a70178-0ee5-4079-be25-0d89b2dc382e"
      },
      "source": [
        "Write the objective function of the problem to be maximized:\n",
        "\n",
        "$15 * x_1 + 30 * x_2 + 40 * x_3 + 40 * x_4 + 75 * x_5 - 1500 * y1 - 1200 * y_2 - 1600 * y_3 - 1500 * y_4 - 1600 * y_5$"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "id": "37db64fe-a8ec-4c21-b558-d9845d58483d",
      "metadata": {
        "id": "37db64fe-a8ec-4c21-b558-d9845d58483d"
      },
      "outputs": [],
      "source": [
        "solver.Maximize(15 * x1 + 30 * x2 + 40 * x3 + 40 * x4 + 75 * x5 - 1500 * y1 - 1200 * y2 - 1600 * y3 - 1500 * y4 - 1600 * y5)"
      ]
    },
    {
      "cell_type": "markdown",
      "id": "1dba4849-0c9c-4597-af5c-7729a9c2d64c",
      "metadata": {
        "id": "1dba4849-0c9c-4597-af5c-7729a9c2d64c"
      },
      "source": [
        "And, finally, solve it:"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "id": "e4292c8f-62b7-4350-8af3-c9b4fa996831",
      "metadata": {
        "id": "e4292c8f-62b7-4350-8af3-c9b4fa996831",
        "outputId": "da1d69ec-d093-408c-ab88-8cc1483dae94"
      },
      "outputs": [
        {
          "name": "stdout",
          "output_type": "stream",
          "text": [
            "Solution:\n",
            "Objective value = 54605.00000000001\n",
            "x1 = 0.0\n",
            "x2 = 966.0\n",
            "x3 = 0.0\n",
            "x4 = 0.0\n",
            "x5 = 379.0\n",
            "y1 = 0.0\n",
            "y2 = 1.0\n",
            "y3 = 0.0\n",
            "y4 = 0.0\n",
            "y5 = 1.0\n"
          ]
        }
      ],
      "source": [
        "solver.Solve()\n",
        "print('Solution:')\n",
        "print('Objective value =', solver.Objective().Value())\n",
        "print('x1 =', x1.solution_value())\n",
        "print('x2 =', x2.solution_value())\n",
        "print('x3 =', x3.solution_value())\n",
        "print('x4 =', x4.solution_value())\n",
        "print('x5 =', x5.solution_value())\n",
        "print('y1 =', y1.solution_value())\n",
        "print('y2 =', y2.solution_value())\n",
        "print('y3 =', y3.solution_value())\n",
        "print('y4 =', y4.solution_value())\n",
        "print('y5 =', y5.solution_value())"
      ]
    }
  ],
  "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.8.10"
    },
    "colab": {
      "name": "integer_programming_ortools.ipynb",
      "provenance": [],
      "include_colab_link": true
    }
  },
  "nbformat": 4,
  "nbformat_minor": 5
}