{
"cells": [
{
"cell_type": "markdown",
"metadata": {},
"source": [
"**Description:** This notebook describes how to implement column generation, which is a large scale optimization scheme, in JuMP. The cutting stock problem has been used as an illustrative example.\n",
"\n",
"**Author:** [Shuvomoy Das Gupta](http://scg.utoronto.ca/~shuvomoy.dasgupta/)\n",
"\n",
"**License:**
This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.\n",
"\n",
"# Using Julia+JuMP for optimization - column generation \n",
"--------------------------\n",
"\n",
"Implementing large scale optimization techniques such as column generation is really easy using JuMP. To explain how to implement column generation in JuMP, we consider the famous cutting stock problem. For more details about the problem, see pages 234-236 of Introduction to Linear Optimization by Bertsimas and Tsitsiklis."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Notation and notions:\n",
"\n",
"- Width of a large roll is $W$, and it needs to be cut into smaller width papers according to customer demand\n",
"- The set of indices of all feasible patterns is, $\\mathcal{J}=\\{1,2,\\ldots,n\\}$, where $n$ is a very large number\n",
"- A strict subset of $\\mathcal{J}$ that is considered in the master problem is $\\mathcal{J}'$\n",
"- The dummy index for a pattern is $j$ \n",
"- The index set of all possible paper-widths is, $\\mathcal{M}=\\{1,2,\\ldots,m\\}$\n",
"- The width of the paper with index $i$ is $w_i$\n",
"- The demand for the paper of width $w_i$ is $b_i$\n",
"- Number of smaller rolls of width $w_i$ produced by pattern $j$ is denoted by $a_{ij}$\n",
"- Number of large rolls cut according to pattern $j$ is denoted by $x_j$"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"\n",
"----------------------\n",
"## Original unabridged problem: \n",
"$$\n",
"\\begin{align}\n",
"&\\text{minimize} && \\sum_{j \\in \\mathcal{J}}{x_j} \\\\\n",
"&\\text{subject to} &&\\\\\n",
"& &&\\forall i \\in \\mathcal{M} \\quad \\sum_{j \\in \\mathcal{J}}{a_{ij} x_j}=b_i \\\\\n",
"& && \\forall j \\in \\mathcal{J} \\quad x_j \\geq 0 \\\\\n",
"\\end{align}\n",
"$$\n",
"\n",
"Because the set $\\mathcal{J}$ can be astronomically large, even storing the problem is a challenge. So, we start with a smaller version of the problem, called the master problem, by replacing $\\mathcal{J}$ with a strict subset $\\mathcal{J}'$, which is much smaller than the original one. "
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"----------------------\n",
"\n",
"## Structure of the decomposition\n",
"\n",
"**Master Problem:**\n",
"$$\n",
"\\begin{align}\n",
"&\\text{minimize} && \\sum_{j \\in \\mathcal{J}'}{x_j} \\\\\n",
"&\\text{subject to} &&\\\\\n",
"& &&\\forall i \\in \\mathcal{M} \\quad \\sum_{j \\in \\mathcal{J}'}{a_{ij} x_j}=b_i \\\\\n",
"& && \\forall j \\in \\mathcal{J}' \\quad x_j \\geq 0 \\\\\n",
"\\end{align}\n",
"$$"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"After solving the master problem, we want to check the optimality status. Structure of the cutting stock problem allows us to construct a subproblem which can do this very easily. \n",
"\n",
"**Subproblem:**\n",
"$$\n",
"\\begin{align}\n",
"&\\text{minimize} && 1 - \\sum_{i \\in \\mathcal{M}} \\quad {p_i a_{i {j^*}}} \\\\\n",
"&\\text{subject to} &&\\\\\n",
"& && \\forall i \\in \\mathcal{M} \\quad a_{i {j^*}} \\geq 0, \\quad a_{ij^*} \\; \\text{integer} \\\\\n",
"& && \\sum_{i \\in \\mathcal{M}}{w_i a_{i{j^*}}} \\leq W\\\\\n",
"\\end{align}\n",
"$$\n",
"\n"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"The objective of the subproblem is the minimum of the reduced cost vector of the original problem. If the objective value of the subproblem is greater than or equal to $0$, then the current solution of the master problem is optimal for the original unabridged problem. Otherwise, add the resultant cost reducing column $(a_{i {j^*}})_{i \\in \\mathcal{M}}=A_{j*}$ and a corresponding new variable $x_{j*}$ is added to the master problem. The modified master problem is as follows:\n",
"\n",
"**Modified Master Problem**\n",
"$$\n",
"\\begin{align}\n",
"&\\text{minimize} && \\sum_{j \\in \\mathcal{J}'}{x_j} + x_{j^*} \\\\\n",
"&\\text{subject to} &&\\\\\n",
"& &&\\forall i \\in \\mathcal{M} \\quad \\sum_{j \\in \\mathcal{J}'}{a_{ij} x_j}+a_{i j^*} x_{j^*}=b_i \\\\\n",
"& && \\forall j \\in \\mathcal{J}' \\quad x_j \\geq 0, x_j^* \\geq 0 \\\\\n",
"\\end{align}\n",
"$$\n",
"\n",
"The pseudocode for the cutting stock problem is given below."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Pseduocode\n",
"\n",
"- Input preliminary data for starting the problem\n",
"- Solve the master problem with the initial data\n",
"\n",
"$$\n",
"\\begin{align}\n",
"&\\text{minimize} && \\sum_{j \\in \\mathcal{J}'}{x_j} \\\\\n",
"&\\text{subject to} &&\\\\\n",
"& &&\\forall i \\in \\mathcal{M} \\quad \\sum_{j \\in \\mathcal{J}'}{a_{ij} x_j}=b_i \\\\\n",
"& && \\forall j \\in \\mathcal{J}' \\quad x_j \\geq 0 \\\\\n",
"\\end{align}\n",
"$$\n",
"\n"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"- Collect the dual variables for the equality constraints and store them in an array $(p_i)_{i \\in \\mathcal{M}}$\n",
"\n",
"- Solve the sub problem \n",
"\n",
"$$\n",
"\\begin{align}\n",
"&\\text{minimize} && 1 - \\sum_{i \\in \\mathcal{M}} \\quad {p_i a_{i {j^*}}} \\\\\n",
"&\\text{subject to} &&\\\\\n",
"& && \\forall i \\in \\mathcal{M} \\quad a_{i {j^*}} \\geq 0, \\quad a_{ij^*} \\; \\text{integer} \\\\\n",
"& && \\sum_{i \\in \\mathcal{M}}{w_i a_{i{j^*}}} \\leq W\\\\\n",
"\\end{align}\n",
"$$\n"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
" \n",
"- Flow control:
\n",
"\n",
"\n",
"while ( $\\text{optimal value of the subproblem} < 0$)
\n",
"> * Add the column $(a_{i {j^*}})_{i \\in \\mathcal{M}}=A_{j*}$ to $A$
\n",
"> * Add a corresponding new variable $x_{j*}$ to the list of variables
\n",
"> * Solve the modified master problem
\n",
"\n",
" $$\n",
" \\begin{align}\n",
"&\\text{minimize} && \\sum_{j \\in \\mathcal{J}'}{x_j} + x_{j^*} \\\\\n",
"&\\text{subject to} &&\\\\\n",
"& &&\\forall i \\in \\mathcal{M} \\quad \\sum_{j \\in \\mathcal{J}'}{a_{ij} x_j}+a_{i j^*} x_{j^*}=b_i \\\\\n",
"& && \\forall j \\in \\mathcal{J}' \\quad x_j \\geq 0 \\\\\n",
"& && \\qquad \\qquad \\; \\; x_{j^*} \\geq 0\n",
"\\end{align}\n",
"$$\n",
"\n",
"> * Collect the dual variables for the equality constraints and store them in an array $(p_i)_{i \\in \\mathcal{M}}$\n",
"> * Solve the sub problem as before
\n",
"> * Set $\\mathcal{J}':=\\mathcal{J}'\\cup \\{j^*\\}$
\n",
"\n",
" end while
\n",
"\n",
"- Display the results "
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Master Problem Modification in JuMP\n",
"The problem modification can be done by using the already mentioned `@variable` macro:\n",
"\n",
"$$\n",
"\\texttt{@variable}(m, l \\leq x_\\text{new} \\leq u, \\texttt{Int}, \\texttt{objective} = c_\\text{new}, \\texttt{inconstraints} = \\text{arrayConstrrefs}, \\texttt{coefficients} = \\text{arrayCoefficients}) \n",
"$$\n"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Here: \n",
"\n",
"- The name of the original model is $m$.\n",
"- The new variable to be added is $x_\\text{new}$ with lower bound $l$ and upper bound $u$.\n",
"- The type of the variable can be `Int`, `Bin`. For real variable the third argument is left vacant.\n",
"- The original objective, say $f_o(x)$ will become $f_o(x) + c_\\text{new} x_\\text{new}$ after modification\n",
"- The array $\\texttt{arrayConstrrefs}$ contain references to those constraints that need to be modified by inclusion of $x_\\text{new}$\n",
"- The array $\\texttt{arrayCoefficients}$ contain the coefficients that have to multiplied with $x_\\text{new}$ and then added to the constraints referenced by $\\texttt{arrayConstrrefs}$ in an orderly manner. For example, if the $i$th element of $\\texttt{arrayConstrrefs}$ refers to a constraint $a_i^T x \\lesseqgtr b_i$, then after invoking the command, the constraint is modified as:\n",
"$a_i^T x +\\texttt{arrayCoefficients}[i] x_\\text{new} \\lesseqgtr b_i$"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Implementing one iteration of the column generation algorithm\n",
"\n",
"To understand how the column generation is working in Julia, we implement one iteration of the column generation algorithm manually. The entire code is presented in the next section.\n"
]
},