authors/glebbelov/miscellaneous/sched_numberof.ipynb

{
  "cells": [
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "# CP-style scheduling model with the *numberof* operator, solved by a MIP solver\n",
        "[![sched_numberof.ipynb](https://img.shields.io/badge/github-%23121011.svg?logo=github)](https://github.com/ampl/colab.ampl.com/blob/master/authors/glebbelov/miscellaneous/sched_numberof.ipynb) [![Open In Colab](https://colab.research.google.com/assets/colab-badge.svg)](https://colab.research.google.com/github/ampl/colab.ampl.com/blob/master/authors/glebbelov/miscellaneous/sched_numberof.ipynb) [![Kaggle](https://kaggle.com/static/images/open-in-kaggle.svg)](https://kaggle.com/kernels/welcome?src=https://github.com/ampl/colab.ampl.com/blob/master/authors/glebbelov/miscellaneous/sched_numberof.ipynb) [![Gradient](https://assets.paperspace.io/img/gradient-badge.svg)](https://console.paperspace.com/github/ampl/colab.ampl.com/blob/master/authors/glebbelov/miscellaneous/sched_numberof.ipynb) [![Open In SageMaker Studio Lab](https://studiolab.sagemaker.aws/studiolab.svg)](https://studiolab.sagemaker.aws/import/github/ampl/colab.ampl.com/blob/master/authors/glebbelov/miscellaneous/sched_numberof.ipynb) [![Hits](https://h.ampl.com/https://github.com/ampl/colab.ampl.com/blob/master/authors/glebbelov/miscellaneous/sched_numberof.ipynb)](https://colab.ampl.com)\n",
        "\n",
        "Description: Scheduling model with the Constraint Programming *numberof* operator, solved with a MIP solver. New MIP solver drivers based on the [MP library](https://amplmp.readthedocs.io/) enable CP-style modeling.\n",
        "\n",
        "Tags: ampl-only, constraint-programming\n",
        "\n",
        "Notebook author: Gleb Belov <<gleb@ampl.com>>\n",
        "\n",
        "Model author: AMPL logic programming examples\n"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 130,
      "metadata": {},
      "outputs": [],
      "source": [
        "# Install dependencies\n",
        "%pip install -q amplpy"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 131,
      "metadata": {},
      "outputs": [],
      "source": [
        "# Google Colab & Kaggle integration\n",
        "from amplpy import AMPL, ampl_notebook\n",
        "\n",
        "ampl = ampl_notebook(\n",
        "    modules=[\"coin\", \"highs\"],  # modules to install\n",
        "    license_uuid=\"default\",  # license to use\n",
        ")  # instantiate AMPL object and register magics"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "## Scheduling model with the *numberof* operator\n",
        "\n",
        "We create a MIP model for a scheduling problem. Then we express the model with the syntax of the [AMPL Logic and Constraint Programming extensions](https://ampl.com/products/ampl/logic-and-constraint-programming-extensions/) and use a MIP solver driver with automatic CP-to-MIP transformation.\n",
        "\n",
        "The problem is to assign *n* jobs to *n* machines, so that each machine's capacity is obeyed, and minimizing total cost. We formulate a parameteric model, and provide data to create a model instance. The parameters are as follows:"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 132,
      "metadata": {},
      "outputs": [],
      "source": [
        "%%ampl_eval\n",
        "param n integer > 0;\n",
        "\n",
        "set JOBS := 1..n;\n",
        "set MACHINES := 1..n;\n",
        "\n",
        "param cap {MACHINES} integer >= 0;\n",
        "\n",
        "param cost {JOBS,MACHINES} > 0;"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "For a MIP formulation we introduce *n* * *n* binary variables:"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 133,
      "metadata": {},
      "outputs": [],
      "source": [
        "%%ampl_eval\n",
        "\n",
        "var Assign {JOBS,MACHINES} binary;"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "The first set of constraints asks that each job is assigned to some machine:"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 134,
      "metadata": {},
      "outputs": [],
      "source": [
        "%%ampl_eval\n",
        "subj to OneMachinePerJob {j in JOBS}:\n",
        "   sum {k in MACHINES} Assign[j,k] = 1;"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "The second set of constraints obeys the machine capacity:"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 135,
      "metadata": {},
      "outputs": [],
      "source": [
        "%%ampl_eval\n",
        "subj to CapacityOfMachine {k in MACHINES}:\n",
        "   sum {j in JOBS} Assign[j,k] <= cap[k];"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "Objective function:"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 136,
      "metadata": {},
      "outputs": [],
      "source": [
        "%%ampl_eval\n",
        "minimize TotalCost:\n",
        "   sum {j in JOBS, k in MACHINES} cost[j,k] * Assign[j,k];"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "We need data for the model parameters:"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 137,
      "metadata": {},
      "outputs": [],
      "source": [
        "%%ampl_eval\n",
        "data;\n",
        "param n := 3;\n",
        "\n",
        "param cost:\n",
        "  1 2 3 :=\n",
        "1 1 3 3\n",
        "2 2 3 3\n",
        "3 3 3 2;\n",
        "\n",
        "param cap :=\n",
        "1 2\n",
        "2 3\n",
        "3 1;\n"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "Solving with a MIP solver:"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 138,
      "metadata": {},
      "outputs": [
        {
          "name": "stdout",
          "output_type": "stream",
          "text": [
            "HiGHS 1.2.2: tech:outlev=1\n",
            "Running HiGHS 1.2.2 [date: 2022-09-28, git hash: 9c7b2cf27]\n",
            "Copyright (c) 2022 ERGO-Code under MIT licence terms\n",
            "Presolving model\n",
            "5 rows, 9 cols, 15 nonzeros\n",
            "0 rows, 0 cols, 0 nonzeros\n",
            "Presolve: Optimal\n",
            "\n",
            "Solving report\n",
            "  Status            Optimal\n",
            "  Primal bound      5\n",
            "  Dual bound        5\n",
            "  Gap               0% (tolerance: 0.01%)\n",
            "  Solution status   feasible\n",
            "                    5 (objective)\n",
            "                    0 (bound viol.)\n",
            "                    0 (int. viol.)\n",
            "                    0 (row viol.)\n",
            "  Timing            0.00 (total)\n",
            "                    0.00 (presolve)\n",
            "                    0.00 (postsolve)\n",
            "  Nodes             0\n",
            "  LP iterations     0 (total)\n",
            "                    0 (strong br.)\n",
            "                    0 (separation)\n",
            "                    0 (heuristics)\n",
            "HiGHS 1.2.2: optimal solution; objective 5\n",
            "0 branching nodes\n",
            "Assign [*,*]\n",
            ":   1   2   3    :=\n",
            "1   1   0   0\n",
            "2   1   0   0\n",
            "3   0   0   1\n",
            ";\n",
            "\n"
          ]
        }
      ],
      "source": [
        "%%ampl_eval\n",
        "option solver highs;\n",
        "option highs_options 'outlev=1';\n",
        "solve;\n",
        "option display_1col 5;    # To display a matrix\n",
        "display Assign;"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "Now we enter a CP-style model with the same parameters."
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 139,
      "metadata": {},
      "outputs": [],
      "source": [
        "%%ampl_eval\n",
        "reset;            ## Clear model and data\n",
        "\n",
        "param n integer > 0;\n",
        "\n",
        "set JOBS := 1..n;\n",
        "set MACHINES := 1..n;\n",
        "\n",
        "param cap {MACHINES} integer >= 0;\n",
        "\n",
        "param cost {JOBS,MACHINES} > 0;"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "The variables denote the chosen machine for each job:"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 140,
      "metadata": {},
      "outputs": [],
      "source": [
        "%%ampl_eval\n",
        "var MachineForJob {JOBS} integer >= 1, <= n;"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "The single set of constraints obeys for the machine capacity:"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 141,
      "metadata": {},
      "outputs": [],
      "source": [
        "%%ampl_eval\n",
        "subj to CapacityOfMachine {k in MACHINES}:\n",
        "   numberof k in ({j in JOBS} MachineForJob[j]) <= cap[k];"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "The objective function is formulated using the new *MachineForJob* variables:"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 142,
      "metadata": {},
      "outputs": [],
      "source": [
        "%%ampl_eval\n",
        "minimize TotalCost:\n",
        "   sum {j in JOBS, k in MACHINES} \n",
        "      if MachineForJob[j] = k then cost[j,k];"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "We need to re-enter the parameters:"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 143,
      "metadata": {},
      "outputs": [],
      "source": [
        "%%ampl_eval\n",
        "data;\n",
        "param n := 3;\n",
        "\n",
        "param cost:\n",
        "  1 2 3 :=\n",
        "1 1 3 3\n",
        "2 2 3 3\n",
        "3 3 3 2;\n",
        "\n",
        "param cap :=\n",
        "1 2\n",
        "2 3\n",
        "3 1;"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "Solving with a MIP solver again:"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 144,
      "metadata": {},
      "outputs": [
        {
          "name": "stdout",
          "output_type": "stream",
          "text": [
            "HiGHS 1.2.2: tech:outlev=1\n",
            "Running HiGHS 1.2.2 [date: 2022-09-28, git hash: 9c7b2cf27]\n",
            "Copyright (c) 2022 ERGO-Code under MIT licence terms\n",
            "Presolving model\n",
            "8 rows, 14 cols, 29 nonzeros\n",
            "8 rows, 14 cols, 26 nonzeros\n",
            "Objective function is integral with scale 1\n",
            "\n",
            "Solving MIP model with:\n",
            "   8 rows\n",
            "   14 cols (10 binary, 4 integer, 0 implied int., 0 continuous)\n",
            "   26 nonzeros\n",
            "\n",
            "        Nodes      |    B&B Tree     |            Objective Bounds              |  Dynamic Constraints |       Work      \n",
            "     Proc. InQueue |  Leaves   Expl. | BestBound       BestSol              Gap |   Cuts   InLp Confl. | LpIters     Time\n",
            "\n",
            "         0       0         0   0.00%   0               inf                  inf        0      0      0         0     0.0s\n",
            " T       0       0         0   0.00%   0               5                100.00%        0      0      0         6     0.0s\n",
            "\n",
            "Solving report\n",
            "  Status            Optimal\n",
            "  Primal bound      5\n",
            "  Dual bound        5\n",
            "  Gap               0% (tolerance: 0.01%)\n",
            "  Solution status   feasible\n",
            "                    5 (objective)\n",
            "                    0 (bound viol.)\n",
            "                    0 (int. viol.)\n",
            "                    0 (row viol.)\n",
            "  Timing            0.00 (total)\n",
            "                    0.00 (presolve)\n",
            "                    0.00 (postsolve)\n",
            "  Nodes             1\n",
            "  LP iterations     6 (total)\n",
            "                    0 (strong br.)\n",
            "                    0 (separation)\n",
            "                    0 (heuristics)\n",
            "HiGHS 1.2.2: optimal solution; objective 5\n",
            "1 branching nodes\n",
            "MachineForJob [*] :=\n",
            "1  1\n",
            "2  1\n",
            "3  3\n",
            ";\n",
            "\n"
          ]
        }
      ],
      "source": [
        "%%ampl_eval\n",
        "solve;\n",
        "display MachineForJob;"
      ]
    }
  ],
  "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.9.6"
    }
  },
  "nbformat": 4,
  "nbformat_minor": 2
}