{ "cells": [ { "cell_type": "markdown", "metadata": {}, "source": [ "**Description**: Shows how to implement column generation in JuMP for solving the cutting stock problem.\n", "\n", "**Author**: Chiwei Yan\n", "\n", "**License**: \"Creative
This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License." ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "slide" } }, "source": [ "## Cutting Stock Problem Using Julia/JuMP" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "slide" } }, "source": [ "In this notebook, we deploy column generation to solve the cutting stock problem using Julia/JuMP. The origin of the cutting stock problem is in the paper industry. Given paper rolls of fixed width and a set of orders for rolls of smaller widths, the objective of the cutting stock problem is to determine how to cut the rolls into smaller widths to fulfill the orders in such a way as to minimize the amount of scrap. The cutting stock problem example we use in this notebook is from *Linear Programming* by Vasek Chvatal, 1983.\n", "\n", "Suppose that rolls are produced in a uniform width of 100 inches and that orders can be placed for rolls of widths 14 inches, 31 inches, 36 inches, and 45 inches. The company has received the following orders:\n", "\n", "\\begin{array}{|c|c|}\n", "\\hline \\textrm{Order Width} & \\textrm{Quantity} \\\\\\hline\n", " 14 & 211 \\\\\\hline\n", " 31 & 395 \\\\\\hline\n", " 36 & 610 \\\\\\hline\n", " 45 & 97 \\\\\\hline\n", "\\end{array}\n", "\n", "A single 100 inch roll can be cut into one or more of the order widths. For example, one roll could be cut into two rolls of 45 inches with a 10 inch roll of scrap.\n", "\n", "\n", "\n", "Or a roll could be cut into a roll of 45 inches, a roll of 31 inches, and a roll of 14 inches with no scrap. Each such possible combination is called a pattern. For this example, there are 37 different patterns. Determining how many of each pattern to cut to satisfy the customer orders while minimizing the scrap is too difficult to do by hand. Instead the problem can be formulated as an optimization problem, specifically an integer linear program.\n", "\n", "### Mathematical Formulation ###\n", "\n", "**Sets**\n", "- $I$ = set of order widths\n", "- $J$ = set of patterns\n", "\n", "**Parameters**\n", "- $a_{ij}$ = number of rolls of width $i$ cut in pattern $j$\n", "- $b_i$ = demand for order width $i$\n", "\n", "**Decision Variables**\n", "- $x_j$ = number of rolls cut using pattern $j$\n", "\n", "The objective of the cutting stock problem is to minimize the number of rolls cut subject to cutting enough rolls to satisfy the customer orders. Using the notation above, the problem can be formulated as follows:\n", "\n", "$$\\begin{align}\n", "\\nonumber\n", "\\min\\qquad &\\sum_{j\\in J}x_j \\\\ \\nonumber\n", "\\textrm{s.t.}\\qquad &\\sum_{j\\in J}a_{ij}x_j\\ge b_i,~\\forall i\\in I \\\\ \\nonumber\n", "&x_j\\in\\textrm{integer},~\\forall j\\in J\n", "\\end{align}$$" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "###Let's see how to formulate this problem in JuMP" ] }, { "cell_type": "code", "execution_count": 1, "metadata": { "collapsed": false }, "outputs": [ { "data": { "text/latex": [ "$$ \\begin{alignat*}{1}\\min\\quad & 0\\\\\n", "\\text{Subject to} \\quad\\end{alignat*}\n", " $$" ], "text/plain": [ "Feasibility problem with:\n", " * 0 linear constraints\n", " * 0 variables\n", "Solver set to Default" ] }, "execution_count": 1, "metadata": {}, "output_type": "execute_result" } ], "source": [ "#import necessary packages and define model\n", "# Load JuMP\n", "using JuMP\n", "using MathOptInterface\n", "# Load solver package\n", "using MathOptInterfaceXpress\n", "# shortcuts\n", "const MOI = MathOptInterface\n", "const MOIU = MathOptInterface.Utilities\n", "\n", "master = Model(optimizer = XpressOptimizer())\n", "\n", "#If Gurobi is installed (requires license), you may uncomment the code below to switch solvers\n", "#using Gurobi\n", "#master = Model(solver=GurobiSolver(Method=0)) # Switch LP algorithm to Primal Simplex, in order to enjoy warm start" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "We are now going to initialize a ***\"restricted master problem\"*** with only two variables, corresponding two cutting patterns: \n", "- width (14,31,36,45), quantity (1,1,0,1), denoted as $x_1$\n", "- width (14,31,36,45), quantity (0,0,2,0), denoted as $x_2$\n", "\n", "**\\[Recall 1\\]** what's the meaning of each variable? _Number of paper rolls cut using this pattern._\n", "\n", "**\\[Recall 2\\]** How should the formulation of the restricted master problem look like?\n", "\n", "$$\n", "\\begin{align}\n", "\\nonumber\\min\\qquad\\qquad\\quad &x_1+x_2 \\\\\n", "s.t.\\qquad\\left( \\begin{array}{c}\n", "1 \\\\\n", "1 \\\\\n", "0 \\\\\n", "1 \\end{array} \\right)&x_1+\\left( \\begin{array}{c}\n", "0 \\\\\n", "0 \\\\\n", "2 \\\\\n", "0 \\end{array} \\right)x_2 \\ge \\left( \\begin{array}{c}\n", "211 \\\\\n", "395 \\\\\n", "610 \\\\\n", "97 \\end{array} \\right) \\\\ \n", "&x_1,x_2\\ge0\n", "\\end{align}$$" ] }, { "cell_type": "code", "execution_count": 2, "metadata": { "collapsed": false }, "outputs": [ { "data": { "text/latex": [ "$$ \\begin{alignat*}{1}\\min\\quad & x_{1} + x_{2}\\\\\n", "\\text{Subject to} \\quad & x_{1} \\geq 211\\\\\n", " & x_{1} \\geq 395\\\\\n", " & 2 x_{2} \\geq 610\\\\\n", " & x_{1} \\geq 97\\\\\n", " & x_{i} \\geq 0 \\quad\\forall i \\in \\{1,2\\}\\\\\n", "\\end{alignat*}\n", " $$" ], "text/plain": [ "Minimization problem with:\n", " * 4 linear constraints\n", " * 2 variables\n", "Solver set to Default" ] }, "execution_count": 2, "metadata": {}, "output_type": "execute_result" } ], "source": [ "#define initial variables\n", "@variable(master, x[1:2] >= 0)\n", "\n", "#width\n", "w=[14 31 36 45]\n", "\n", "#constraint coefficient for initial variables\n", "A=[1 0; 1 0; 0 2; 1 0]\n", "b=[211; 395; 610; 97]\n", "\n", "\n", "#define constraint references\n", "myCons = Any[]\n", "\n", "#define constraints\n", "for i=1:4\n", " myCon = @constraint(master, dot(x, vec(A[i,:]))>=b[i])\n", " push!(myCons, myCon)\n", "end\n", "\n", "#define objective\n", "@objective(master, Min, sum(x))\n", "\n", "master" ] }, { "cell_type": "code", "execution_count": 3, "metadata": { "collapsed": false }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "\n", "Optimal Solution is:\n", "\n", "width: [14 31 36 45]\n", "Cutting Pattern: [1,1,0,1], Number of Paper Rolls Cut Using this Pattern: 395.0\n", "Cutting Pattern: [0,0,2,0], Number of Paper Rolls Cut Using this Pattern: 305.0\n" ] } ], "source": [ "JuMP.optimize(master)\n", "status = JuMP.terminationstatus(master)\n", "JuMP.resultvalue.(x)\n", "\n", "#get the optimal solution\n", "println(\"\\nOptimal Solution is:\\n\")\n", "\n", "println(\"width: \", w)\n", "\n", "epsilon=1e-6\n", "\n", "for i=1:size(A,2)\n", " \n", " if JuMP.resultvalue(x[i])>epsilon \n", " println(\"Cutting Pattern: \", A[:,i], \", Number of Paper Rolls Cut Using this Pattern: \", JuMP.resultvalue(x[i]))\n", " end\n", "end" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "**\\[Result Analysis\\]**\n", "\n", "The minimal number of paper rolls is 700. \n", "\n", "Clearly this is not the best we can do, because we are not considering all possible feasible patterns.\n", "\n", "Let's now generate some new patterns based on the value of reduced costs. Denote $r=(r_1,r_2,r_3,r_4)$ as the optimal dual price of constraints 1, 2, 3, 4. The reduced cost of a potential variable $x_k$, with cutting pattern $A_k$ can be calculated as\n", "$$rc(x_k)=1-A_k^Tr$$\n", "\n", "We want to add a potential variable $x_k$ such that $rc(x_k)<0$, this can be done by solving the following sub-problem:\n", "\n", "$$\\begin{align}\n", "z^*=\\max\\qquad &r_1a_{k,1}+r_2a_{k,2}+r_3a_{k,3}+r_4a_{k,4} \\\\\n", "s.t.\\qquad &14a_{k,1}+31a_{k,2}+36a_{k,3}+45a_{k,4}\\le 100 \\\\\n", "&a_{k,1},a_{k,2},a_{k,3},a_{k,4}\\ge0,~\\textrm{and are integers}\n", "\\end{align}$$\n", "\n", "If $z^*>1$, then $x_k$ with cutting pattern $(a_{k,1},a_{k,2},a_{k,3},a_{k,4})$ should be added to the master problem. And resolve the master problem." ] }, { "cell_type": "code", "execution_count": 4, "metadata": { "collapsed": false }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "width: [14,31,36,45]\n", "\n", "New Cutting Pattern: [0,3,0,0]\n" ] } ], "source": [ "r=[getDual(myCons)[1:4]]\n", "\n", "sub = Model(optimizer = XpressOptimizer()) \n", "\n", "#width\n", "w=[14,31,36,45]\n", "\n", "#define cutting pattern variables\n", "@variable(sub, a[1:4]>=0, Int)\n", "\n", "#define feasible cutting constraint\n", "@constraint(sub, dot(w,a)<=100)\n", "\n", "#define objective\n", "@objective(sub, Max, dot(r,a))\n", "\n", "sub\n", "\n", "JuMP.optimize(master)\n", "status = JuMP.terminationstatus(master)\n", "\n", "#print new cutting pattern\n", "pattern=[getValue(a)[1:4]]\n", "\n", "println(\"width: \", w)\n", "\n", "println(\"\\nNew Cutting Pattern: \", int(pattern))" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "**\\[Result Analysis\\]**\n", "\n", "The reduced cost of this variable is $(1-3)=-2<0$. Add this new variable to the ***\"restricted master problem\"***." ] }, { "cell_type": "code", "execution_count": 5, "metadata": { "collapsed": false }, "outputs": [ { "data": { "text/latex": [ "$$ \\begin{alignat*}{1}\\min\\quad & x_{1} + x_{2}\\\\\n", "\\text{Subject to} \\quad & x_{1} \\geq 211\\\\\n", " & x_{1} \\geq 395\\\\\n", " & 2 x_{2} \\geq 610\\\\\n", " & x_{1} \\geq 97\\\\\n", " & x_{i} \\geq 0 \\quad\\forall i \\in \\{1,2\\}\\\\\n", "\\end{alignat*}\n", " $$" ], "text/plain": [ "Minimization problem with:\n", " * 4 linear constraints\n", " * 2 variables\n", "Solver set to Default" ] }, "execution_count": 5, "metadata": {}, "output_type": "execute_result" } ], "source": [ "#model before adding new column\n", "master" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "JuMP supports column-wise modeling in defining variables. Think about it, when we add a new variable to the existing model, we need to know:\n", "\n", "- What's the coefficient for this new variable in the objective function?\n", "- Which constraint does this new variable appear? With what coefficient?" ] }, { "cell_type": "code", "execution_count": 6, "metadata": { "collapsed": false }, "outputs": [ { "data": { "text/latex": [ "$$ \\begin{alignat*}{1}\\min\\quad & x_{1} + x_{2} + z\\\\\n", "\\text{Subject to} \\quad & x_{1} \\geq 211\\\\\n", " & x_{1} + 2.9999999999999996 z \\geq 395\\\\\n", " & 2 x_{2} \\geq 610\\\\\n", " & x_{1} \\geq 97\\\\\n", " & x_{i} \\geq 0 \\quad\\forall i \\in \\{1,2\\}\\\\\n", " & z \\geq 0\\\\\n", "\\end{alignat*}\n", " $$" ], "text/plain": [ "Minimization problem with:\n", " * 4 linear constraints\n", " * 3 variables\n", "Solver set to Default" ] }, "execution_count": 6, "metadata": {}, "output_type": "execute_result" } ], "source": [ "#column-wise adding new variable z\n", "# TODO column addtion\n", "@variable(master, z>=0, objective=1, inconstraints=myCons, coefficients=pattern)\n", "\n", "#look at the master problem again\n", "master" ] }, { "cell_type": "code", "execution_count": 7, "metadata": { "collapsed": false }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "\n", "Optimal Solution is:\n", "\n", "width: [14,31,36,45]\n", "Cutting Pattern: [1,1,0,1], Number of Paper Rolls Cut Using this Pattern: 211.0\n", "Cutting Pattern: [0,0,2,0], Number of Paper Rolls Cut Using this Pattern: 305.0\n", "Cutting Pattern: [0,3,0,0], Number of Paper Rolls Cut Using this Pattern: 61.33333333333334\n" ] } ], "source": [ "#solve the master problem again\n", "JuMP.optimize(master)\n", "status = JuMP.terminationstatus(master)\n", "\n", "#get the optimal solution\n", "println(\"\\nOptimal Solution is:\\n\")\n", "\n", "println(\"width: \", w)\n", "\n", "for i=1:length(x)\n", " \n", " if JuMP.resultvalue(x[i])>epsilon\n", " println(\"Cutting Pattern: \", A[:,i], \", Number of Paper Rolls Cut Using this Pattern: \", JuMP.resultvalue(x[i]))\n", " end\n", "end\n", "\n", "\n", "if JuMP.resultvalue(z)>epsilon\n", " println(\"Cutting Pattern: \", int(pattern), \", Number of Paper Rolls Cut Using this Pattern: \", JuMP.resultvalue(z))\n", "end\n" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "**\\[Result Analysis\\]**\n", "\n", "We see that after adding a new variable, the objective value is reduced to 577.3 \n", "\n", "###Now it's time to put all pieces together###" ] }, { "cell_type": "code", "execution_count": 8, "metadata": { "collapsed": false }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Iteration 1, Master Problem Objective Value:700.0\n", "\tAdd a new variable with cutting pattern: [0.0,2.9999999999999996,0.0,0.0], reduced cost: -2.0\n", "\n", "Iteration 2, Master Problem Objective Value:577.3333333333334\n", "\tAdd a new variable with cutting pattern: [7.000000000000001,0.0,0.0,0.0], reduced cost: -3.666666666666666\n", "\n", "Iteration 3, Master Problem Objective Value:517.6190476190477\n", "Presolve 0 (-1) rows, 0 (-4) columns and 0 (-4) elements\n", "Optimal - objective value 1\n", "After Postsolve, objective 1, infeasibilities - dual 0 (0), primal 0 (0)\n", "Optimal objective 1 - 0 iterations time 0.002, Presolve 0.00\n", "Cbc0045I Solution with objective value -1 saved\n", "\tAdd a new variable with cutting pattern: [2.0,0.0,2.0,0.0], reduced cost: -0.2857142857142856\n", "\n", "Iteration 4, Master Problem Objective Value:501.33333333333337\n", "Presolve 0 (-1) rows, 0 (-4) columns and 0 (-4) elements\n", "Optimal - objective value 1\n", "After Postsolve, objective 1, infeasibilities - dual 0 (0), primal 0 (0)\n", "Optimal objective 1 - 0 iterations time 0.002, Presolve 0.00\n", "Cbc0045I Solution with objective value -1 saved\n", "\tAdd a new variable with cutting pattern: [0.0,0.0,0.0,2.0], reduced cost: -0.33333333333333326\n", "\n", "Iteration 5, Master Problem Objective Value:485.1666666666667\n", "Presolve 0 (-1) rows, 0 (-4) columns and 0 (-4) elements\n", "Optimal - objective value 1\n", "After Postsolve, objective 1, infeasibilities - dual 0 (0), primal 0 (0)\n", "Optimal objective 1 - 0 iterations time 0.002, Presolve 0.00\n", "Cbc0045I Solution with objective value -1 saved\n", "Presolve 0 (-1) rows, 0 (-4) columns and 0 (-4) elements\n", "Optimal - objective value 1\n", "After Postsolve, objective 1, infeasibilities - dual 0 (0), primal 0 (0)\n", "Optimal objective 1 - 0 iterations time 0.002, Presolve 0.00\n", "Cbc0045I Solution with objective value -1 saved\n", "\tAdd a new variable with cutting pattern: [0.0,2.0,1.0,0.0], reduced cost: -0.16666666666666674\n", "\n", "Iteration 6, Master Problem Objective Value:452.25\n", "\n", "Optimal Solution is:\n", "\n", "width: [14,31,36,45]\n", "Cutting Pattern: [2,0,2,0], Number of Paper Rolls Cut Using this Pattern: 206.25\n", "Cutting Pattern: [0,0,0,2], Number of Paper Rolls Cut Using this Pattern: 48.5\n", "Cutting Pattern: [0,2,1,0], Number of Paper Rolls Cut Using this Pattern: 197.5\n", "Presolve 0 (-1) rows, 0 (-4) columns and 0 (-4) elements\n", "Optimal - objective value 1\n", "After Postsolve, objective 1, infeasibilities - dual 0 (0), primal 0 (0)\n", "Optimal objective 1 - 0 iterations time 0.002, Presolve 0.00\n", "Cbc0045I Solution with objective value -1 saved\n", "Coin0505I Presolved problem not optimal, resolve after postsolve\n", "Coin0505I Presolved problem not optimal, resolve after postsolve\n" ] } ], "source": [ "#import necessary packages and define master problem\n", "using JuMP, Cbc\n", "master = Model() \n", "\n", "#If Gurobi is installed (requires license), you may uncomment the code below to switch solvers\n", "#using Gurobi\n", "#master = Model(solver=GurobiSolver(Method=0)) # Switch LP algorithm to Primal Simplex, in order to enjoy warm start\n", "\n", "#define initial variables\n", "@variable(master, x[1:2] >= 0)\n", "\n", "#constraint coefficient for initial variables\n", "A=[1 0; 1 0; 0 2; 1 0]\n", "b=[211; 395; 610; 97]\n", "\n", "#define constraint references (why?)\n", "@constraint myCons[1:4]\n", "\n", "#define constraints\n", "for i=1:4\n", " myCons[i] = @constraint(master, dot(x, vec(A[i,:]))>=b[i])\n", "end\n", "\n", "#define objective\n", "@objective(master, Min, sum(x))\n", "\n", "#solve master problem\n", "JuMP.optimize(master)\n", "\n", "println(\"Iteration 1, Master Problem Objective Value:\", getObjectiveValue(master))\n", "\n", "#subproblem to iteratively generate new columns\n", "\n", "#get optimal dual prices from the master problem\n", "r=[JuMP.resultdual(myCons)[1:4]]\n", "\n", "sub=Model(optimizer = XpressOptimizer()) \n", "\n", "#width\n", "w=[14,31,36,45]\n", "\n", "#define cutting pattern variables\n", "@variable(sub, a[1:4]>=0, Int)\n", "\n", "#define feasible cutting constraint\n", "@constraint(sub, dot(w,a)<=100)\n", "\n", "#define objective\n", "@objective(sub, Max, dot(r,a))\n", "\n", "#solve the subproblem\n", "JuMP.optimize(sub)\n", "\n", "sub_obj=JuMP.objectivevalue(sub);\n", "\n", "epsilon=1e-6; \n", "\n", "#list of new variables\n", "newColumns=Variable[]\n", "#pattern list\n", "A_new=Float64[];\n", "\n", "iter=2\n", "\n", "while sub_obj>1+epsilon #why?\n", "\n", " #cutting pattern (constraint coefficients) for the new variable\n", " pattern=JuMP.resultvalue(a)[1:4]\n", " \n", " #column-wise adding new variable z\n", " @variable(master, z>=0, objective=1, inconstraints=myCons, coefficients=pattern)\n", " \n", " println(\"\\tAdd a new variable with cutting pattern: \", pattern, \", reduced cost: \", (1-sub_obj))\n", " \n", " #add new variable to the new variable list\n", " push!(newColumns, z)\n", " #add new cutting pattern to pattern list\n", " append!(A_new, pattern)\n", " \n", " JuMP.optimize(master)\n", " \n", " println(\"\\nIteration \",iter, \", Master Problem Objective Value:\", JuMP.objectivevalue(master))\n", " \n", " #get new optimal dual prices\n", " r=[JuMP.resultdual(myCons)[1:4]]\n", " \n", " #modify the objective of the subproblem based on new dual prices\n", " @objective(sub, Max, dot(r,a))\n", " \n", " JuMP.optimize(sub)\n", " \n", " sub_obj=JuMP.objectivevalue(sub)\n", " \n", " iter=iter+1\n", " \n", "end\n", "\n", "#print optimal solution\n", "A_new=reshape(A_new,4, convert(Int64,length(A_new)/4))\n", "\n", "println(\"\\nOptimal Solution is:\\n\")\n", "\n", "println(\"width: \", w)\n", "\n", "for i=1:length(x)\n", " \n", " if JuMP.resultvalue(x[i])>epsilon\n", " println(\"Cutting Pattern: \", A[:,i], \", Number of Paper Rolls Cut Using this Pattern: \", JuMP.resultvalue(x[i]))\n", " end\n", "end\n", "\n", "for i=1:length(newColumns)\n", " \n", " if getValue(newColumns[i])>epsilon\n", " println(\"Cutting Pattern: \", int(A_new[:,i]), \", Number of Paper Rolls Cut Using this Pattern: \", JuMP.resultvalue(newColumns[i]))\n", " end\n", "end" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ ">**\\[Exercise and Discussion\\]**: \n", "\n", "> - Change the initial variables we use to construct the first restricted master problem (but still maintain the starting restricted master problem feasible). How does it effect the convergence of the algorithm? (number of total columns generated?)\n", "> - Could you find a way to generate multiple columns whose reduced cost are less than 0 at one iteration?" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### How to obtain INTEGER solution? ###\n", "\n", "We solve the LP relaxation successfully using column generation, however the original cutting stock problem is an integer program. Can we apply column generation to obtain optimal integer solution? \n", "\n", "The answer is _Yes_. However, it involves an advanced solution methodology called [branch-and-price](http://en.wikipedia.org/wiki/Branch_and_price) where column generation is applied on each node of the branch-and-bound tree. Unfortunately, commercial solvers (Gurobi, CPLEX) don't support this feature. Till now, the only academic solver supports branch-and-price is [SCIP](http://scip.zib.de/).\n", "\n", "Instead of solving the integer program to optimality, we here introduce two approximation methods that are widely used in solving real-world problems. " ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "#### Method 1: Rounding####\n", "\n", "Rounding a fractional solution to its _nearest_ and _feasible_ is a common heuristic for solving integer program. It's pretty problem specific. In cutting stock problem, we observe that if we _round up_ all the fractional solutions, feasibility will maintain. Thus we get our first integer solution:" ] }, { "cell_type": "code", "execution_count": 9, "metadata": { "collapsed": false }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "\n", "Integer Solution Based on Rounding is:\n", "\n", "width: [14,31,36,45]\n", "Cutting Pattern: [2,0,2,0], Number of Paper Rolls Cut Using this Pattern: 207.0\n", "Cutting Pattern: [0,0,0,2], Number of Paper Rolls Cut Using this Pattern: 49.0\n", "Cutting Pattern: [0,2,1,0], Number of Paper Rolls Cut Using this Pattern: 198.0\n", "Total Number of Paper Rolls Used: 454.0\n" ] } ], "source": [ "println(\"\\nInteger Solution Based on Rounding is:\\n\")\n", "\n", "println(\"width: \", w)\n", "\n", "summation=0\n", "\n", "for i=1:length(x)\n", " \n", " if JuMP.resultvalue(x[i])>epsilon\n", " println(\"Cutting Pattern: \", A[:,i], \", Number of Paper Rolls Cut Using this Pattern: \", ceil(JuMP.resultvalue(x[i])))\n", " summation=summation+ceil(JuMP.resultvalue(x[i]))\n", " end\n", "end\n", "\n", "for i=1:length(newColumns)\n", " \n", " if getValue(newColumns[i])>epsilon\n", " println(\"Cutting Pattern: \", int(A_new[:,i]), \", Number of Paper Rolls Cut Using this Pattern: \", ceil(JuMP.resultvalue(newColumns[i])))\n", " summation=summation+ceil(JuMP.resultvalue(newColumns[i]))\n", " end\n", "end\n", "\n", "println(\"Total Number of Paper Rolls Used: \", summation)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "We now have an integer solution using 454.0 paper rolls in total. Can we do better?" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "#### Method 2: Branch-and-Bound on Root Node ####\n", "\n", "It is troublesome to implement column generation on every node of the branch and bound tree. A common industry / research practice is to directly branch-and-bound the model only with columns generated from solving the LP relaxation. This is a heuristic because optimal set of cutting patterns for the IP might not be the same as the LP relaxation, i.e. we might lose some \"good columns\" to reach optimal integer solution. The upside is, it is very easy to implement with commercial solvers." ] }, { "cell_type": "code", "execution_count": 10, "metadata": { "collapsed": false }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "\n", "Integer Solution Based on Branch-and-Bound is:\n", "\n", "width: [14,31,36,45]\n", "Cutting Pattern: [0,0,2,0], Number of Paper Rolls Cut Using this Pattern: 100.99999999999999\n", "Cutting Pattern: [2,0,2,0], Number of Paper Rolls Cut Using this Pattern: 106.0\n", "Cutting Pattern: [0,0,0,2], Number of Paper Rolls Cut Using this Pattern: 49.0\n", "Cutting Pattern: [0,2,1,0], Number of Paper Rolls Cut Using this Pattern: 198.0\n", "Total Number of Paper Rolls Used: 454.0\n", "Presolve 0 (-4) rows, 0 (-7) columns and 0 (-11) elements\n", "Optimal - objective value 453\n", "After Postsolve, objective 453, infeasibilities - dual 0 (0), primal 0 (0)\n", "Optimal objective 453 - 0 iterations time 0.002, Presolve 0.00\n", "Cbc0045I Warning 3 integer variables were more than 1.0e-4 away from integer\n", "Cbc0045I Given objective value 452.25, computed 453\n", "Cbc0045I Solution with objective value 453 saved\n" ] } ], "source": [ "#change the solver from Clp to Cbc in order to get support for integer variables\n", "#if you use Gurobi as your solver choice, you don't need to switch solver.\n", "\n", "setSolver(master, CbcSolver())\n", "\n", "#change variable type from continuous to integer\n", "\n", "for i=1:length(x)\n", " setCategory(x[i], :Int)\n", "end\n", "\n", "for i=1:length(newColumns)\n", " setCategory(newColumns[i],:Int)\n", "end\n", "\n", "JuMP.optimize(master)\n", "\n", "\n", "#print optimal solution\n", "\n", "\n", "\n", "println(\"\\nInteger Solution Based on Branch-and-Bound is:\\n\")\n", "\n", "println(\"width: \", w)\n", "\n", "summation=0\n", "\n", "for i=1:length(x)\n", " \n", " if JuMP.resultvalue(x[i])>epsilon\n", " println(\"Cutting Pattern: \", A[:,i], \", Number of Paper Rolls Cut Using this Pattern: \", JuMP.resultvalue(x[i]))\n", " summation=summation+JuMP.resultvalue(x[i])\n", " end\n", "end\n", "\n", "for i=1:length(newColumns)\n", " \n", " if JuMP.resultvalue(newColumns[i])>epsilon\n", " println(\"Cutting Pattern: \", int(A_new[:,i]), \", Number of Paper Rolls Cut Using this Pattern: \", JuMP.resultvalue(newColumns[i]))\n", " summation=summation+JuMP.resultvalue(newColumns[i])\n", " end\n", "end\n", "\n", "println(\"Total Number of Paper Rolls Used: \", summation)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "We save one paper roll by using method 2" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "> **\\[Question\\]:**\n", "\n", "> Is method 2 always able to produce feasible integer solution?" ] } ], "metadata": { "kernelspec": { "display_name": "Julia 0.6.0", "language": "julia", "name": "julia-0.6" }, "language_info": { "file_extension": ".jl", "mimetype": "application/julia", "name": "julia", "version": "0.6.0" } }, "nbformat": 4, "nbformat_minor": 0 }