
{
"cell_type": "code",
"execution_count": 1,
"metadata": {
"collapsed": false
},
"outputs": [],
"source": [
"# Uploading the packages:\n",
"# -----------------------\n",
"\n",
"using JuMP \n",
"\n",
"# We will use default solvers"
]
},
{
"cell_type": "code",
"execution_count": 2,
"metadata": {
"collapsed": false
},
"outputs": [
{
"data": {
"text/plain": [
"5-element Array{Int64,1}:\n",
" 22\n",
" 42\n",
" 52\n",
" 53\n",
" 78"
]
},
"execution_count": 2,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"# Input preliminary data for starting the problem\n",
"# -----------------------------------------------\n",
"\n",
"W=100\n",
"cardinalityM=5\n",
"M=collect(1:cardinalityM)\n",
"A=eye(cardinalityM)\n",
"p=zeros(5)\n",
"b=[45; 38; 25; 11; 12]\n",
"w=[22; 42; 52; 53; 78]"
]
},
{
"cell_type": "code",
"execution_count": 3,
"metadata": {
"collapsed": false
},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"Min x[1] + x[2] + x[3] + x[4] + x[5]\n",
"Subject to\n",
" x[1] == 45\n",
" x[2] == 38\n",
" x[3] == 25\n",
" x[4] == 11\n",
" x[5] == 12\n",
" 0 <= x[i] <= 1.0e6 for all i in {1,2,..,4,5}\n"
]
}
],
"source": [
"# Description of the master problem with the initial data\n",
"#----------------------\n",
"\n",
"cutstockMain = Model() # Model for the master problem\n",
"Jprime=collect(1:size(A,2)) # Initial number of variables\n",
"@variable(cutstockMain, 0 <= x[Jprime] <= 1000000) # Defining the variables\n",
"@objective(cutstockMain, Min, sum(1*x[j] for j in Jprime)) # Setting the objective\n",
"@constraint(cutstockMain, consRef[i=1:cardinalityM], sum(A[i,j]*x[j] for j in Jprime)==b[i]) \n",
"# Here the second argument consRef[i=1:cardinalityM] means that the i-th constraint aᵢᵀx = bᵢ has the corresponding constraint reference\n",
"# consRef[i]\n",
"print(cutstockMain)"
]
},