2_Integer_vs_Linear_Programming.ipynb

{
  "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/2_Integer_vs_Linear_Programming.ipynb\" target=\"_parent\"><img src=\"https://colab.research.google.com/assets/colab-badge.svg\" alt=\"Open In Colab\"/></a>"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "5kf_NODHE9yc"
      },
      "source": [
        "# Integer vs. Linear Programming\n",
        "\n",
        "> Chapter 2 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://towardsdatascience.com/integer-programming-vs-linear-programming-in-python-f1be5bb4e60e"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 1,
      "metadata": {
        "id": "ZK0c0hhQklGb"
      },
      "outputs": [],
      "source": [
        "!python -m pip install --upgrade --user -q ortools"
      ]
    },
    {
      "cell_type": "markdown",
      "source": [
        "# MIP solution with CBC\n",
        "\n",
        "The goal is to maximize the army with the following resources: 1200 food, 800 wood, 600 gold.\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",
        "If the following cell fails, click on `Runtime > Restart and run all`."
      ],
      "metadata": {
        "id": "xVJzzODwFX7c"
      }
    },
    {
      "cell_type": "code",
      "execution_count": 2,
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "Dvxq9hyCk8uW",
        "outputId": "08ae1162-c5dd-43b3-ec22-e13ed3a3417e"
      },
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "================= Solution =================\n",
            "Solved in 4.00 milliseconds in 0 iterations\n",
            "\n",
            "Optimal value = 1800.0 💪power\n",
            "Army:\n",
            " - 🗡️Swordsmen = 6.0\n",
            " - 🏹Bowmen = 0.0\n",
            " - 🐎Horsemen = 6.0\n"
          ]
        }
      ],
      "source": [
        "# Import OR-Tools wrapper for linear programming\n",
        "from ortools.linear_solver import pywraplp\n",
        "\n",
        "# Create the linear solver using the CBC backend\n",
        "solver = pywraplp.Solver('Maximize army power', pywraplp.Solver.CBC_MIXED_INTEGER_PROGRAMMING)\n",
        "\n",
        "# 1. 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')\n",
        "\n",
        "# 2. Add constraints for each resource\n",
        "solver.Add(swordsmen*60 + bowmen*80 + horsemen*140 <= 1200)\n",
        "solver.Add(swordsmen*20 + bowmen*10 <= 800)\n",
        "solver.Add(bowmen*40 + horsemen*100 <= 600)\n",
        "\n",
        "# 3. Maximize the objective function\n",
        "solver.Maximize(swordsmen*70 + bowmen*95 + horsemen*230)\n",
        "\n",
        "# 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 value = {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.')"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "vHTmOQzUK295"
      },
      "source": [
        "# Abstract model as a Python function\n",
        "\n",
        "Same problem but with a function and parameters instead of a static model."
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 3,
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "qR-fbnruehR4",
        "outputId": "6f0ebc4c-c8b7-4bbc-dfd0-fc565cc032a3"
      },
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "================= Solution =================\n",
            "Solved in 3.00 milliseconds in 0 iterations\n",
            "\n",
            "Optimal value = 1800.0 💪power\n",
            "Army:\n",
            " - 🗡️Swordsmen = 6.0\n",
            " - 🏹Bowmen = 0.0\n",
            " - 🐎Horsemen = 6.0\n"
          ]
        }
      ],
      "source": [
        "# Inputs\n",
        "UNITS = ['🗡️Swordsmen', '🏹Bowmen', '🐎Horsemen']\n",
        "\n",
        "DATA = [[60, 20, 0, 70],\n",
        "        [80, 10, 40, 95],\n",
        "        [140, 0, 100, 230]]\n",
        "\n",
        "RESOURCES = [1200, 800, 600]\n",
        "\n",
        "\n",
        "def solve_army(UNITS, DATA, RESOURCES):\n",
        "    # Create the linear solver using the CBC backend\n",
        "    solver = pywraplp.Solver('Maximize army power', pywraplp.Solver.CBC_MIXED_INTEGER_PROGRAMMING)\n",
        "\n",
        "    # 1. Create the variables we want to optimize\n",
        "    units = [solver.IntVar(0, solver.infinity(), unit) for unit in UNITS]\n",
        "\n",
        "    # 2. Add constraints for each resource\n",
        "    for r, _ in enumerate(RESOURCES):\n",
        "      solver.Add(sum(DATA[u][r] * units[u] for u, _ in enumerate(units)) <= RESOURCES[r])\n",
        "\n",
        "    # 3. Maximize the objective function\n",
        "    solver.Maximize(sum(DATA[u][-1] * units[u] for u, _ in enumerate(units)))\n",
        "\n",
        "    # 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 value = {solver.Objective().Value()} 💪power')\n",
        "      print('Army:')\n",
        "      for u, _ in enumerate(units):\n",
        "        print(f' - {units[u].name()} = {units[u].solution_value()}')\n",
        "    else:\n",
        "      print('The solver could not find an optimal solution.')\n",
        "\n",
        "solve_army(UNITS, DATA, RESOURCES)"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "qj6lzFPsT6MS"
      },
      "source": [
        "# Optimize a new problem\n",
        "\n",
        "The goal is to maximize the power of the army with the following resources: 183000 food, 90512 wood, 80150 gold.\n",
        "\n",
        "<br/>\n",
        "\n",
        "| Unit | 🌾Food | 🪵Wood | 🪙Gold | 💪Attack | ❤️Health\n",
        "| :--- | :---: | :---: | :---: | :---: | :---: |\n",
        "| 🗡️Swordsman      | 60  | 20  | 0   | 6   | 70 |\n",
        "| 🛡️Man-at-arms    | 100 | 0   | 20  | 12  | 155 |\n",
        "| 🏹Bowman         | 30  | 50  | 0   | 5   | 70 |\n",
        "| ❌Crossbowman    | 80  | 0   | 40  | 12  | 80 |\n",
        "| 🔫Handcannoneer  | 120 | 0   | 120 | 35  | 150 |\n",
        "| 🐎Horseman       | 100 | 20  | 0   | 9   | 125 |\n",
        "| ♞Knight          | 140 | 0   | 100 | 24  | 230 | \n",
        "| 🐏Battering ram  | 0   | 300 | 0   | 200 | 700 |\n",
        "| 🎯Springald      | 0   | 250 | 250 | 30 | 200 |\n",
        "\n",
        "</br>"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 4,
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "Y2EUFqCETvLZ",
        "outputId": "f5f36d84-961d-4637-8625-21c0a47a2fab"
      },
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "================= Solution =================\n",
            "Solved in 113.00 milliseconds in 412 iterations\n",
            "\n",
            "Optimal value = 1393145.0 💪power\n",
            "Army:\n",
            " - 🗡️Swordsmen = 2.0\n",
            " - 🛡️Men-at-arms = 1283.0\n",
            " - 🏹Bowmen = 3.0\n",
            " - ❌Crossbowmen = 0.0\n",
            " - 🔫Handcannoneers = 454.0\n",
            " - 🐎Horsemen = 0.0\n",
            " - ♞Knights = 0.0\n",
            " - 🐏Battering rams = 301.0\n",
            " - 🎯Springalds = 0.0\n",
            " - 🪨Mangonels = 0.0\n"
          ]
        }
      ],
      "source": [
        "UNITS = [\n",
        "    '🗡️Swordsmen',\n",
        "    '🛡️Men-at-arms',\n",
        "    '🏹Bowmen',\n",
        "    '❌Crossbowmen',\n",
        "    '🔫Handcannoneers',\n",
        "    '🐎Horsemen',\n",
        "    '♞Knights',\n",
        "    '🐏Battering rams',\n",
        "    '🎯Springalds',\n",
        "    '🪨Mangonels',\n",
        "]\n",
        "\n",
        "DATA = [\n",
        "    [60, 20, 0, 6, 70],\n",
        "    [100, 0, 20, 12, 155],\n",
        "    [30, 50, 0, 5, 70],\n",
        "    [80, 0, 40, 12, 80],\n",
        "    [120, 0, 120, 35, 150],\n",
        "    [100, 20, 0, 9, 125],\n",
        "    [140, 0, 100, 24, 230],\n",
        "    [0, 300, 0, 200, 700],\n",
        "    [0, 250, 250, 30, 200],\n",
        "    [0, 400, 200, 12*3, 240]\n",
        "]\n",
        "\n",
        "RESOURCES = [183000, 90512, 80150]\n",
        "\n",
        "\n",
        "def solve_army(UNITS, DATA, RESOURCES):\n",
        "  # Create the linear solver using the CBC backend\n",
        "  solver = pywraplp.Solver('Maximize army power', pywraplp.Solver.CBC_MIXED_INTEGER_PROGRAMMING)\n",
        "\n",
        "  # 1. Create the variables we want to optimize\n",
        "  units = [solver.IntVar(0, solver.infinity(), unit) for unit in UNITS]\n",
        "\n",
        "  # 2. Add constraints for each resource\n",
        "  for r, _ in enumerate(RESOURCES):\n",
        "    solver.Add(sum(DATA[u][r] * units[u] for u, _ in enumerate(units)) <= RESOURCES[r])\n",
        "\n",
        "  # 3. Maximize the new objective function\n",
        "  solver.Maximize(sum((10*DATA[u][-2] + DATA[u][-1]) * units[u] for u, _ in enumerate(units)))\n",
        "\n",
        "  # 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 value = {solver.Objective().Value()} 💪power')\n",
        "    print('Army:')\n",
        "    for u, _ in enumerate(units):\n",
        "      print(f' - {units[u].name()} = {units[u].solution_value()}')\n",
        "  else:\n",
        "    print('The solver could not find an optimal solution.')\n",
        "\n",
        "solve_army(UNITS, DATA, RESOURCES)"
      ]
    },
    {
      "cell_type": "markdown",
      "source": [
        "# Minimize resource consumption\n",
        "\n",
        "The goal is to minimize the resources that are used to get an army power >= 1,000,001."
      ],
      "metadata": {
        "id": "8HEf61kAGQZ-"
      }
    },
    {
      "cell_type": "code",
      "execution_count": 10,
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "nz5244z9nBYw",
        "outputId": "ad6c57ff-4d59-4641-8a38-8497027bbff7"
      },
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "================= Solution =================\n",
            "Solved in 3.00 milliseconds in 0 iterations\n",
            "\n",
            "Optimal value = 111300.0 🌾🪵🪙resources\n",
            "Power = 💪1001700.0\n",
            "Army:\n",
            " - 🗡️Swordsmen = 0.0\n",
            " - 🛡️Men-at-arms = 0.0\n",
            " - 🏹Bowmen = 0.0\n",
            " - ❌Crossbowmen = 0.0\n",
            " - 🔫Handcannoneers = 0.0\n",
            " - 🐎Horsemen = 0.0\n",
            " - ♞Knights = 0.0\n",
            " - 🐏Battering rams = 371.0\n",
            " - 🎯Springalds = 0.0\n",
            " - 🪨Mangonels = 0.0\n",
            "\n",
            "Resources:\n",
            " - 🌾Food = 0.0\n",
            " - 🪵Wood = 111300.0\n",
            " - 🪙Gold = 0.0\n"
          ]
        }
      ],
      "source": [
        "def solve_army(UNITS, DATA, RESOURCES):\n",
        "  # Create the linear solver using the CBC backend\n",
        "  solver = pywraplp.Solver('Minimize resource consumption', pywraplp.Solver.CBC_MIXED_INTEGER_PROGRAMMING)\n",
        "\n",
        "  # 1. Create the variables we want to optimize\n",
        "  units = [solver.IntVar(0, solver.infinity(), unit) for unit in UNITS]\n",
        "\n",
        "  # 2. Add power constraint\n",
        "  solver.Add(sum((10 * DATA[u][-2] + DATA[u][-1]) * units[u] for u, _ in enumerate(units)) >= 1000001)\n",
        "\n",
        "  # 3. Minimize the objective function\n",
        "  solver.Minimize(sum((DATA[u][0] + DATA[u][1] + DATA[u][2]) * units[u] for u, _ in enumerate(units)))\n",
        "\n",
        "  # 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",
        "\n",
        "    power = sum((10 * DATA[u][-2] + DATA[u][-1]) * units[u].solution_value() for u, _ in enumerate(units))\n",
        "    print(f'Optimal value = {solver.Objective().Value()} 🌾🪵🪙resources')\n",
        "    print(f'Power = 💪{power}')\n",
        "    print('Army:')\n",
        "    for u, _ in enumerate(units):\n",
        "      print(f' - {units[u].name()} = {units[u].solution_value()}')\n",
        "    print()\n",
        "\n",
        "    food = sum((DATA[u][0]) * units[u].solution_value() for u, _ in enumerate(units))\n",
        "    wood = sum((DATA[u][1]) * units[u].solution_value() for u, _ in enumerate(units))\n",
        "    gold = sum((DATA[u][2]) * units[u].solution_value() for u, _ in enumerate(units))\n",
        "    print('Resources:')\n",
        "    print(f' - 🌾Food = {food}')\n",
        "    print(f' - 🪵Wood = {wood}')\n",
        "    print(f' - 🪙Gold = {gold}')\n",
        "  else:\n",
        "    print('The solver could not find an optimal solution.')\n",
        "\n",
        "solve_army(UNITS, DATA, RESOURCES)"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "Qxeyd7vV3YmH"
      },
      "source": [
        "# Minimize resource consumption + limited resources\n",
        "\n",
        "The goal is to minimize the resources that are used to get an army power > 1,000,00 but the resources cannot exceed: 183000 food, 90512 wood, 80150 gold."
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 6,
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "lyi0eVvu1I8Q",
        "outputId": "3b7a1b1d-42b0-4e9d-e7f9-5993e1c275d2"
      },
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "================= Solution =================\n",
            "Solved in 31.00 milliseconds in 1 iterations\n",
            "\n",
            "Optimal value = 172100.0 🌾🪵🪙resources\n",
            "Power = 💪1000105.0\n",
            "Army:\n",
            " - 🗡️Swordsmen = 1.0\n",
            " - 🛡️Men-at-arms = 681.0\n",
            " - 🏹Bowmen = 0.0\n",
            " - ❌Crossbowmen = 0.0\n",
            " - 🔫Handcannoneers = 0.0\n",
            " - 🐎Horsemen = 0.0\n",
            " - ♞Knights = 0.0\n",
            " - 🐏Battering rams = 301.0\n",
            " - 🎯Springalds = 0.0\n",
            " - 🪨Mangonels = 0.0\n",
            "\n",
            "Resources:\n",
            " - 🌾Food = 68160.0\n",
            " - 🪵Wood = 90320.0\n",
            " - 🪙Gold = 13620.0\n"
          ]
        }
      ],
      "source": [
        "def solve_army(UNITS, DATA, RESOURCES):\n",
        "  # Create the linear solver using the CBC backend\n",
        "  solver = pywraplp.Solver('Minimize resource consumption', pywraplp.Solver.CBC_MIXED_INTEGER_PROGRAMMING)\n",
        "\n",
        "  # 1. Create the variables we want to optimize\n",
        "  units = [solver.IntVar(0, solver.infinity(), unit) for unit in UNITS]\n",
        "\n",
        "  # 2. Add constraints for each resource\n",
        "  for r, _ in enumerate(RESOURCES):\n",
        "    solver.Add(sum((10 * DATA[u][-2] + DATA[u][-1]) * units[u] for u, _ in enumerate(units)) >= 1000001)\n",
        "\n",
        "  # Old constraints for limited resources\n",
        "  for r, _ in enumerate(RESOURCES):\n",
        "    solver.Add(sum(DATA[u][r] * units[u] for u, _ in enumerate(units)) <= RESOURCES[r])\n",
        "\n",
        "  # 3. Minimize the objective function\n",
        "  solver.Minimize(sum((DATA[u][0] + DATA[u][1] + DATA[u][2]) * units[u] for u, _ in enumerate(units)))\n",
        "\n",
        "  # 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",
        "\n",
        "    power = sum((10 * DATA[u][-2] + DATA[u][-1]) * units[u].solution_value() for u, _ in enumerate(units))\n",
        "    print(f'Optimal value = {solver.Objective().Value()} 🌾🪵🪙resources')\n",
        "    print(f'Power = 💪{power}')\n",
        "    print('Army:')\n",
        "    for u, _ in enumerate(units):\n",
        "      print(f' - {units[u].name()} = {units[u].solution_value()}')\n",
        "    print()\n",
        "    \n",
        "    food = sum((DATA[u][0]) * units[u].solution_value() for u, _ in enumerate(units))\n",
        "    wood = sum((DATA[u][1]) * units[u].solution_value() for u, _ in enumerate(units))\n",
        "    gold = sum((DATA[u][2]) * units[u].solution_value() for u, _ in enumerate(units))\n",
        "    print('Resources:')\n",
        "    print(f' - 🌾Food = {food}')\n",
        "    print(f' - 🪵Wood = {wood}')\n",
        "    print(f' - 🪙Gold = {gold}')\n",
        "  else:\n",
        "    print('The solver could not find an optimal solution.')\n",
        "\n",
        "solve_army(UNITS, DATA, RESOURCES)"
      ]
    }
  ],
  "metadata": {
    "colab": {
      "name": "2. Integer vs. Linear Programming.ipynb",
      "provenance": [],
      "include_colab_link": true
    },
    "kernelspec": {
      "display_name": "Python 3",
      "name": "python3"
    },
    "language_info": {
      "name": "python",
      "version": "3.8.12"
    }
  },
  "nbformat": 4,
  "nbformat_minor": 0
}