authors/fdabrandao/examples/pattern_enumeration.ipynb

{
  "cells": [
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "# Pattern Enumeration\n",
        "[![pattern_enumeration.ipynb](https://img.shields.io/badge/github-%23121011.svg?logo=github)](https://github.com/ampl/colab.ampl.com/blob/master/authors/fdabrandao/examples/pattern_enumeration.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/fdabrandao/examples/pattern_enumeration.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/fdabrandao/examples/pattern_enumeration.ipynb) [![Gradient](https://assets.paperspace.io/img/gradient-badge.svg)](https://console.paperspace.com/github/ampl/colab.ampl.com/blob/master/authors/fdabrandao/examples/pattern_enumeration.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/fdabrandao/examples/pattern_enumeration.ipynb) [![Hits](https://h.ampl.com/https://github.com/ampl/colab.ampl.com/blob/master/authors/fdabrandao/examples/pattern_enumeration.ipynb)](https://colab.ampl.com)\n",
        "\n",
        "Description: Pattern enumeration example with amplpy\n",
        "\n",
        "Tags: amplpy, example\n",
        "\n",
        "Notebook author: Filipe Brandão <<fdabrandao@gmail.com>>\n",
        "\n",
        "Model author: N/A\n",
        "\n",
        "References: N/A"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 1,
      "metadata": {},
      "outputs": [],
      "source": [
        "# Install dependencies\n",
        "%pip install -q amplpy amplpy matplotlib numpy"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 2,
      "metadata": {},
      "outputs": [],
      "source": [
        "# Google Colab & Kaggle integration\n",
        "from amplpy import AMPL, ampl_notebook\n",
        "\n",
        "ampl = ampl_notebook(\n",
        "    modules=[\"gurobi\"],  # modules to install\n",
        "    license_uuid=\"default\",  # license to use\n",
        ")  # instantiate AMPL object and register magics"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "### Basic pattern-cutting model"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 3,
      "metadata": {},
      "outputs": [],
      "source": [
        "%%ampl_eval\n",
        "param nPatterns integer > 0;\n",
        "set PATTERNS = 1..nPatterns; # patterns\n",
        "set WIDTHS; # finished widths\n",
        "param order {WIDTHS} >= 0; # rolls of width j ordered\n",
        "param overrun; # permitted overrun on any width\n",
        "param rolls {WIDTHS,PATTERNS} >= 0 default 0; # rolls of width i in pattern j\n",
        "\n",
        "var Cut {PATTERNS} integer >= 0; # raw rolls to cut in each pattern\n",
        "\n",
        "minimize TotalRawRolls: sum {p in PATTERNS} Cut[p];\n",
        "\n",
        "subject to FinishedRollLimits {w in WIDTHS}:\n",
        "  order[w] <= sum {p in PATTERNS} rolls[w,p] * Cut[p] <= order[w] + overrun;"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "### Enumeration routine"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 4,
      "metadata": {},
      "outputs": [],
      "source": [
        "from math import floor\n",
        "\n",
        "\n",
        "def patternEnum(roll_width, widths, prefix=[]):\n",
        "    max_rep = int(floor(roll_width / widths[0]))\n",
        "    if len(widths) == 1:\n",
        "        patmat = [prefix + [max_rep]]\n",
        "    else:\n",
        "        patmat = []\n",
        "        for n in reversed(range(max_rep + 1)):\n",
        "            patmat += patternEnum(roll_width - n * widths[0], widths[1:], prefix + [n])\n",
        "    return patmat"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "### Plotting routine"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 5,
      "metadata": {},
      "outputs": [],
      "source": [
        "def cuttingPlot(roll_width, widths, solution):\n",
        "    import numpy as np\n",
        "    import matplotlib.pyplot as plt\n",
        "\n",
        "    ind = np.arange(len(solution))\n",
        "    acc = [0] * len(solution)\n",
        "    for p, (patt, rep) in enumerate(solution):\n",
        "        for i in range(len(widths)):\n",
        "            for j in range(patt[i]):\n",
        "                vec = [0] * len(solution)\n",
        "                vec[p] = widths[i]\n",
        "                plt.bar(ind, vec, width=0.35, bottom=acc)\n",
        "                acc[p] += widths[i]\n",
        "    plt.title(\"Solution\")\n",
        "    plt.xticks(ind, tuple(\"x {:}\".format(rep) for patt, rep in solution))\n",
        "    plt.yticks(np.arange(0, roll_width, 10))\n",
        "    plt.show()"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "### Set & generate data"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 6,
      "metadata": {},
      "outputs": [],
      "source": [
        "roll_width = 64.5\n",
        "overrun = 6\n",
        "orders = {6.77: 10, 7.56: 40, 17.46: 33, 18.76: 10}\n",
        "widths = list(sorted(orders.keys(), reverse=True))\n",
        "patmat = patternEnum(roll_width, widths)"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "### Send data to AMPL (Java/C++ style)"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 7,
      "metadata": {},
      "outputs": [],
      "source": [
        "# Send scalar values\n",
        "ampl.get_parameter(\"overrun\").set(overrun)\n",
        "ampl.get_parameter(\"nPatterns\").set(len(patmat))\n",
        "# Send order vector\n",
        "ampl.get_set(\"WIDTHS\").set_values(widths)\n",
        "ampl.get_parameter(\"order\").set_values(orders)\n",
        "# Send pattern matrix\n",
        "ampl.get_parameter(\"rolls\").set_values(\n",
        "    {\n",
        "        (widths[i], 1 + p): patmat[p][i]\n",
        "        for i in range(len(widths))\n",
        "        for p in range(len(patmat))\n",
        "    }\n",
        ")"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "### Send data to AMPL (alternative style)"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 8,
      "metadata": {},
      "outputs": [],
      "source": [
        "# Send scalar values\n",
        "ampl.param[\"overrun\"] = overrun\n",
        "ampl.param[\"nPatterns\"] = len(patmat)\n",
        "# Send order vector\n",
        "ampl.set[\"WIDTHS\"] = widths\n",
        "ampl.param[\"order\"] = orders\n",
        "# Send pattern matrixc\n",
        "ampl.param[\"rolls\"] = {\n",
        "    (widths[i], 1 + p): patmat[p][i]\n",
        "    for i in range(len(widths))\n",
        "    for p in range(len(patmat))\n",
        "}"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "### Solve and report"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 9,
      "metadata": {},
      "outputs": [
        {
          "name": "stdout",
          "output_type": "stream",
          "text": [
            "Gurobi 9.5.0: optimal solution; objective 18\n",
            "6 simplex iterations\n",
            "1 branch-and-cut nodes\n"
          ]
        },
        {
          "data": {
            "image/png": "iVBORw0KGgoAAAANSUhEUgAAAXAAAAEICAYAAABGaK+TAAAAOXRFWHRTb2Z0d2FyZQBNYXRwbG90bGliIHZlcnNpb24zLjUuMSwgaHR0cHM6Ly9tYXRwbG90bGliLm9yZy/YYfK9AAAACXBIWXMAAAsTAAALEwEAmpwYAAARB0lEQVR4nO3da7BdZX3H8e9PAo0VKwkcU0rEYEGR0YLOEfE6ShSxUuEFQ71Uo6WTsaOWFlsLnVqrtR19423qOKaixAoIxTpksKOkAUq1ioSCXAyaiKBQIFFAQUUb/PfFWdHdk52cnXP2Ppvn5PuZ2bPX5Vlr/fNkzW/WefZea6eqkCS151HjLkCSNDsGuCQ1ygCXpEYZ4JLUKANckhplgEtSowxwLXhJViSpJItmuf1rk1w27LqkuTLA1ZQkz0/yX0l+mOTeJF9O8qwh7n+nsK+q86rqhGEdQxqWWV2RSOOQ5DeAS4E/Bi4C9gNeAPxsnHVJ4+IVuFryZICquqCqHq6qn1bVZVV1Q5JHJfnrJLcn2ZrkU0ke128nSW5L8pKe+b9N8ulu9qru/f4kDyZ5TpI3JPlST/vnJrmm+yvgmiTP7Vl3ZZK/6/4yeCDJZUkOGn5XSAa42vIt4OEka5O8PMmSnnVv6F4vBp4E7A/84yyO8cLu/YCq2r+qvtK7MslS4PPAh4EDgfcDn09yYE+z1wBvBB7P1F8Jfz6LOqQZGeBqRlX9CHg+UMA/AduSrEuyDHgt8P6qurWqHgTOBl412w8ud+MVwOaq+ueq2l5VFwC3AL/X0+aTVfWtqvopU0M9xwy5BgkwwNWYqtpUVW+oquXA04DfAj7Yvd/e0/R2pj7jWTbkEqYfZ8exDumZv7tn+idM/TUgDZ0BrmZV1S3AuUwF+f8AT+xZfSiwHbinz6Y/Bn69Z/43e3c7w2GnH2fHse6cuWJpuAxwNSPJkUnelmR5N/8E4NXAV4ELgD9LcliS/YF/AC6squ19dnU9U8Mr+yaZBE7tWbcN+AVT4+j9/Bvw5CSvSbIoye8DRzH17RhpXvk1QrXkAeDZwJlJDgDuZyo4/wJ4kKnhjauAxcAXgbfuYj/vYCrw7wP+AzgfWApQVT9J8vfAl5PsC5zYu2FV/SDJScCHgI8CW4CTqur7Q/tXSgOKP+ggSW1yCEWSGmWAS1KjDHBJapQBLkmNmtdvoRx00EG1YsWK+TykJDXv2muv/X5VTUxfPq8BvmLFCjZu3Difh5Sk5iWZfvcv4BCKJDXLAJekRhngktQoA1ySGmWAS1KjDHBJapQBLkmNMsAlqVEGuCQ1yh90kLRX2HD5b4/t2CuP//ZI9ttMgG868qljPf5Tb9k01uNL0nQOoUhSowxwSWqUAS5JjTLAJalRBrgkNcoAl6RGGeCS1CgDXJIaZYBLUqMGCvAkByS5OMktSTYleU6SpUnWJ9ncvS8ZdbGSpF8Z9Ar8Q8AXqupI4GhgE3AWsKGqjgA2dPOSpHkyY4AneRzwQuAcgKr6eVXdD5wMrO2arQVOGU2JkqR+BnmY1WHANuCTSY4GrgXOAJZV1V1dm7uBZf02TrIaWA1w6KGHzrlgaSF5+tqnj/X4N666cazH19wMMoSyCHgm8NGqegbwY6YNl1RVAdVv46paU1WTVTU5MTEx13olSZ1BAvwO4I6qurqbv5ipQL8nycEA3fvW0ZQoSepnxiGUqro7yfeSPKWqvgmsBL7RvVYB7+3eLxlppZo343zwPYzu4ffSQjPoDzq8FTgvyX7ArcAbmbp6vyjJ6cDtwGmjKVGS1M9AAV5V1wOTfVatHGo1kqSBeSemJDWqmd/ElKS5+M+rXje2Y688fjT79QpckhplgEtSowxwSWqUAS5JjWrmQ8zTzh5vqT4xQtIjjVfgktQoA1ySGmWAS1KjDHBJapQBLkmNMsAlqVEGuCQ1ygCXpEYZ4JLUKANckhplgEtSo5p5Foq0EN34ne+OuwQ1zCtwSWqUAS5JjTLAJalRjoFrJ+P88VcY3Q/ASgvNQAGe5DbgAeBhYHtVTSZZClwIrABuA06rqvtGU6Ykabo9GUJ5cVUdU1WT3fxZwIaqOgLY0M1LkubJXMbATwbWdtNrgVPmXI0kaWCDjoEXcFmSAj5WVWuAZVV1V7f+bmBZvw2TrAZWAxx66KFzLFeSZuePHlo57hKGbtAAf35V3Znk8cD6JLf0rqyq6sJ9J13YrwGYnJzs20aStOcGGkKpqju7963A54BjgXuSHAzQvW8dVZGSpJ3NGOBJHpPksTumgROAm4B1wKqu2SrgklEVKUna2SBDKMuAzyXZ0f78qvpCkmuAi5KcDtwOnDa6MiVJ080Y4FV1K3B0n+U/ABbepwKS1AhvpZekRhngktQoA1ySGmWAS1KjDHBJapQBLkmNMsAlqVEGuCQ1ygCXpEYZ4JLUKANckhplgEtSowxwSWqUAS5JjRr0J9W0F1mIvx0oLURegUtSowxwSWqUAS5JjXIMXNJe4cLvvG9sx34bLxjJfr0Cl6RGGeCS1CgDXJIaZYBLUqMGDvAk+yS5Lsml3fxhSa5OsiXJhUn2G12ZkqTp9uQK/AxgU8/8+4APVNXhwH3A6cMsTJK0ewMFeJLlwCuAj3fzAY4HLu6arAVOGUF9kqRdGPQK/IPA24FfdPMHAvdX1fZu/g7gkH4bJlmdZGOSjdu2bZtLrZKkHjMGeJKTgK1Vde1sDlBVa6pqsqomJyYmZrMLSVIfg9yJ+TzglUl+F1gM/AbwIeCAJIu6q/DlwJ2jK1OSNN2MV+BVdXZVLa+qFcCrgMur6rXAFcCpXbNVwCUjq1KStJO5fA/8L4Ezk2xhakz8nOGUJEkaxB49zKqqrgSu7KZvBY4dfkmSpEF4J6YkNcoAl6RGNfM88Bu/891xlyBJjyhegUtSowxwSWqUAS5JjWpmDFzzZ5y/HQij+/1AaaHxClySGmWAS1KjDHBJapRj4NIYrXjo/LEe/7axHn1+LV5y5rhLGDqvwCWpUQa4JDXKAJekRhngktQoA1ySGmWAS1KjDHBJapQBLkmNMsAlqVEGuCQ1ygCXpEYZ4JLUqBkDPMniJF9L8vUkNyd5V7f8sCRXJ9mS5MIk+42+XEnSDoNcgf8MOL6qjgaOAU5MchzwPuADVXU4cB9w+siqlCTtZMYArykPdrP7dq8Cjgcu7pavBU4ZRYGSpP4GGgNPsk+S64GtwHrg28D9VbW9a3IHcMgutl2dZGOSjdu2bRtCyZIkGDDAq+rhqjoGWA4cCxw56AGqak1VTVbV5MTExOyqlCTtZI++hVJV9wNXAM8BDkiy4xd9lgN3Drc0SdLuDPItlIkkB3TTjwZeCmxiKshP7ZqtAi4ZUY2SpD4G+U3Mg4G1SfZhKvAvqqpLk3wD+EyS9wDXAeeMsE5J0jQzBnhV3QA8o8/yW5kaD5ckjYF3YkpSowxwSWqUAS5JjTLAJalRBrgkNcoAl6RGGeCS1CgDXJIaZYBLUqMMcElqlAEuSY0ywCWpUQa4JDXKAJekRhngktQoA1ySGmWAS1KjDHBJapQBLkmNMsAlqVEGuCQ1ygCXpEYZ4JLUqBkDPMkTklyR5BtJbk5yRrd8aZL1STZ370tGX64kaYdBrsC3A2+rqqOA44A3JzkKOAvYUFVHABu6eUnSPJkxwKvqrqr67276AWATcAhwMrC2a7YWOGVENUqS+tijMfAkK4BnAFcDy6rqrm7V3cCyXWyzOsnGJBu3bds2l1olST0GDvAk+wOfBf60qn7Uu66qCqh+21XVmqqarKrJiYmJORUrSfqVgQI8yb5Mhfd5VfWv3eJ7khzcrT8Y2DqaEiVJ/QzyLZQA5wCbqur9PavWAau66VXAJcMvT5K0K4sGaPM84HXAjUmu75b9FfBe4KIkpwO3A6eNpMLOiofOH+XuZ3TbWI8+vxYvOXPcJUgawIwBXlVfArKL1SuHW44kaVDeiSlJjTLAJalRBrgkNWqQDzEljchDLztk3CXsNY6/8s1jPPqmkezVK3BJapQBLkmNMsAlqVEGuCQ1ygCXpEYZ4JLUKANckhplgEtSowxwSWqUAS5JjTLAJalRBrgkNcoAl6RGGeCS1CgDXJIaZYBLUqMMcElqlAEuSY0ywCWpUTMGeJJPJNma5KaeZUuTrE+yuXtfMtoyJUnTDXIFfi5w4rRlZwEbquoIYEM3L0maRzMGeFVdBdw7bfHJwNpuei1wynDLkiTNZLZj4Muq6q5u+m5g2ZDqkSQNaM4fYlZVAbWr9UlWJ9mYZOO2bdvmejhJUme2AX5PkoMBuvetu2pYVWuqarKqJicmJmZ5OEnSdLMN8HXAqm56FXDJcMqRJA1qkK8RXgB8BXhKkjuSnA68F3hpks3AS7p5SdI8WjRTg6p69S5WrRxyLZKkPeCdmJLUKANckhplgEtSowxwSWqUAS5JjTLAJalRBrgkNcoAl6RGGeCS1CgDXJIaZYBLUqMMcElqlAEuSY0ywCWpUQa4JDXKAJekRhngktQoA1ySGmWAS1KjDHBJapQBLkmNMsAlqVEGuCQ1ygCXpEbNKcCTnJjkm0m2JDlrWEVJkmY26wBPsg/wEeDlwFHAq5McNazCJEm7N5cr8GOBLVV1a1X9HPgMcPJwypIkzWTRHLY9BPhez/wdwLOnN0qyGljdzT6Y5JtzOOZcHAR8f7Yb531DrGThm1Nfv+VjQ6xk4ZvbeT3EQvYCs+/rzLmnn9hv4VwCfCBVtQZYM+rjzCTJxqqaHHcdewP7ev7Y1/PnkdjXcxlCuRN4Qs/88m6ZJGkezCXArwGOSHJYkv2AVwHrhlOWJGkmsx5CqartSd4CfBHYB/hEVd08tMqGb+zDOHsR+3r+2Nfz5xHX16mqcdcgSZoF78SUpEYZ4JLUqAUd4EkWJ/lakq8nuTnJu3bR7teSXNg9EuDqJCvmudTmJflEkq1JbtpNmyT5cNfPNyR55nzWuJAk2SfJdUku3cV6z+lZ2tW5nGRpkvVJNnfvS3ax/aquzeYkq0ZZ64IOcOBnwPFVdTRwDHBikuP6tDsduK+qDgc+AHjbzp47FzhxhjYvB47oXquBj464poXsDGDTbtZ7Ts/eufQ/l88CNlTVEcCGbv7/SbIUeCdTNzUeC7xzV0E/DM0GeJJndVdxi5M8prvCflpvm5ryYDe7b/fq96ntycDabvpiYGUy91unFoJB+hmgqq4C7p1hdycDn+r+X74KHJDk4FHU3aJB+zrJcuAVwMd3szvP6WmGcC739ula4JQ+bV4GrK+qe6vqPmA9M1/YzNrI78Qclaq6Jsk64D3Ao4FPV9VOf753D926Fjgc+EhVXd1nd798LED39cgfAgcyh1uUF4pB+3lA/R6/cAhw19yqXBj2oK8/CLwdeOxuduc5Pc0QzuVlVbXjXL0bWNanza7O8ZFoNsA772bqhqKHgD/p16CqHgaOSXIA8LkkT5tDAO2tZuxnDc1u+zrJScDWqro2yYvmt7QFYSjnclVVkrF/B7vZIZTOgcD+TF2JLN5dw6q6H7iC/n/O/PKxAEkWAY8DfjDMQhs3cD/PwMcvzGymvn4e8MoktzH1BNDjk3y6TzvP6f7mci7fs2PIr3vf2qfNvJ7jrQf4x4B3AOfR50OaJBPdlTdJHg28FLilz37WATs+LT4VuLy8w6nXbvt5D6wDXt99G+U44Ic9f5Jqym77uqrOrqrlVbWCqcdXXF5Vf9BnP57T/c3lXO7t01XAJX3afBE4IcmS7sPLE7plo1FVTb6A1wOf7ab3Aa5m6hsnvW1+B7gOuAG4CfibnnXvBl7ZTS8G/gXYAnwNeNK4/32PlNcg/dytu4Cpsez/ZWrc7/Ru+ZuAN3XTYepHQL4N3AhMjvvf90h6DdrXPe1fBFzaM+85PYT+3c25fCBT3z7ZDPw7sLRbPgl8vGf7P+z6fQvwxlH+m7yVXpIa1foQiiTttQxwSWqUAS5JjTLAJalRBrgkNcoAl6RGGeCS1Kj/A65tu9DOFrd6AAAAAElFTkSuQmCC",
            "text/plain": [
              "<Figure size 432x288 with 1 Axes>"
            ]
          },
          "metadata": {
            "needs_background": "light"
          },
          "output_type": "display_data"
        }
      ],
      "source": [
        "# Solve\n",
        "ampl.option[\"solver\"] = \"gurobi\"\n",
        "ampl.solve()\n",
        "# Retrieve solution\n",
        "cutvec = ampl.var[\"Cut\"].to_list(skip_index=True)\n",
        "\n",
        "# Display solution\n",
        "solution = [(patmat[p], cutvec[p]) for p in range(len(patmat)) if cutvec[p] > 0]\n",
        "cuttingPlot(roll_width, widths, solution)"
      ]
    }
  ],
  "metadata": {
    "kernelspec": {
      "display_name": "Python 3.9.13 ('venv': venv)",
      "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.13"
    },
    "vscode": {
      "interpreter": {
        "hash": "ee4198aac13dae9b6fccd443041680d99c2643c4956ef7c80ff6dcc0057cb523"
      }
    }
  },
  "nbformat": 4,
  "nbformat_minor": 2
}