
{
"cell_type": "code",
"execution_count": 4,
"metadata": {
"collapsed": false
},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"Current solution of the master problem is x: 1 dimensions:\n",
"[1] = 45.0\n",
"[2] = 38.0\n",
"[3] = 25.0\n",
"[4] = 11.0\n",
"[5] = 12.0\n",
"\n",
"Current objective value of the master problem is 131.0\n"
]
}
],
"source": [
"# Solving the master problem with the initial data\n",
"# ------------------------------------------------\n",
"solve(cutstockMain)\n",
"println(\"Current solution of the master problem is \", getvalue(x))\n",
"println(\"Current objective value of the master problem is \", getobjectivevalue(cutstockMain))"
]
},
{
"cell_type": "code",
"execution_count": 5,
"metadata": {
"collapsed": false
},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"The array storing the dual variables is [1.0,1.0,1.0,1.0,1.0]\n"
]
}
],
"source": [
"#Collect the dual variables for the equality constraints and store them in an array p\n",
"for i in M\n",
" p[i] = getdual(consRef[i]) # These p[i] are the input data for the subproblem\n",
"end \n",
"println(\"The array storing the dual variables is \", p)"
]
},
{
"cell_type": "code",
"execution_count": 6,
"metadata": {
"collapsed": false
},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"Min -Ajstar[1] - Ajstar[2] - Ajstar[3] - Ajstar[4] - Ajstar[5] + 1\n",
"Subject to\n",
" 22 Ajstar[1] + 42 Ajstar[2] + 52 Ajstar[3] + 53 Ajstar[4] + 78 Ajstar[5] <= 100\n",
" 0 <= Ajstar[i] <= 1.0e6, integer, for all i in {1,2,..,4,5}\n"
]
}
],
"source": [
"# Describe the sub problem\n",
"# ------------------------\n",
"cutstockSub=Model() # Model for the subproblem\n",
"@variable(cutstockSub, 0 <= Ajstar[M] <= 1000000, Int )\n",
"@objective(cutstockSub, Min, 1-sum(p[i]*Ajstar[i] for i in M))\n",
"@constraint(cutstockSub, sum(w[i]*Ajstar[i] for i in M) <= W)\n",
"print(cutstockSub)"
]
},