Project_Family_Advanced_CP.ipynb

{
  "nbformat": 4,
  "nbformat_minor": 0,
  "metadata": {
    "colab": {
      "provenance": [],
      "include_colab_link": true
    },
    "kernelspec": {
      "name": "python3",
      "display_name": "Python 3"
    }
  },
  "cells": [
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "view-in-github",
        "colab_type": "text"
      },
      "source": [
        "<a href=\"https://colab.research.google.com/github/OptimizationExpert/Pyomo/blob/main/Project_Family_Advanced_CP.ipynb\" target=\"_parent\"><img src=\"https://colab.research.google.com/assets/colab-badge.svg\" alt=\"Open In Colab\"/></a>"
      ]
    },
    {
      "cell_type": "markdown",
      "source": [
        "Let’s assume that Rene and Leo are both heads of household, and, what a coincidence, both families include three girls and three boys. The youngest child in Leo’s family is a girl, and in Rene’s family, a little girl has just arrived. In other words, there is a girl in Rene’s family whose age is less than one year. Neither family includes any twins, nor any children closer in  age than a year. All the children are under age ten. In each family, the sum of the ages of the girls is equal to the sum of the ages of the boys; in fact, the sum of the squares of the ages of the girls is equal to the sum of the squares of the ages of the boys. The sum of the ages of all these children is 60.\n",
        "\n",
        "# Question: What are the ages of the children in these two families? How many solutions does this problem have?"
      ],
      "metadata": {
        "id": "HOnCQvVn0pDI"
      }
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "w_3yuwV8XtMF",
        "outputId": "6c05e519-debd-47cc-f945-d1af1d579c0b",
        "colab": {
          "base_uri": "https://localhost:8080/"
        }
      },
      "source": [
        "!pip install ortools\n",
        "from ortools.sat.python import cp_model # CP-SAT solver\n",
        "import numpy as np\n",
        "from random import randint\n",
        "import random\n",
        "from math import ceil\n",
        "import pandas as pd\n",
        "import matplotlib.pyplot as plt # Data visualization\n",
        "#plt.rcParams[\"figure.figsize\"] = (15,10)"
      ],
      "execution_count": 1,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "Collecting ortools\n",
            "  Downloading ortools-9.8.3296-cp310-cp310-manylinux_2_17_x86_64.manylinux2014_x86_64.whl (22.9 MB)\n",
            "\u001b[2K     \u001b[90m━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━\u001b[0m \u001b[32m22.9/22.9 MB\u001b[0m \u001b[31m28.7 MB/s\u001b[0m eta \u001b[36m0:00:00\u001b[0m\n",
            "\u001b[?25hCollecting absl-py>=2.0.0 (from ortools)\n",
            "  Downloading absl_py-2.0.0-py3-none-any.whl (130 kB)\n",
            "\u001b[2K     \u001b[90m━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━\u001b[0m \u001b[32m130.2/130.2 kB\u001b[0m \u001b[31m11.5 MB/s\u001b[0m eta \u001b[36m0:00:00\u001b[0m\n",
            "\u001b[?25hRequirement already satisfied: numpy>=1.13.3 in /usr/local/lib/python3.10/dist-packages (from ortools) (1.23.5)\n",
            "Collecting pandas>=2.0.0 (from ortools)\n",
            "  Downloading pandas-2.1.4-cp310-cp310-manylinux_2_17_x86_64.manylinux2014_x86_64.whl (12.3 MB)\n",
            "\u001b[2K     \u001b[90m━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━\u001b[0m \u001b[32m12.3/12.3 MB\u001b[0m \u001b[31m35.4 MB/s\u001b[0m eta \u001b[36m0:00:00\u001b[0m\n",
            "\u001b[?25hCollecting protobuf>=4.25.0 (from ortools)\n",
            "  Downloading protobuf-4.25.1-cp37-abi3-manylinux2014_x86_64.whl (294 kB)\n",
            "\u001b[2K     \u001b[90m━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━\u001b[0m \u001b[32m294.6/294.6 kB\u001b[0m \u001b[31m2.8 MB/s\u001b[0m eta \u001b[36m0:00:00\u001b[0m\n",
            "\u001b[?25hRequirement already satisfied: python-dateutil>=2.8.2 in /usr/local/lib/python3.10/dist-packages (from pandas>=2.0.0->ortools) (2.8.2)\n",
            "Requirement already satisfied: pytz>=2020.1 in /usr/local/lib/python3.10/dist-packages (from pandas>=2.0.0->ortools) (2023.3.post1)\n",
            "Collecting tzdata>=2022.1 (from pandas>=2.0.0->ortools)\n",
            "  Downloading tzdata-2023.4-py2.py3-none-any.whl (346 kB)\n",
            "\u001b[2K     \u001b[90m━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━\u001b[0m \u001b[32m346.6/346.6 kB\u001b[0m \u001b[31m11.6 MB/s\u001b[0m eta \u001b[36m0:00:00\u001b[0m\n",
            "\u001b[?25hRequirement already satisfied: six>=1.5 in /usr/local/lib/python3.10/dist-packages (from python-dateutil>=2.8.2->pandas>=2.0.0->ortools) (1.16.0)\n",
            "Installing collected packages: tzdata, protobuf, absl-py, pandas, ortools\n",
            "  Attempting uninstall: protobuf\n",
            "    Found existing installation: protobuf 3.20.3\n",
            "    Uninstalling protobuf-3.20.3:\n",
            "      Successfully uninstalled protobuf-3.20.3\n",
            "  Attempting uninstall: absl-py\n",
            "    Found existing installation: absl-py 1.4.0\n",
            "    Uninstalling absl-py-1.4.0:\n",
            "      Successfully uninstalled absl-py-1.4.0\n",
            "  Attempting uninstall: pandas\n",
            "    Found existing installation: pandas 1.5.3\n",
            "    Uninstalling pandas-1.5.3:\n",
            "      Successfully uninstalled pandas-1.5.3\n",
            "\u001b[31mERROR: pip's dependency resolver does not currently take into account all the packages that are installed. This behaviour is the source of the following dependency conflicts.\n",
            "lida 0.0.10 requires fastapi, which is not installed.\n",
            "lida 0.0.10 requires kaleido, which is not installed.\n",
            "lida 0.0.10 requires python-multipart, which is not installed.\n",
            "lida 0.0.10 requires uvicorn, which is not installed.\n",
            "bigframes 0.17.0 requires pandas<2.1.4,>=1.5.0, but you have pandas 2.1.4 which is incompatible.\n",
            "google-colab 1.0.0 requires pandas==1.5.3, but you have pandas 2.1.4 which is incompatible.\n",
            "tensorboard 2.15.1 requires protobuf<4.24,>=3.19.6, but you have protobuf 4.25.1 which is incompatible.\n",
            "tensorflow-metadata 1.14.0 requires absl-py<2.0.0,>=0.9, but you have absl-py 2.0.0 which is incompatible.\n",
            "tensorflow-metadata 1.14.0 requires protobuf<4.21,>=3.20.3, but you have protobuf 4.25.1 which is incompatible.\u001b[0m\u001b[31m\n",
            "\u001b[0mSuccessfully installed absl-py-2.0.0 ortools-9.8.3296 pandas-2.1.4 protobuf-4.25.1 tzdata-2023.4\n"
          ]
        }
      ]
    },
    {
      "cell_type": "code",
      "source": [
        "from ortools.sat.python import cp_model\n",
        "\n",
        "\n",
        "class VarArraySolutionPrinter(cp_model.CpSolverSolutionCallback):\n",
        "    \"\"\"Print intermediate solutions.\"\"\"\n",
        "\n",
        "    def __init__(self, variables):\n",
        "        cp_model.CpSolverSolutionCallback.__init__(self)\n",
        "        self.__variables = variables\n",
        "        self.__solution_count = 0\n",
        "\n",
        "    def on_solution_callback(self):\n",
        "        self.__solution_count += 1\n",
        "        for kk,v in self.__variables.items():\n",
        "            print(f\"{kk}={self.Value(v)}\")\n",
        "        print(self.__solution_count )\n",
        "\n",
        "    def solution_count(self):\n",
        "        return self.__solution_count\n",
        "\n",
        "\n",
        "def SearchForAllSolutionsSampleSat():\n",
        "    \"\"\"Showcases calling the solver to search for all solutions.\"\"\"\n",
        "    # Creates the model.\n",
        "    model = cp_model.CpModel()\n",
        "\n",
        "    # Creates the variables.\n",
        "    families = ['F1' , 'F2']\n",
        "    Jens = ['b' , 'g']\n",
        "    kids = [k for k in range(3)]\n",
        "\n",
        "    U = {(f,j,k):model.NewIntVar(0, 10, f\"kid_{f}_{j}_{k}\") for f in families for j in Jens \\\n",
        "         for k in kids}\n",
        "    US = {(f,j,k):model.NewIntVar(0, 100, f\"kidS_{f}_{j}_{k}\") for f in families for j in Jens \\\n",
        "         for k in kids}\n",
        "    expressions = [v for v in U.values()]\n",
        "    model.Add(sum(expressions)== 60)\n",
        "    model.Add(U[\"F1\",'g',0]== 0)\n",
        "\n",
        "    for (f,j,k), v in U.items():\n",
        "      model.AddMultiplicationEquality(US[f,j,k],[v,v])\n",
        "      if k <2:\n",
        "        model.Add(U[f,j,k]<=U[f,j,k+1])\n",
        "\n",
        "\n",
        "    for k in kids:\n",
        "      for j in Jens:\n",
        "        model.Add(U[\"F2\",'g',0]<= U[\"F2\",j,k])\n",
        "\n",
        "    for f in families:\n",
        "      expressions_family = [v for (F,j,k),v in U.items() if F==f]\n",
        "      model.AddAllDifferent(expressions_family)\n",
        "      expressions_family_boys = [v for (F,j,k),v in U.items() if F==f and j =='b']\n",
        "      expressions_family_girls = [v for (F,j,k),v in U.items() if F==f and j =='g']\n",
        "      model.Add(sum(expressions_family_boys)==sum(expressions_family_girls))\n",
        "\n",
        "      expressions_family_boys_square = [v for (F,j,k),v in US.items() if F==f and j =='b']\n",
        "      expressions_family_girls_square = [v for (F,j,k),v in US.items() if F==f and j =='g']\n",
        "      model.Add(sum(expressions_family_boys_square)==sum(expressions_family_girls_square))\n",
        "\n",
        "\n",
        "\n",
        "\n",
        "\n",
        "    # Create the constraints.\n",
        "\n",
        "    # Create a solver and solve.\n",
        "    solver = cp_model.CpSolver()\n",
        "    solution_printer = VarArraySolutionPrinter(U)\n",
        "    # Enumerate all solutions.\n",
        "    solver.parameters.enumerate_all_solutions = True\n",
        "    # Solve.\n",
        "    status = solver.Solve(model, solution_printer)\n",
        "\n",
        "    print(f\"Status = {solver.StatusName(status)}\")\n",
        "    #print(f\"Number of solutions found: {solution_printer.solution_count()}\")\n",
        "\n",
        "\n",
        "SearchForAllSolutionsSampleSat()"
      ],
      "metadata": {
        "id": "CFwTJ91NUzn9",
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "outputId": "e590d96c-abd2-4aa0-dec4-e3c6df91e4aa"
      },
      "execution_count": 18,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "('F1', 'b', 0)=1\n",
            "('F1', 'b', 1)=3\n",
            "('F1', 'b', 2)=8\n",
            "('F1', 'g', 0)=0\n",
            "('F1', 'g', 1)=5\n",
            "('F1', 'g', 2)=7\n",
            "('F2', 'b', 0)=4\n",
            "('F2', 'b', 1)=5\n",
            "('F2', 'b', 2)=9\n",
            "('F2', 'g', 0)=3\n",
            "('F2', 'g', 1)=7\n",
            "('F2', 'g', 2)=8\n",
            "1\n",
            "('F1', 'b', 0)=1\n",
            "('F1', 'b', 1)=4\n",
            "('F1', 'b', 2)=10\n",
            "('F1', 'g', 0)=0\n",
            "('F1', 'g', 1)=6\n",
            "('F1', 'g', 2)=9\n",
            "('F2', 'b', 0)=3\n",
            "('F2', 'b', 1)=4\n",
            "('F2', 'b', 2)=8\n",
            "('F2', 'g', 0)=2\n",
            "('F2', 'g', 1)=6\n",
            "('F2', 'g', 2)=7\n",
            "2\n",
            "('F1', 'b', 0)=1\n",
            "('F1', 'b', 1)=4\n",
            "('F1', 'b', 2)=10\n",
            "('F1', 'g', 0)=0\n",
            "('F1', 'g', 1)=6\n",
            "('F1', 'g', 2)=9\n",
            "('F2', 'b', 0)=1\n",
            "('F2', 'b', 1)=4\n",
            "('F2', 'b', 2)=10\n",
            "('F2', 'g', 0)=0\n",
            "('F2', 'g', 1)=6\n",
            "('F2', 'g', 2)=9\n",
            "3\n",
            "('F1', 'b', 0)=2\n",
            "('F1', 'b', 1)=3\n",
            "('F1', 'b', 2)=10\n",
            "('F1', 'g', 0)=0\n",
            "('F1', 'g', 1)=7\n",
            "('F1', 'g', 2)=8\n",
            "('F2', 'b', 0)=1\n",
            "('F2', 'b', 1)=4\n",
            "('F2', 'b', 2)=10\n",
            "('F2', 'g', 0)=0\n",
            "('F2', 'g', 1)=6\n",
            "('F2', 'g', 2)=9\n",
            "4\n",
            "('F1', 'b', 0)=1\n",
            "('F1', 'b', 1)=2\n",
            "('F1', 'b', 2)=6\n",
            "('F1', 'g', 0)=0\n",
            "('F1', 'g', 1)=4\n",
            "('F1', 'g', 2)=5\n",
            "('F2', 'b', 0)=5\n",
            "('F2', 'b', 1)=6\n",
            "('F2', 'b', 2)=10\n",
            "('F2', 'g', 0)=4\n",
            "('F2', 'g', 1)=8\n",
            "('F2', 'g', 2)=9\n",
            "5\n",
            "('F1', 'b', 0)=2\n",
            "('F1', 'b', 1)=3\n",
            "('F1', 'b', 2)=10\n",
            "('F1', 'g', 0)=0\n",
            "('F1', 'g', 1)=7\n",
            "('F1', 'g', 2)=8\n",
            "('F2', 'b', 0)=3\n",
            "('F2', 'b', 1)=4\n",
            "('F2', 'b', 2)=8\n",
            "('F2', 'g', 0)=2\n",
            "('F2', 'g', 1)=6\n",
            "('F2', 'g', 2)=7\n",
            "6\n",
            "('F1', 'b', 0)=1\n",
            "('F1', 'b', 1)=4\n",
            "('F1', 'b', 2)=10\n",
            "('F1', 'g', 0)=0\n",
            "('F1', 'g', 1)=6\n",
            "('F1', 'g', 2)=9\n",
            "('F2', 'b', 0)=2\n",
            "('F2', 'b', 1)=4\n",
            "('F2', 'b', 2)=9\n",
            "('F2', 'g', 0)=1\n",
            "('F2', 'g', 1)=6\n",
            "('F2', 'g', 2)=8\n",
            "7\n",
            "('F1', 'b', 0)=2\n",
            "('F1', 'b', 1)=3\n",
            "('F1', 'b', 2)=10\n",
            "('F1', 'g', 0)=0\n",
            "('F1', 'g', 1)=7\n",
            "('F1', 'g', 2)=8\n",
            "('F2', 'b', 0)=2\n",
            "('F2', 'b', 1)=4\n",
            "('F2', 'b', 2)=9\n",
            "('F2', 'g', 0)=1\n",
            "('F2', 'g', 1)=6\n",
            "('F2', 'g', 2)=8\n",
            "8\n",
            "('F1', 'b', 0)=1\n",
            "('F1', 'b', 1)=4\n",
            "('F1', 'b', 2)=10\n",
            "('F1', 'g', 0)=0\n",
            "('F1', 'g', 1)=6\n",
            "('F1', 'g', 2)=9\n",
            "('F2', 'b', 0)=2\n",
            "('F2', 'b', 1)=3\n",
            "('F2', 'b', 2)=10\n",
            "('F2', 'g', 0)=0\n",
            "('F2', 'g', 1)=7\n",
            "('F2', 'g', 2)=8\n",
            "9\n",
            "('F1', 'b', 0)=2\n",
            "('F1', 'b', 1)=3\n",
            "('F1', 'b', 2)=10\n",
            "('F1', 'g', 0)=0\n",
            "('F1', 'g', 1)=7\n",
            "('F1', 'g', 2)=8\n",
            "('F2', 'b', 0)=2\n",
            "('F2', 'b', 1)=3\n",
            "('F2', 'b', 2)=10\n",
            "('F2', 'g', 0)=0\n",
            "('F2', 'g', 1)=7\n",
            "('F2', 'g', 2)=8\n",
            "10\n",
            "('F1', 'b', 0)=1\n",
            "('F1', 'b', 1)=3\n",
            "('F1', 'b', 2)=8\n",
            "('F1', 'g', 0)=0\n",
            "('F1', 'g', 1)=5\n",
            "('F1', 'g', 2)=7\n",
            "('F2', 'b', 0)=3\n",
            "('F2', 'b', 1)=5\n",
            "('F2', 'b', 2)=10\n",
            "('F2', 'g', 0)=2\n",
            "('F2', 'g', 1)=7\n",
            "('F2', 'g', 2)=9\n",
            "11\n",
            "Status = OPTIMAL\n"
          ]
        }
      ]
    }
  ]
}