3_Constraint_Programming.ipynb

{
  "nbformat": 4,
  "nbformat_minor": 0,
  "metadata": {
    "colab": {
      "name": "3. Constraint Programming.ipynb",
      "provenance": [],
      "collapsed_sections": [],
      "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/jonbaer/googlecolab/blob/master/3_Constraint_Programming.ipynb\" target=\"_parent\"><img src=\"https://colab.research.google.com/assets/colab-badge.svg\" alt=\"Open In Colab\"/></a>"
      ]
    },
    {
      "cell_type": "markdown",
      "source": [
        "# Constraint Programming\n",
        "\n",
        "> Chapter 3 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: "
      ],
      "metadata": {
        "id": "Ti4Xsm_RpqxE"
      }
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "id": "lRgbfs48pYOA"
      },
      "outputs": [],
      "source": [
        "!python -m pip install --upgrade --user -q ortools"
      ]
    },
    {
      "cell_type": "markdown",
      "source": [
        "# Satisfiability\n",
        "\n",
        "Find the number of soldiers in the enemy army, called $army$.\n",
        "\n",
        "$$\n",
        "  \\left\\{\\begin{array}{@{}l@{}}\n",
        "    army \\equiv 0 \\mod 13\\\\\n",
        "    army \\equiv 0 \\mod 19\\\\\n",
        "    army \\equiv 0 \\mod 37\\\\\n",
        "    1 \\leq army \\leq 10\\ 000\n",
        "  \\end{array}\\right.\\,\n",
        "$$\n",
        "\n",
        "If the following cell fails, click on `Runtime > Restart and run all`."
      ],
      "metadata": {
        "id": "f-8tYRrcp4Y7"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "from ortools.sat.python import cp_model\n",
        "\n",
        "# Instantiate model and solver\n",
        "model = cp_model.CpModel()\n",
        "solver = cp_model.CpSolver()\n",
        "\n",
        "# 1. Variable\n",
        "army = model.NewIntVar(1, 10000, 'army')\n",
        "\n",
        "# 2. Constraints\n",
        "# variable % mod = target → (target, variable, mod)\n",
        "model.AddModuloEquality(0, army, 13)\n",
        "model.AddModuloEquality(0, army, 19)\n",
        "model.AddModuloEquality(0, army, 37)\n",
        "\n",
        "# Find the variable that satisfies these constraints\n",
        "status = solver.Solve(model)\n",
        "\n",
        "# If a solution has been found, print results\n",
        "if status == cp_model.OPTIMAL or status == cp_model.FEASIBLE:\n",
        "    print('================= Solution =================')\n",
        "    print(f'Solved in {solver.WallTime():.2f} milliseconds')\n",
        "    print()\n",
        "    print(f'🪖 Army = {solver.Value(army)}')\n",
        "    print()\n",
        "    print('Check solution:')\n",
        "    print(f' - Constraint 1: {solver.Value(army)} % 13 = {solver.Value(army) % 13}')\n",
        "    print(f' - Constraint 2: {solver.Value(army)} % 19 = {solver.Value(army) % 19}')\n",
        "    print(f' - Constraint 3: {solver.Value(army)} % 37 = {solver.Value(army) % 37}')\n",
        "\n",
        "else:\n",
        "    print('The solver could not find a solution.')"
      ],
      "metadata": {
        "id": "y9ITXS14pcps",
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "outputId": "fd6192b0-a757-4f80-d0a6-f5b3dd8bc156"
      },
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "================= Solution =================\n",
            "Solved in 0.00 milliseconds\n",
            "\n",
            "🪖 Army = 9139\n",
            "\n",
            "Check solution:\n",
            " - Constraint 1: 9139 % 13 = 0\n",
            " - Constraint 2: 9139 % 19 = 0\n",
            " - Constraint 3: 9139 % 37 = 0\n"
          ]
        }
      ]
    },
    {
      "cell_type": "markdown",
      "source": [
        "Print every solution with a callback with a new upper bound:\n",
        "\n",
        "$$1 \\leq army \\leq 100\\ 000$$"
      ],
      "metadata": {
        "id": "Naa_73V_qG8r"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "model = cp_model.CpModel()\n",
        "solver = cp_model.CpSolver()\n",
        "\n",
        "# 1. Variable\n",
        "army = model.NewIntVar(1, 100000, 'army')\n",
        "\n",
        "# 2. Constraints\n",
        "model.AddModuloEquality(0, army, 13)\n",
        "model.AddModuloEquality(0, army, 19)\n",
        "model.AddModuloEquality(0, army, 37)\n",
        "\n",
        "\n",
        "class PrintSolutions(cp_model.CpSolverSolutionCallback):\n",
        "    \"\"\"Callback to print every solution.\"\"\"\n",
        "\n",
        "    def __init__(self, variable):\n",
        "        cp_model.CpSolverSolutionCallback.__init__(self)\n",
        "        self.__variable = variable\n",
        "\n",
        "    def on_solution_callback(self):\n",
        "        print(self.Value(self.__variable))\n",
        "\n",
        "# Solve with callback\n",
        "solution_printer = PrintSolutions(army)\n",
        "solver.parameters.enumerate_all_solutions = True\n",
        "status = solver.Solve(model, solution_printer)"
      ],
      "metadata": {
        "id": "gTkTq-K1pcnT",
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "outputId": "f597e8b1-0f77-466e-b5dc-e9b410849e71"
      },
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "9139\n",
            "18278\n",
            "27417\n",
            "36556\n",
            "45695\n",
            "54834\n",
            "63973\n",
            "73112\n",
            "82251\n",
            "91390\n"
          ]
        }
      ]
    },
    {
      "cell_type": "markdown",
      "source": [
        "# Optimization\n",
        "\n",
        "The goal is to maximize the popularity of the rations without exceeding the capacity of 19.\n",
        "\n",
        "|  | 🥖Bread | 🥩Meat | 🍺Beer |\n",
        "| :--- | :---: | :---: | :---: |\n",
        "| Size | 1 | 3 | 7 |\n",
        "| Popularity    | 3 | 10 | 26 |\n",
        "\n",
        "## 1. Constraint Programming solution:"
      ],
      "metadata": {
        "id": "WYqQqKe9qTbi"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "from ortools.sat.python import cp_model\n",
        "\n",
        "# Instantiate model and solver\n",
        "model = cp_model.CpModel()\n",
        "solver = cp_model.CpSolver()\n",
        "\n",
        "# 1. Variables\n",
        "capacity = 19\n",
        "bread = model.NewIntVar(0, capacity, 'bread')\n",
        "meat  = model.NewIntVar(0, capacity, 'meat')\n",
        "beer  = model.NewIntVar(0, capacity, 'beer')\n",
        "\n",
        "# 2. Constraints\n",
        "model.Add(1 * bread\n",
        "        + 3 * meat \n",
        "        + 7 * beer <= capacity)\n",
        "\n",
        "# 3. Objective\n",
        "model.Maximize(3  * bread\n",
        "             + 10 * meat\n",
        "             + 26 * beer)\n",
        "\n",
        "# Solve problem\n",
        "status = solver.Solve(model)\n",
        "\n",
        "# If an optimal solution has been found, print results\n",
        "if status == cp_model.OPTIMAL:\n",
        "    print('================= Solution =================')\n",
        "    print(f'Solved in {solver.WallTime():.2f} milliseconds')\n",
        "    print()\n",
        "    print(f'Optimal value = {3*solver.Value(bread)+10*solver.Value(meat)+26*solver.Value(beer)} popularity')\n",
        "    print('Food:')\n",
        "    print(f' - 🥖Bread = {solver.Value(bread)}')\n",
        "    print(f' - 🥩Meat  = {solver.Value(meat)}')\n",
        "    print(f' - 🍺Beer  = {solver.Value(beer)}')\n",
        "    print()\n",
        "    print(f'Constraint: 1*{solver.Value(bread)}🥖 + 3*{solver.Value(meat)}🥩 + 7*{solver.Value(beer)}🍺')\n",
        "    print(f'            = {1*solver.Value(bread)+3*solver.Value(meat)+7*solver.Value(beer)} (<= {capacity})')\n",
        "else:\n",
        "    print('The solver could not find an optimal solution.')"
      ],
      "metadata": {
        "id": "LNdnehD5pck0",
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "outputId": "39e8c0b4-666e-47ee-9328-6ed927dfa81f"
      },
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "================= Solution =================\n",
            "Solved in 0.00 milliseconds\n",
            "\n",
            "Optimal value = 68 popularity\n",
            "Food:\n",
            " - 🥖Bread = 2\n",
            " - 🥩Meat  = 1\n",
            " - 🍺Beer  = 2\n",
            "\n",
            "Constraint: 1*2🥖 + 3*1🥩 + 7*2🍺\n",
            "            = 19 (<= 19)\n"
          ]
        }
      ]
    },
    {
      "cell_type": "markdown",
      "source": [
        "## 2. Linear Programming solution:"
      ],
      "metadata": {
        "id": "b0kQYdd4rWBU"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "from ortools.linear_solver import pywraplp\n",
        "\n",
        "# Instantiate solver with CBC backend\n",
        "solver = pywraplp.Solver('',\n",
        "                         pywraplp.Solver.CBC_MIXED_INTEGER_PROGRAMMING)\n",
        "\n",
        "# 1. Variables\n",
        "capacity = 19\n",
        "bread = solver.IntVar(0, capacity, 'bread')\n",
        "meat  = solver.IntVar(0, capacity, 'meat')\n",
        "beer  = solver.IntVar(0, capacity, 'beer')\n",
        "\n",
        "# 2. Constraints\n",
        "solver.Add(1 * bread\n",
        "         + 3 * meat\n",
        "         + 7 * beer <= capacity)\n",
        "\n",
        "# 3. Objective\n",
        "solver.Maximize(3  * bread\n",
        "              + 10 * meat\n",
        "              + 26 * beer)\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()} popularity')\n",
        "  print('Food:')\n",
        "  print(f' - 🥖Bread  = {bread.solution_value()}')\n",
        "  print(f' - 🥩Meat = {meat.solution_value()}')\n",
        "  print(f' - 🍺Beer = {beer.solution_value()}')\n",
        "  print()\n",
        "  print(f'Constraint: 1*{bread.solution_value()}🥖 + 3*{meat.solution_value()}🥩 + 7*{beer.solution_value()}🍺')\n",
        "  print(f'            = {1*bread.solution_value()+3*meat.solution_value()+7*beer.solution_value()} (<= {capacity})')\n",
        "else:\n",
        "  print('The solver could not find an optimal solution.')"
      ],
      "metadata": {
        "id": "XQz8YzsspciE",
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "outputId": "7eb617f5-102e-41e0-9cce-034035ecb522"
      },
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "================= Solution =================\n",
            "Solved in 97.00 milliseconds in 1 iterations\n",
            "\n",
            "Optimal value = 68.0 popularity\n",
            "Food:\n",
            " - 🥖Bread  = 2.0\n",
            " - 🥩Meat = 1.0\n",
            " - 🍺Beer = 2.0\n",
            "\n",
            "Constraint: 1*2.0🥖 + 3*1.0🥩 + 7*2.0🍺\n",
            "            = 19.0 (<= 19)\n"
          ]
        }
      ]
    },
    {
      "cell_type": "markdown",
      "source": [
        "Count the number of possible solutions (it takes hours and hours with a capacity of 1000)."
      ],
      "metadata": {
        "id": "xC86ceQUrgMh"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "class CountSolutions(cp_model.CpSolverSolutionCallback):\n",
        "    \"\"\"Count the number of solutions.\"\"\"\n",
        "\n",
        "    def __init__(self):\n",
        "        cp_model.CpSolverSolutionCallback.__init__(self)\n",
        "        self.__solution_count = 0\n",
        "\n",
        "    def on_solution_callback(self):\n",
        "        self.__solution_count += 1\n",
        "\n",
        "    def solution_count(self):\n",
        "        return self.__solution_count\n",
        "\n",
        "solution_printer = CountSolutions()\n",
        "\n",
        "# Instantiate model and solver\n",
        "model = cp_model.CpModel()\n",
        "solver = cp_model.CpSolver()\n",
        "\n",
        "# 1. Variables\n",
        "capacity = 1000\n",
        "bread = model.NewIntVar(0, capacity, 'bread')\n",
        "meat  = model.NewIntVar(0, capacity, 'meat')\n",
        "beer  = model.NewIntVar(0, capacity, 'beer')\n",
        "\n",
        "# 2. Constraints\n",
        "model.Add(1 * bread\n",
        "        + 3 * meat \n",
        "        + 7 * beer <= capacity)\n",
        "\n",
        "# Print results\n",
        "solver.parameters.enumerate_all_solutions = True\n",
        "status = solver.Solve(model, solution_printer)\n",
        "print(solution_printer.solution_count())"
      ],
      "metadata": {
        "id": "JEVgIrPapcbY"
      },
      "execution_count": null,
      "outputs": []
    }
  ]
}