
{
"cell_type": "code",
"execution_count": 7,
"metadata": {
"collapsed": false
},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"The minimum component of the reduced cost vector is -3.0\n"
]
}
],
"source": [
"# Solve the sub problem\n",
"# ---------------------\n",
"solve(cutstockSub)\n",
"minreducedCost=getobjectivevalue(cutstockSub)\n",
"println(\"The minimum component of the reduced cost vector is \", minreducedCost)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"The minimum component of the reduced cost vector is negative, so we have a suboptimal solution."
]
},
{
"cell_type": "code",
"execution_count": 8,
"metadata": {
"collapsed": false
},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"We have a cost reducing column Ajstar: 1 dimensions:\n",
"[1] = 4.0\n",
"[2] = 0.0\n",
"[3] = 0.0\n",
"[4] = 0.0\n",
"[5] = 0.0\n",
"\n"
]
}
],
"source": [
"if minreducedCost >= 0\n",
" println(\"We are done, current solution of the master problem is optimal\")\n",
"else\n",
" println(\"We have a cost reducing column \", getvalue(Ajstar))\n",
"end\n"
]
},
{
"cell_type": "code",
"execution_count": 9,
"metadata": {
"collapsed": false
},
"outputs": [
{
"data": {
"text/plain": [
"JuMP.JuMPArray{JuMP.Variable,1,Tuple{Array{Int64,1}}}"
]
},
"execution_count": 9,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"typeof(Ajstar)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Now `Ajstar` is of type JuMPDict. To use it in the modified master problem, we have to store values from `Ajstar` in a column vector."
]
},
{
"cell_type": "code",
"execution_count": 10,
"metadata": {
"collapsed": false
},
"outputs": [],
"source": [
"Anew=Float64[] # This Anew correspond to the newly added column to the A matrix\n",
"for i in 1:cardinalityM\n",
" push!(Anew, getvalue(Ajstar)[i])\n",
"end"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"When we add the cost reducing column `Anew` to the original matrix `A`, it also gives rise to a new variable `xNew` corresponding to `Anew`. Now we want to keep track of the new variables that are added by the subproblem. We do this by declaring an array of `Variable`s named `xNewArray`, which will contain all such newly added variables in the process of column generation. "
]
},