one-dimensional-bin-packing.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "from mip import Model, xsum, BINARY, INTEGER, OptimizationStatus\n",
    "\n",
    "import matplotlib.pyplot as plt\n",
    "import numpy as np\n",
    "import pandas as pd\n",
    "\n",
    "import ipywidgets as widgets\n",
    "\n",
    "from IPython.display import display, FileLink\n",
    "\n",
    "import uuid"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "# remove files from csv folder older that 24 hours\n",
    "!find 'files/' -name '*.*' -type f -mmin +60 -delete"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [],
   "source": [
    "wL = widgets.BoundedIntText(\n",
    "    value=6000,\n",
    "    min=0,\n",
    "    max=100000.0,\n",
    "    step=1,\n",
    "    description='Stock Length:',\n",
    "    disabled=False\n",
    ")\n",
    "\n",
    "wK = widgets.BoundedIntText(\n",
    "    value=0,\n",
    "    min=0,\n",
    "    max=10,\n",
    "    step=1,\n",
    "    description='Kerf:',\n",
    "    disabled=False\n",
    ")\n",
    "\n",
    "wG = widgets.BoundedIntText(\n",
    "    value=0,\n",
    "    min=0,\n",
    "    max=250,\n",
    "    step=1,\n",
    "    description='Green:',\n",
    "    disabled=False\n",
    ")\n",
    "\n",
    "myupload = widgets.FileUpload(\n",
    "    accept='.csv',\n",
    "    multiple=False  \n",
    ")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [],
   "source": [
    "button1 = widgets.Button(description=\"Optimise\")\n",
    "#output = widgets.Output()\n",
    "\n",
    "def on_button1_clicked(b):\n",
    "    with output:\n",
    "        out.clear_output()\n",
    "        readInCSV()\n",
    "\n",
    "button1.on_click(on_button1_clicked)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [],
   "source": [
    "button2 = widgets.Button(description=\"Try Example CSV\")\n",
    "#output = widgets.Output()\n",
    "\n",
    "def on_button2_clicked(b):\n",
    "    with output:\n",
    "        out.clear_output()\n",
    "        runExampleCSV()\n",
    "\n",
    "button2.on_click(on_button2_clicked)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [],
   "source": [
    "button3 = widgets.Button(description=\"Download Solution\")\n",
    "#output = widgets.Output()\n",
    "    \n",
    "def on_button3_clicked(b):\n",
    "            with output:\n",
    "                createLinkToFiles()                \n",
    "\n",
    "button3.on_click(on_button3_clicked)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [],
   "source": [
    "checkbox1 = widgets.Checkbox(\n",
    "    value=True,\n",
    "    description='Reduce symmetry',\n",
    "    disabled=False\n",
    ")\n",
    "output = widgets.Output()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Cutting Stock / One-dimensional Bin Packing Problem"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Upload a CSV file with column names \"Quantity\" & \"Length\".  Then click \"Optimise\".  Enjoy."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "For a description see \"Cutting Stock / One-dimensional Bin Packing Problem\" https://docs.python-mip.com/en/latest/examples.html#cutting-stock-one-dimensional-bin-packing-problem"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "application/vnd.jupyter.widget-view+json": {
       "model_id": "6e6dbe136cf049d6a03bc3cdb7d291e9",
       "version_major": 2,
       "version_minor": 0
      },
      "text/plain": [
       "VBox(children=(HBox(children=(BoundedIntText(value=6000, description='Stock Length:', max=100000),)), HBox(chi…"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "out = widgets.Output(layout={'border': '1px solid black'})\n",
    "\n",
    "row0 = widgets.HBox([wL])\n",
    "row1 = widgets.HBox([wK])\n",
    "row2 = widgets.HBox([wG])\n",
    "row3 = widgets.HBox([myupload, button1])\n",
    "row4 = widgets.HBox([checkbox1])\n",
    "row5 = widgets.HBox([out])\n",
    "row6 = widgets.HBox([button2])\n",
    "\n",
    "widgets.VBox((row0, row1, row2, row3, row4, row5, row6))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Clicking on \"Try Example\" button will optimise cutting lengths for the \"Example CSV File\" linked below.\n",
    "\n",
    "Hint 1: Run \"Try Example\" with \"Reduce symmetry\" checkbox on and off.\n",
    "\n",
    "Hint 2: If you have part of a stock length left over, enter the length that is missing in to your csv file.  For example you have 4200 left from a stock length of 6000, then add to your csv file 1, 1800."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "[Example CSV File](files/Example.csv)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [],
   "source": [
    "def readInCSV():\n",
    "    unique_filename = str(uuid.uuid4())\n",
    "\n",
    "    uploaded_filename = next(iter(myupload.value))\n",
    "    content = myupload.value[uploaded_filename]['content']\n",
    "    \n",
    "    with open('files/' + unique_filename + '.csv', 'wb') as f: f.write(content)\n",
    "\n",
    "    url='files/' + unique_filename + '.csv'\n",
    "    df1=pd.read_csv(url, sep=r'\\s*,\\s*', engine='python')\n",
    "    with out:\n",
    "        print(df1)\n",
    "        \n",
    "    !pwd\n",
    "    !echo $url\n",
    "    !rm $url\n",
    "    \n",
    "    b = df1['Quantity'].tolist()\n",
    "    w = df1['Length'].tolist()\n",
    "    \n",
    "    w = [i+wK.value for i in w] # add kerf to each cut length\n",
    "\n",
    "    optimization(b, w)\n",
    "    \n",
    "def runExampleCSV():\n",
    "    url='Example.csv'\n",
    "    df1=pd.read_csv(url, sep=r'\\s*,\\s*', engine='python')\n",
    "    with out:\n",
    "        print(df1)\n",
    "\n",
    "    b = df1['Quantity'].tolist()\n",
    "    w = df1['Length'].tolist()\n",
    "\n",
    "    optimization(b, w)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [],
   "source": [
    "def optimization(b, w):\n",
    "    L = wL.value - wG.value # stock length\n",
    "\n",
    "    n = round(sum([b[i]*w[i] for i in range(len(b))])/L+1)  # maximum number of bars\n",
    "    \n",
    "    m = len(w)  # number of requests\n",
    "\n",
    "    # creating the model\n",
    "    model = Model()\n",
    "    \n",
    "    x = {(i, j): model.add_var(obj=0, var_type=INTEGER, name=\"x[%d,%d]\" % (i, j))\n",
    "         for i in range(m) for j in range(n)}\n",
    "    y = {j: model.add_var(obj=1, var_type=BINARY, name=\"y[%d]\" % j)\n",
    "         for j in range(n)}\n",
    "\n",
    "    # constraints\n",
    "    for i in range(m):\n",
    "        model.add_constr(xsum(x[i, j] for j in range(n)) == b[i])\n",
    "    for j in range(n):\n",
    "        model.add_constr(xsum(w[i] * x[i, j] for i in range(m)) <= L * y[j])\n",
    "\n",
    "    # additional constraints to reduce symmetry\n",
    "    if checkbox1.value == True:\n",
    "        for j in range(1, n):\n",
    "            model.add_constr(y[j - 1] >= y[j])\n",
    "    \n",
    "    #model.emphasis = 1\n",
    "    \n",
    "    # optimizing the model\n",
    "    model.optimize(max_seconds=10, max_solutions=10, relax=False)\n",
    "    \n",
    "    # printing the solution\n",
    "    #print('')\n",
    "    #print('Objective value: {model.objective_value:.3}'.format(**locals()))\n",
    "    #print('Solution: ', end='')\n",
    "    #for v in model.vars:\n",
    "    #    if v.x > 1e-5:\n",
    "    #        print('{v.name} = {v.x}'.format(**locals()))\n",
    "    #        print('          ', end='')\n",
    "    \n",
    "    if model.status == OptimizationStatus.OPTIMAL or model.status == OptimizationStatus.FEASIBLE:\n",
    "        displayOptimization(model.vars, w, L)\n",
    "    with out:\n",
    "        print(model.status)    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [],
   "source": [
    "df = pd.DataFrame()\n",
    "\n",
    "def displayOptimization(mv, w, L):\n",
    "    sol = list()\n",
    "    for v in mv:\n",
    "        if v.x > 1e-5 and v.name[0] == \"x\":\n",
    "            y = (int(v.name.split(',',1)[1].replace(']', ''))) # stock length\n",
    "            l = (int(v.name.split(',',1)[0].replace('x[', ''))) # cut length\n",
    "            sol.append((y, int(v.x), w[int(l)]))\n",
    "\n",
    "\n",
    "    sorted_sol = sorted(sol, key=lambda tup: tup[0])\n",
    "\n",
    "\n",
    "    # https://stackoverflow.com/questions/61966978/convert-a-list-of-3-tuples-in-to-list-of-list-for-a-matplot-stacked-bar-chart\n",
    "\n",
    "    dx = max(x[0] for x in sorted_sol) + 1\n",
    "    predata = []\n",
    "    for x in range(dx):\n",
    "        col_data = [tup[1:] for tup in sorted_sol if tup[0] == x]\n",
    "        temp = [n * [y] for n, y in col_data]\n",
    "        predata.append([i for sublist in temp for i in sublist])\n",
    "\n",
    "    dy = max(len(x) for x in predata)\n",
    "    data = [[i.pop() if i else 0 for i in predata] for _ in range(dy)]\n",
    "    data = [[i-wK.value if i!=0 else 0 for i in j]for j in data] # remove kerf value from each cut length\n",
    "\n",
    "    plt.figure()\n",
    "\n",
    "    global df\n",
    "    df = pd.DataFrame(data).T\n",
    "    df = df.loc[(df!=0).any(axis=1)]\n",
    "    df.plot.bar(legend=False, table=True, stacked=True, title='STOCK LENGTHS')\n",
    "    plt.tick_params(\n",
    "        axis='x',          # changes apply to the x-axis\n",
    "        which='both',      # both major and minor ticks are affected\n",
    "        bottom=False,      # ticks along the bottom edge are off\n",
    "        top=False,         # ticks along the top edge are off\n",
    "        labelbottom=False) # labels along the bottom edge are off\n",
    "    #plt.xlabel('STOCK LENGTHS')\n",
    "    plt.ylabel('CUTS REQUIRED IN STOCK LENGTHS')\n",
    "    with out:\n",
    "        plt.show()\n",
    "\n",
    "        #print(\"Total length\")\n",
    "        #x = (df.sum(axis=1))\n",
    "        #print(x.sum(axis=0))\n",
    "\n",
    "        waste=L-df.sum(axis=1)\n",
    "        waste = waste.rename_axis(\"Waste for each stock length\")\n",
    "        print(waste)\n",
    "        print('\\n')\n",
    "        print(\"Total wasted \\t= \\t\" + str(waste.sum(axis=0)))\n",
    "        print('% wasted \\t= \\t'+ '{0:.2f}'.format((waste.sum(axis=0))/(L*dy)*100))\n",
    "        \n",
    "        \n",
    "        display(button3)\n",
    "           \n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [],
   "source": [
    "def createLinkToFiles():\n",
    "    global df\n",
    "\n",
    "    unique_filename = str(uuid.uuid4())\n",
    "\n",
    "    df.T.to_csv(\"files/\" + unique_filename + \".csv\", encoding='utf-8', index=False)\n",
    "    local_csv = FileLink(\"files/\" + unique_filename + \".csv\", result_html_prefix=\"Download csv file: \")\n",
    "    #df.T.to_excel(\"files/\" + unique_filename + \".xlsx\", encoding='utf-8', index=False)\n",
    "    #local_excel = FileLink(\"files/\" + unique_filename + \".xlsx\", result_html_prefix=\"Download excel file: \")\n",
    "    with out:\n",
    "        display(local_csv)\n",
    "        #display(local_excel)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "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.7.4"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}