{ "cells": [ { "cell_type": "markdown", "metadata": { "colab_type": "text", "id": "mAw_uZvzOZ_u", "pycharm": {} }, "source": [ "\n", "*This notebook contains course material from [CBE40455](https://jckantor.github.io/CBE40455) by\n", "Jeffrey Kantor (jeff at nd.edu); the content is available [on Github](https://github.com/jckantor/CBE40455.git).\n", "The text is released under the [CC-BY-NC-ND-4.0 license](https://creativecommons.org/licenses/by-nc-nd/4.0/legalcode),\n", "and code is released under the [MIT license](https://opensource.org/licenses/MIT).*" ] }, { "cell_type": "markdown", "metadata": { "colab_type": "text", "id": "YD3YLBmoOZ_v", "pycharm": {} }, "source": [ "\n", "< [Pickup and Delivery](http://nbviewer.jupyter.org/github/jckantor/CBE40455/blob/master/notebooks/05.06-Pickup-and-Delivery.ipynb) | [Contents](toc.ipynb) | [Optimization under Uncertainty](http://nbviewer.jupyter.org/github/jckantor/CBE40455/blob/master/notebooks/06.00-Optimization-under-Uncertainty.ipynb) >

\"Open

\"Download\"" ] }, { "cell_type": "markdown", "metadata": { "colab_type": "text", "id": "6K_QYzxfOZ_w", "pycharm": {} }, "source": [ "# Stock Cutting" ] }, { "cell_type": "markdown", "metadata": { "colab_type": "text", "id": "5POUHhHlOZ_w", "pycharm": {} }, "source": [ "This [IPython notebook](http://ipython.org/notebook.html) demonstrates the formulation and solution of stock cutting problems using GLPK/Mathprog." ] }, { "cell_type": "markdown", "metadata": { "colab_type": "text", "id": "56QF_qjKOZ_x", "pycharm": {} }, "source": [ "## Background" ] }, { "cell_type": "markdown", "metadata": { "colab_type": "text", "id": "0nF3q5K8OZ_y", "pycharm": {} }, "source": [ "The stock cutting problem is to minimize the waste associated with cutting up stock materials to produce a set of products. Examples of the one dimensional problem include cutting lengths of steel bar into a set of products, cutting wide paper rolls into smaller ones, and cutting dimensioned lumber to meet the production needs of furniture shops.\n", "\n", "In large scale applications the stock cutting problem begins with a base set of cutting patterns. Each cutting pattern breaks a piece of stock into a set of products. The base calculation is to find a mix of cutting patterns to meet product requirements. A secondary problem is solved to find additional cutting patterns with the potential to reduce costs. The solution then proceeds iteratively with new patterns are generated 'on the fly' coupled with a branch and bound search to find an optimal solution. This approach is called 'column generation.'\n", "\n", "As demonstrated below, for small scale problems the stock cutting problem can be formulated as an assignment of product pieces to stock pieces. For this example the data consists of a list of product types, lengths and demand. The example incorporates multiple types of raw materials. The objective is to maximize the number of pieces of stock material that are left uncut.\n", "\n", "An aspect of this problem is the high degree of solution symmetry. The number of equivalent solutions is a combinatorial function of the number of identical pieces of raw of materials. In these cases a solver may quickly find a solution but then need to search many equivalent solutions to verify optimality. This example uses a weighted objective to separate otherwise equivalent solutions.\n", "\n", "To repeat, this approach will not work for larger problems due to the excessive number of binary variables required and high degree of solution symmetry. Consult the cspsol project for a solution method using column generation and glpk api." ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "colab": {}, "colab_type": "code", "id": "GTbuaqp_PE5f" }, "outputs": [], "source": [ "!apt-get install glpk-utils -qq" ] }, { "cell_type": "code", "execution_count": 2, "metadata": { "colab": { "base_uri": "https://localhost:8080/", "height": 34 }, "colab_type": "code", "executionInfo": { "elapsed": 3657, "status": "ok", "timestamp": 1557198164271, "user": { "displayName": "Jeffrey Kantor", "photoUrl": "https://lh5.googleusercontent.com/-8zK5aAW5RMQ/AAAAAAAAAAI/AAAAAAAAKB0/kssUQyz8DTQ/s64/photo.jpg", "userId": "09038942003589296665" }, "user_tz": 240 }, "id": "TX869yDlOZ_z", "outputId": "c92531af-37af-4894-a8a5-491ba04ac180", "pycharm": {} }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Overwriting input.dat\n" ] } ], "source": [ "%%writefile input.dat\n", "\n", "data;\n", "\n", "param bigM := 20;\n", "\n", "param: PRODUCTS: pLength demand :=\n", " '7m' 7 3\n", " '6m' 6 2\n", " '4m' 4 6\n", " '3m' 3 1 ;\n", " \n", "param: RAWMATERIALS: rLength avail := \n", " '15m' 15 3\n", " '10m' 10 3 ;\n", " \n", "end;" ] }, { "cell_type": "code", "execution_count": 3, "metadata": { "colab": { "base_uri": "https://localhost:8080/", "height": 850 }, "colab_type": "code", "executionInfo": { "elapsed": 4531, "status": "ok", "timestamp": 1557198165162, "user": { "displayName": "Jeffrey Kantor", "photoUrl": "https://lh5.googleusercontent.com/-8zK5aAW5RMQ/AAAAAAAAAAI/AAAAAAAAKB0/kssUQyz8DTQ/s64/photo.jpg", "userId": "09038942003589296665" }, "user_tz": 240 }, "id": "UXwWUUDFOZ_3", "outputId": "9ebdcba1-ed93-4987-d198-5c5af2f8c5d0", "pycharm": {} }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "GLPSOL: GLPK LP/MIP Solver, v4.65\n", "Parameter(s) specified in the command line:\n", " -m /dev/stdin -d input.dat -y output.txt\n", "Reading model section from /dev/stdin...\n", "86 lines were read\n", "Reading data section from input.dat...\n", "input.dat:16: warning: final NL missing before end of file\n", "16 lines were read\n", "Checking (line 16)...\n", "Generating A...\n", "Generating B...\n", "Generating C...\n", "Generating D...\n", "Generating Pieces...\n", "Model has been successfully generated\n", "GLPK Integer Optimizer, v4.65\n", "29 rows, 84 columns, 306 non-zeros\n", "78 integer variables, all of which are binary\n", "Preprocessing...\n", "6 constraint coefficient(s) were reduced\n", "28 rows, 78 columns, 294 non-zeros\n", "78 integer variables, all of which are binary\n", "Scaling...\n", " A: min|aij| = 1.000e+00 max|aij| = 1.200e+01 ratio = 1.200e+01\n", "GM: min|aij| = 8.091e-01 max|aij| = 1.236e+00 ratio = 1.528e+00\n", "EQ: min|aij| = 6.547e-01 max|aij| = 1.000e+00 ratio = 1.528e+00\n", "2N: min|aij| = 3.750e-01 max|aij| = 1.500e+00 ratio = 4.000e+00\n", "Constructing initial basis...\n", "Size of triangular part is 24\n", "Solving LP relaxation...\n", "GLPK Simplex Optimizer, v4.65\n", "28 rows, 78 columns, 294 non-zeros\n", " 0: obj = 0.000000000e+00 inf = 3.650e+01 (2)\n", " 27: obj = 2.961309524e+01 inf = 6.328e-15 (0)\n", "* 61: obj = 1.920138889e+01 inf = 1.031e-15 (0)\n", "OPTIMAL LP SOLUTION FOUND\n", "Integer optimization begins...\n", "Long-step dual simplex will be used\n", "+ 61: mip = not found yet >= -inf (1; 0)\n", "Solution found by heuristic: 140\n", "Solution found by heuristic: 120\n", "+ 18758: >>>>> 1.050000000e+02 >= 1.050000000e+02 0.0% (11; 14610)\n", "+ 18758: mip = 1.050000000e+02 >= tree is empty 0.0% (0; 14643)\n", "INTEGER OPTIMAL SOLUTION FOUND\n", "Time used: 0.9 secs\n", "Memory used: 0.7 Mb (690133 bytes)\n", "Writing products...\n", "Writing rawmaterials...\n", "Model has been successfully processed\n" ] } ], "source": [ "%%script glpsol -m /dev/stdin -d input.dat -y output.txt\n", "\n", "# Stock Cutting Problem\n", "\n", "# Products\n", "set PRODUCTS;\n", "param pLength{PRODUCTS};\n", "param demand{PRODUCTS};\n", "\n", "# Raw Materials\n", "set RAWMATERIALS;\n", "param rLength{RAWMATERIALS};\n", "param avail{RAWMATERIALS};\n", "\n", "# Big M should be greater than the length of any stock piece\n", "param bigM;\n", "check {r in RAWMATERIALS} : bigM > rLength[r];\n", "\n", "# Create indexed sets enumerating all production pieces\n", "set Q{p in PRODUCTS} := 1..demand[p] ;\n", "\n", "# Create indexed sets enumerating all raw material pieces\n", "set S{r in RAWMATERIALS} := 1..avail[r];\n", "\n", "# y[p,q,r,s] = 1 assigns (product p, piece q) to (raw material r, piece s)\n", "var y{p in PRODUCTS, q in Q[p], r in RAWMATERIALS, s in S[r]} binary;\n", "\n", "# u[r,s] = 1 indicates use of (raw material r, piece s)\n", "var u{r in RAWMATERIALS, s in S[r]} binary;\n", "\n", "# w[r,s] is the remainder left over from (raw material r, piece s)\n", "var w{r in RAWMATERIALS, s in S[r]} >= 0;\n", "\n", "# Assign product (p,q) only once to the set of all raw materials (r,s)\n", "s.t. A{p in PRODUCTS, q in Q[p]} : sum{r in RAWMATERIALS, s in S[r]} y[p,q,r,s] = 1;\n", "\n", "# Cut enough pieces to exactly meet the demand for each product\n", "s.t. B{p in PRODUCTS} : sum{q in Q[p], r in RAWMATERIALS, s in S[r]} y[p,q,r,s] = demand[p];\n", "\n", "# Do not exceed the length each piece of raw material\n", "s.t. C{r in RAWMATERIALS, s in S[r]} : \n", " sum{p in PRODUCTS, q in Q[p]} pLength[p]*y[p,q,r,s] + w[r,s] = rLength[r];\n", " \n", "# Determine if a piece (r,s) of raw material is used.\n", "s.t. D{r in RAWMATERIALS, s in S[r]} : bigM*u[r,s] >= sum{p in PRODUCTS, q in Q[p]} y[p,q,r,s];\n", "\n", "minimize Pieces : sum{r in RAWMATERIALS, s in S[r]} rLength[r]*s*u[r,s];\n", "\n", "solve;\n", "\n", "table products {p in PRODUCTS} OUT \"CSV\" \"Products.csv\" \"Table\" : \n", " p~Product, pLength[p]~Length, demand[p]~Demand;\n", "\n", "table rawmaterials {r in RAWMATERIALS} OUT \"CSV\" \"Raw_Materials.csv\" \"Table\" : \n", " r~Raw_Materials, rLength[r]~Length, avail[r]~Available;\n", "\n", "printf \"Cutting Plan\\n\";\n", "for {r in RAWMATERIALS} : {\n", " printf \" Raw Material %s \\n\", r;\n", " for {s in S[r]} : {\n", " printf \" Piece %s-%d : Remainder = %5.2f : Cut product pieces \", r,s, w[r,s];\n", " for {p in PRODUCTS} : {\n", " for {q in Q[p] : y[p,q,r,s]} : {\n", " printf \"%s-%d \", p, q;\n", " }\n", " }\n", " printf \"\\n\";\n", " }\n", " printf \"\\n\";\n", "}\n", "\n", "printf \"Production Plan\\n\";\n", "for {p in PRODUCTS} : {\n", " printf \" Product %s \\n\", p;\n", " for {q in Q[p]} : {\n", " printf \" Piece %s-%d : Cut from stock piece \", p, q;\n", " for {r in RAWMATERIALS} : {\n", " for {s in S[r] : y[p,q,r,s]} : {\n", " printf \"%s-%d \", r, s;\n", " }\n", " }\n", " printf \"\\n\";\n", " }\n", " printf \"\\n\";\n", "}\n", " \n", "end;\n" ] }, { "cell_type": "code", "execution_count": 4, "metadata": { "colab": { "base_uri": "https://localhost:8080/", "height": 578 }, "colab_type": "code", "executionInfo": { "elapsed": 4525, "status": "ok", "timestamp": 1557198165163, "user": { "displayName": "Jeffrey Kantor", "photoUrl": "https://lh5.googleusercontent.com/-8zK5aAW5RMQ/AAAAAAAAAAI/AAAAAAAAKB0/kssUQyz8DTQ/s64/photo.jpg", "userId": "09038942003589296665" }, "user_tz": 240 }, "id": "vjax7BaoOZ_7", "outputId": "d3471b1f-d12a-4bfa-b457-b098bdd25d89", "pycharm": {} }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Cutting Plan\n", " Raw Material 15m \n", " Piece 15m-1 : Remainder = 0.00 : Cut product pieces 7m-1 4m-5 4m-6 \n", " Piece 15m-2 : Remainder = 0.00 : Cut product pieces 7m-3 4m-1 4m-4 \n", " Piece 15m-3 : Remainder = 15.00 : Cut product pieces \n", "\n", " Raw Material 10m \n", " Piece 10m-1 : Remainder = 0.00 : Cut product pieces 6m-2 4m-3 \n", " Piece 10m-2 : Remainder = 0.00 : Cut product pieces 6m-1 4m-2 \n", " Piece 10m-3 : Remainder = 0.00 : Cut product pieces 7m-2 3m-1 \n", "\n", "Production Plan\n", " Product 7m \n", " Piece 7m-1 : Cut from stock piece 15m-1 \n", " Piece 7m-2 : Cut from stock piece 10m-3 \n", " Piece 7m-3 : Cut from stock piece 15m-2 \n", "\n", " Product 6m \n", " Piece 6m-1 : Cut from stock piece 10m-2 \n", " Piece 6m-2 : Cut from stock piece 10m-1 \n", "\n", " Product 4m \n", " Piece 4m-1 : Cut from stock piece 15m-2 \n", " Piece 4m-2 : Cut from stock piece 10m-2 \n", " Piece 4m-3 : Cut from stock piece 10m-1 \n", " Piece 4m-4 : Cut from stock piece 15m-2 \n", " Piece 4m-5 : Cut from stock piece 15m-1 \n", " Piece 4m-6 : Cut from stock piece 15m-1 \n", "\n", " Product 3m \n", " Piece 3m-1 : Cut from stock piece 10m-3 \n", "\n", "\n" ] } ], "source": [ "f = open(\"output.txt\")\n", "print(f.read())\n", "f.close()" ] }, { "cell_type": "code", "execution_count": 5, "metadata": { "colab": { "base_uri": "https://localhost:8080/", "height": 173 }, "colab_type": "code", "executionInfo": { "elapsed": 4520, "status": "ok", "timestamp": 1557198165164, "user": { "displayName": "Jeffrey Kantor", "photoUrl": "https://lh5.googleusercontent.com/-8zK5aAW5RMQ/AAAAAAAAAAI/AAAAAAAAKB0/kssUQyz8DTQ/s64/photo.jpg", "userId": "09038942003589296665" }, "user_tz": 240 }, "id": "pA3EVAofOZ_-", "outputId": "2eb22e86-8993-45a8-eaf8-62ef1e740bcb", "pycharm": {} }, "outputs": [ { "data": { "text/html": [ "

\n", "\n", "\n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", "
ProductLengthDemand
07m73
16m62
24m46
33m31
\n", "
" ], "text/plain": [ " Product Length Demand\n", "0 7m 7 3\n", "1 6m 6 2\n", "2 4m 4 6\n", "3 3m 3 1" ] }, "execution_count": 5, "metadata": { "tags": [] }, "output_type": "execute_result" } ], "source": [ "import pandas\n", "\n", "pandas.read_csv(\"Products.csv\")" ] }, { "cell_type": "code", "execution_count": 6, "metadata": { "colab": { "base_uri": "https://localhost:8080/", "height": 111 }, "colab_type": "code", "executionInfo": { "elapsed": 4512, "status": "ok", "timestamp": 1557198165165, "user": { "displayName": "Jeffrey Kantor", "photoUrl": "https://lh5.googleusercontent.com/-8zK5aAW5RMQ/AAAAAAAAAAI/AAAAAAAAKB0/kssUQyz8DTQ/s64/photo.jpg", "userId": "09038942003589296665" }, "user_tz": 240 }, "id": "g9eYh_9tOaAB", "outputId": "4aa3b554-714f-4fba-a434-dde8d273afb8", "pycharm": {} }, "outputs": [ { "data": { "text/html": [ "
\n", "\n", "\n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", "
Raw_MaterialsLengthAvailable
015m153
110m103
\n", "
" ], "text/plain": [ " Raw_Materials Length Available\n", "0 15m 15 3\n", "1 10m 10 3" ] }, "execution_count": 6, "metadata": { "tags": [] }, "output_type": "execute_result" } ], "source": [ "pandas.read_csv(\"Raw_Materials.csv\")" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "colab": {}, "colab_type": "code", "id": "CkdS6i-nOaAE", "pycharm": {} }, "outputs": [], "source": [] }, { "cell_type": "markdown", "metadata": { "colab_type": "text", "id": "Vg3vh0_kOaAG", "pycharm": {} }, "source": [ "\n", "< [Pickup and Delivery](http://nbviewer.jupyter.org/github/jckantor/CBE40455/blob/master/notebooks/05.06-Pickup-and-Delivery.ipynb) | [Contents](toc.ipynb) | [Optimization under Uncertainty](http://nbviewer.jupyter.org/github/jckantor/CBE40455/blob/master/notebooks/06.00-Optimization-under-Uncertainty.ipynb) >

\"Open

\"Download\"" ] } ], "metadata": { "colab": { "collapsed_sections": [], "name": "05.07-Stock-Cutting.ipynb", "provenance": [], "toc_visible": true, "version": "0.3.2" }, "kernelspec": { "display_name": "Python 2", "language": "python", "name": "python2" }, "language_info": { "codemirror_mode": { "name": "ipython", "version": 2 }, "file_extension": ".py", "mimetype": "text/x-python", "name": "python", "nbconvert_exporter": "python", "pygments_lexer": "ipython2", "version": "2.7.10" } }, "nbformat": 4, "nbformat_minor": 0 }