
{
"cell_type": "code",
"execution_count": 11,
"metadata": {
"collapsed": false
},
"outputs": [
{
"data": {
"text/latex": [
"$$ Empty Array{Variable} (no indices) $$"
],
"text/plain": [
"0-element Array{JuMP.Variable,1}"
]
},
"execution_count": 11,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"xNewArray=Variable[] # The newly added variables by flow control will be\n",
"# pushed to the new array of variables xNewArray"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Here we just illustrate one iteration of the while loop manually, because, for now, we are interested to understand how JuMP is managing the flow control and modifying the master problem and the sub problem. \n",
"\n",
"Let's modify the master problem by adding the new column `Anew` to the old `A` matrix. Note that we do not have to rewrite the entire model."
]
},
{
"cell_type": "code",
"execution_count": 12,
"metadata": {
"collapsed": false
},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"Min x[1] + x[2] + x[3] + x[4] + x[5] + xNew\n",
"Subject to\n",
" x[1] + 4 xNew == 45\n",
" x[2] == 38\n",
" x[3] == 25\n",
" x[4] == 11\n",
" x[5] == 12\n",
" 0 <= x[i] <= 1.0e6 for all i in {1,2,..,4,5}\n",
" 0 <= xNew <= 1.0e6\n"
]
}
],
"source": [
"# Modify the master problem by adding the new column Anew to the old A matrix\n",
"@variable(\n",
"cutstockMain, # Model to be modified\n",
"0 <= xNew <= 1000000, # New variable to be added\n",
"objective=1, # cost coefficient of new variable in the objective\n",
"inconstraints=consRef, # constraints to be modified\n",
"coefficients=Anew # the coefficients of the variable in those constraints\n",
") \n",
"\n",
"# The line above adds the column (aᵢⱼ*)ᵢ=Aⱼ* to A
\n",
"# and add a corresponding new variable xⱼ* to the list of variable\n",
"\n",
"push!(xNewArray, xNew) # Pushing the new variable in the array of new variables\n",
"print(cutstockMain)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Though we are showing only one iteration of the flow control, in the final code for sure we want to have a \n",
">```\n",
"while ( some condition )\n",
"(\n",
"...\n",
")\n",
"end\n",
"```\n",
"\n",
"block. \n",
"\n",
"Now if we do not do anything else in the final code, all the names of the newly added variables by the `while` loop will be the same: `xNew`! JuMP is intelligent enough to treat them as separate variables, but it is not very human-friendly. It is more convenient if the newly added variables were given different names, which we can achieve by `setName(oldName, newName)` function.\n"
]
},
{
"cell_type": "code",
"execution_count": 13,
"metadata": {
"collapsed": false
},
"outputs": [
{
"data": {
"text/plain": [
"\"x[6]\""
]
},
"execution_count": 13,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"setname(xNew, string(\"x[\",size(A,2)+1,\"]\")) # Changing the name of the variable \n",
"# otherwise all the newly added variables will have name xNew!\n",
"# size(A,2) gives the column number of A"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Let us see if the name of the variable has changed as desired."
]
},
{
"cell_type": "code",
"execution_count": 14,
"metadata": {
"collapsed": false
},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"Min x[1] + x[2] + x[3] + x[4] + x[5] + x[6]\n",
"Subject to\n",
" x[1] + 4 x[6] == 45\n",
" x[2] == 38\n",
" x[3] == 25\n",
" x[4] == 11\n",
" x[5] == 12\n",
" 0 <= x[i] <= 1.0e6 for all i in {1,2,..,4,5}\n",
" 0 <= x[6] <= 1.0e6\n"
]
}
],
"source": [
"print(cutstockMain) # Let us see if the name of the variables have changed as desired"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Indeed it has! Now let's solve the modified master problem, and then collect the associated dual variables for the equality constraints and store them in the array `p`."
]
},
{
"cell_type": "code",
"execution_count": 15,
"metadata": {
"collapsed": false
},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"[0.25,1.0,1.0,1.0,1.0]\n"
]
}
],
"source": [
"statusControlFlow=solve(cutstockMain) # Solve the modified master problem\n",
"\n",
"getdual(consRef)\n",
"for i in M\n",
" p[i] = getdual(consRef)[i] \n",
"end \n",
"\n",
"println(p)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Now we solve the subproblem for the current solution of the master problem:"
]
},