1_Introduction_to_Linear_Programming.ipynb

{
  "nbformat": 4,
  "nbformat_minor": 0,
  "metadata": {
    "colab": {
      "name": "1. Introduction to Linear Programming.ipynb",
      "provenance": [],
      "collapsed_sections": [],
      "authorship_tag": "ABX9TyMlv+2eBVwWBjLrSDwHaHr5",
      "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/mlabonne/Linear-Programming-Course/blob/main/1_Introduction_to_Linear_Programming.ipynb\" target=\"_parent\"><img src=\"https://colab.research.google.com/assets/colab-badge.svg\" alt=\"Open In Colab\"/></a>"
      ]
    },
    {
      "cell_type": "markdown",
      "source": [
        "# Introduction to Linear Programming\n",
        "\n",
        "> Chapter 1 of the [Linear Programming Course](https://github.com/mlabonne/Linear-Programming-Course)\n",
        "\n",
        "❤️ Created by [@maximelabonne](https://twitter.com/maximelabonne).\n",
        "\n",
        "Companion notebook to execute the code from the following article: https://mlabonne.github.io/blog/linearoptimization/\n",
        "\n",
        "<br/>\n",
        "\n",
        "| Unit | 🌾Food | 🪵Wood | 🪙Gold | 💪Power |\n",
        "| :--- | :---: | :---: | :---: | :---: |\n",
        "| 🗡️Swordsman | 60 | 20 | 0 | 70 |\n",
        "| 🏹Bowman | 80 | 10 | 40 | 95 |\n",
        "| 🐎Horseman | 140 | 0 |100 | 230 |\n",
        "\n",
        "<br/>\n",
        "\n",
        "**Goal**: optimizing the power of an army composed of swordsmen, bowmen, and horsemen with 1200 🌾food, 800 🪵wood, and 600 🪙gold."
      ],
      "metadata": {
        "id": "2ywEZ_RkknQC"
      }
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "id": "ZK0c0hhQklGb"
      },
      "outputs": [],
      "source": [
        "!python -m pip install --upgrade --user -q ortools"
      ]
    },
    {
      "cell_type": "markdown",
      "source": [
        "# Setup\n",
        "\n",
        "If the following cell fails, click on `Runtime > Restart and run all`."
      ],
      "metadata": {
        "id": "94uu3qEbFn_X"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "# Import OR-Tools' wrapper for linear solvers\n",
        "from ortools.linear_solver import pywraplp\n",
        "\n",
        "# Create a linear solver using the GLOP backend\n",
        "solver = pywraplp.Solver('Maximize army power', pywraplp.Solver.GLOP_LINEAR_PROGRAMMING)"
      ],
      "metadata": {
        "id": "l4RYui9hxcJG"
      },
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "source": [
        "# 1. Declare variables to optimize\n",
        "\n",
        "We have three variables: the numbers of swordsmen, bowmen, and horsemen."
      ],
      "metadata": {
        "id": "PuX75dGGFpXP"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "# Create the variables we want to optimize\n",
        "swordsmen = solver.IntVar(0, solver.infinity(), 'swordsmen')\n",
        "bowmen = solver.IntVar(0, solver.infinity(), 'bowmen')\n",
        "horsemen = solver.IntVar(0, solver.infinity(), 'horsemen')"
      ],
      "metadata": {
        "id": "7Oqc6nBg0ea2"
      },
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "source": [
        "# 2. Declare constraints\n",
        "\n",
        "We have three constraints: the food, wood, and gold spent cannot exceed our current resources (1200 food, 800 wood, and 600 gold)."
      ],
      "metadata": {
        "id": "6J2Xrn-VFrOT"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "# Add constraints for each resource\n",
        "solver.Add(swordsmen*60 + bowmen*80 + horsemen*140 <= 1200) # Food\n",
        "solver.Add(swordsmen*20 + bowmen*10 <= 800)                 # Wood\n",
        "solver.Add(bowmen*40 + horsemen*100 <= 600)                 # Gold"
      ],
      "metadata": {
        "id": "jtD0ZPevY5CO",
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "outputId": "8d714ae5-1feb-45f1-d0b3-1dd1162648d0"
      },
      "execution_count": null,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "<ortools.linear_solver.pywraplp.Constraint; proxy of <Swig Object of type 'operations_research::MPConstraint *' at 0x7f83da0ebc90> >"
            ]
          },
          "metadata": {},
          "execution_count": 4
        }
      ]
    },
    {
      "cell_type": "markdown",
      "source": [
        "# 3. Declare objective\n",
        "\n",
        "The goal is to maximize the power of the army, which the sum of the power of each unit."
      ],
      "metadata": {
        "id": "MpRvec7AFtYo"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "# Maximize the objective function\n",
        "solver.Maximize(swordsmen*70 + bowmen*95 + horsemen*230)"
      ],
      "metadata": {
        "id": "HLkXypIKY8Bm"
      },
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "source": [
        "# Optimize!"
      ],
      "metadata": {
        "id": "Y3B1e_f2Fz8D"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "# Solve problem\n",
        "status = solver.Solve()\n",
        "\n",
        "# If an optimal solution has been found, print results\n",
        "if status == pywraplp.Solver.OPTIMAL:\n",
        "  print('================= Solution =================')\n",
        "  print(f'Solved in {solver.wall_time():.2f} milliseconds in {solver.iterations()} iterations')\n",
        "  print()\n",
        "  print(f'Optimal power = {solver.Objective().Value()} 💪power')\n",
        "  print('Army:')\n",
        "  print(f' - 🗡️Swordsmen = {swordsmen.solution_value()}')\n",
        "  print(f' - 🏹Bowmen = {bowmen.solution_value()}')\n",
        "  print(f' - 🐎Horsemen = {horsemen.solution_value()}')\n",
        "else:\n",
        "  print('The solver could not find an optimal solution.')"
      ],
      "metadata": {
        "id": "ddA-aNJMY-V6",
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "outputId": "252fe084-42f0-41b3-c164-f3d3b8ebf909"
      },
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "================= Solution =================\n",
            "Solved in 49.00 milliseconds in 2 iterations\n",
            "\n",
            "Optimal power = 1800.0 💪power\n",
            "Army:\n",
            " - 🗡️Swordsmen = 6.0000000000000036\n",
            " - 🏹Bowmen = 0.0\n",
            " - 🐎Horsemen = 5.999999999999999\n"
          ]
        }
      ]
    }
  ]
}