
{
"cell_type": "code",
"execution_count": 16,
"metadata": {
"collapsed": false
},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"Min -0.25 Ajstar[1] - Ajstar[2] - Ajstar[3] - Ajstar[4] - Ajstar[5] + 1\n",
"Subject to\n",
" 22 Ajstar[1] + 42 Ajstar[2] + 52 Ajstar[3] + 53 Ajstar[4] + 78 Ajstar[5] <= 100\n",
" 22 Ajstar[1] + 42 Ajstar[2] + 52 Ajstar[3] + 53 Ajstar[4] + 78 Ajstar[5] <= 100\n",
" 0 <= Ajstar[i] <= 1.0e6, integer, for all i in {1,2,..,4,5}\n",
" 0 <= Ajstar[i] <= 1.0e6, integer, for all i in {1,2,..,4,5}\n",
"Current value of the minimum of the reduced cost vector is -1.0\n"
]
},
{
"name": "stderr",
"output_type": "stream",
"text": [
"WARNING: Solver does not appear to support providing initial feasible solutions.\n"
]
}
],
"source": [
"# Solving the modified sub problem \n",
"@variable(cutstockSub, 0 <= Ajstar[M] <= 1000000, Int )\n",
"@objective(cutstockSub, Min, 1-sum(p[i]*Ajstar[i] for i in M))\n",
"@constraint(cutstockSub, sum(w[i]*Ajstar[i] for i in M) <= W)\n",
"print(cutstockSub) # Let's see what is the current subproblem looks like\n",
"solve(cutstockSub)\n",
"minReducedCost=getobjectivevalue(cutstockSub)\n",
"println(\"Current value of the minimum of the reduced cost vector is \", minReducedCost)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"The optimal value of the current subproblem is negative (which will be tested by the conditional statement of the while loop in the final code), giving us a cost reducing column to be added in the master problem. As before we have to store the column `Ajstar` in a column vector `Anew`."
]
},
{
"cell_type": "code",
"execution_count": 17,
"metadata": {
"collapsed": false
},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"New column to be added to A is: [0.0,2.0,0.0,0.0,0.0]\n"
]
}
],
"source": [
"#Store the components of the solution of current subproblem into the column Anew \n",
"Anew=Float64[]\n",
"for i in 1:cardinalityM\n",
" push!(Anew, getvalue(Ajstar)[i])\n",
"end\n",
"\n",
"println(\"New column to be added to A is: \", Anew)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Okay, we have understood how JuMP is working in the column generation process. The entire code of the cutting stock problem is given below:"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Cutting stock problem code:"
]
},
{
"cell_type": "code",
"execution_count": 18,
"metadata": {
"collapsed": false
},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
" 0.003651 seconds (4.00 k allocations: 265.625 KB)\n",
"Objective value: 57.25\n",
"Current Solution is: x: 1 dimensions:\n",
"[1] = 0.0\n",
"[2] = 0.0\n",
"[3] = 0.0\n",
"[4] = 0.0\n",
"[5] = 0.0\n",
"\n",
"With 5 variables added by flow control:\n",
"[6] = 8.25\n",
"[7] = 1.0\n",
"[8] = 11.0\n",
"[9] = 25.0\n",
"[10] = 12.0\n",
"Reduced cost of the current solution is 0.0\n"
]
}
],
"source": [
"# Verfied to be working:\n",
"\n",
"# Uploading the packages:\n",
"# -----------------------\n",
"\n",
"using JuMP\n",
"using GLPKMathProgInterface\n",
"\n",
"# Input preliminary data for starting the problem\n",
"# -----------------------------------------------\n",
"\n",
"W=100\n",
"cardinalityM=5\n",
"M=collect(1:cardinalityM)\n",
"A=eye(cardinalityM)\n",
"p=zeros(5)\n",
"b=[45; 38; 25; 11; 12]\n",
"w=[22; 42; 52; 53; 78]\n",
"\n",
"@time begin # time measurement begins\n",
"\n",
"# Solve the master problem with the initial data\n",
"#-----------------------------------------------\n",
"\n",
"cutstockMain = Model() # Model for the master problem\n",
"Jprime=collect(1:size(A,2)) # Intial number of variables\n",
"@variable(cutstockMain, 0 <= x[Jprime] <= 1000000) # Defining the variables\n",
" \n",
"@objective(cutstockMain, Min, sum(1*x[j] for j in Jprime)) # Setting the objective\n",
" \n",
"@constraint(cutstockMain, consRef[i=1:cardinalityM], sum(A[i,j]*x[j] for j in Jprime)==b[i]) # Adding the constraints\n",
"# Here the second argument consRef[i=1:cardinalityM] means that the i-th constraint aᵢᵀx = bᵢ has \n",
"# the corresponding constraint reference consRef[i]\n",
"\n",
"solve(cutstockMain)\n",
" \n",
"#Collect the dual variables for the equality constraints and store them in an array p\n",
"getdual(consRef)\n",
"for i in M\n",
" p[i] = getdual(consRef)[i] # These p[i] are the input data for the subproblem\n",
"end \n",
"\n",
"# Solve the sub problem\n",
"# -------------------\n",
"\n",
"cutstockSub=Model() # Model for the subproblem\n",
"@variable(cutstockSub, 0 <= Ajstar[M] <= 1000000, Int )\n",
"@objective(cutstockSub, Min, 1-sum(p[i]*Ajstar[i] for i in M))\n",
"@constraint(cutstockSub, sum(w[i]*Ajstar[i] for i in M) <= W)\n",
"solve(cutstockSub)\n",
"minReducedCost=getobjectivevalue(cutstockSub)\n",
"\n",
"Anew=Float64[] # This Anew correspond to the newly added column to the A matrix\n",
"for i in 1:cardinalityM\n",
" push!(Anew, getvalue(Ajstar)[i])\n",
"end\n",
"\n",
"xNewArray=Variable[] # The newly added variables by flow control will be pushed to the new array of variables xNewArray\n",
"\n",
"k=1 # Counter for the while loop\n",
"\n",
" # Flow control\n",
" # ------------\n",
"\n",
"while minReducedCost < 0 #while (current solution of the master problem is suboptimal, i.e., subproblem objective value < 0)\n",
" # Solve the master problem by adding the new column Anew to the old A matrix\n",
" @variable(\n",
" cutstockMain, # Model to be modified\n",
" 0 <= xNew <= 1000000, # New variable to be added\n",
" objective=1, # cost coefficient of new varaible in the objective\n",
" inconstraints=consRef, # constraints to be modified\n",
" coefficients=Anew # the coefficients of the variable in those constraints\n",
" ) \n",
" # The line above adds the column (aᵢⱼ*)ᵢ=Aⱼ* to A
\n",
" # and add a corresponding new variable xⱼ* to the list of variable\n",
" push!(xNewArray, xNew) # Pushing the new variable in the array of new variables\n",
" setname(xNew, string(\"x[\",size(A,2)+k,\"]\")) # Changing the name of the variable \n",
" # otherwise all the newly added variables will have name xNew!\n",
" k=k+1 # Increasing k by 1\n",
" statusControlFlow=solve(cutstockMain)\n",
"\n",
" #Collect the dual variables for the equality constraints and store them in an array p\n",
" getdual(consRef)\n",
" for i in M\n",
" p[i] = getdual(consRef)[i] \n",
" end \n",
"\n",
" # Solving the modified sub problem \n",
" @variable(cutstockSub, 0 <= Ajstar[M] <= 1000000, Int )\n",
" @objective(cutstockSub, Min, 1-sum{p[i]*Ajstar[i],i in M})\n",
" @constraint(cutstockSub, sum{w[i]*Ajstar[i], i in M} <= W)\n",
" solve(cutstockSub)\n",
" minReducedCost=getobjectivevalue(cutstockSub)\n",
"\n",
" #Store the components of the solution of current subproblem into the column Anew \n",
" Anew=Float64[]\n",
" for i in 1:cardinalityM\n",
" push!(Anew, getvalue(Ajstar)[i])\n",
" end\n",
" end # While loop ends\n",
" \n",
"end # time measurement ends\n",
"\n",
"# Print the results\n",
"# -----------------\n",
"\n",
"println(\"Objective value: \", getobjectivevalue(cutstockMain))\n",
"println(\"Current Solution is: \", getvalue(x))\n",
"println(\"With \", length(xNewArray), \" variables added by flow control:\")\n",
"for i in 1:length(xNewArray)\n",
" println(\"[\",size(A,2)+i,\"] = \",getvalue(xNewArray[i]))\n",
"end\n",
"println(\"Reduced cost of the current solution is \", getobjectivevalue(cutstockSub))"
]
}
],
"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
}