1% BEGIN LICENSE BLOCK 2% Version: CMPL 1.1 3% 4% The contents of this file are subject to the Cisco-style Mozilla Public 5% License Version 1.1 (the "License"); you may not use this file except 6% in compliance with the License. You may obtain a copy of the License 7% at www.eclipse-clp.org/license. 8% 9% Software distributed under the License is distributed on an "AS IS" 10% basis, WITHOUT WARRANTY OF ANY KIND, either express or implied. See 11% the License for the specific language governing rights and limitations 12% under the License. 13% 14% The Original Code is The ECLiPSe Constraint Logic Programming System. 15% The Initial Developer of the Original Code is Cisco Systems, Inc. 16% Portions created by the Initial Developer are 17% Copyright (C) 2006 Cisco Systems, Inc. All Rights Reserved. 18% 19% Contributor(s): 20% 21% END LICENSE BLOCK 22 23\chapter{The Colgen Library} 24\label{chapcolgen} 25%HEVEA\cutdef[1]{section} 26 27\enableunderscores 28This chapter provides a brief introduction to the use of the {\tt 29colgen} library by comparing the solution of a simple 301-dimensional cutting stock problem --- in which we wish to minimize 31the waste in cutting stock boards of length $l$ to produce specified 32numbers of boards of various lengths ${l}_{i}$ --- by LP using {\tt lib(eplex)} and 33hybrid column generation using {\tt lib(colgen)}. 34\section{The LP Model} 35In modeling this problem as a MILP we could choose to introduce a 36variable $x_{j}$ for each feasible way of cutting a board of length 37$l$ into boards of length $l_{i}$ with coefficients $a_{ij}$ 38representing the number of boards of length $l_{i}$ obtained from the 39cutting associated with $x_{j}$ and a constraint 40$\sum_{j=1}^{n}a_{ij}x_{j}\geq b_{i}$ specifying the number of boards 41$b_{i}$ required for each length $l_{i}$; for realistic problems there 42will frequently be very many feasible cuttings and associated 43variables $x_{j}$ and as these must be enumerated before problem 44solution can begin this approach may be impractical. We could instead 45introduce for each stock board used a set of variables $x_{i,j}$ for 46each demand $i$ indicating the cutting required, a variable $w_{j}$ 47representing the resulting waste and a constraint 48$\sum_{i=1}^{m}l_{i}x_{i,j} + w_{j} = l$ ensuring the cutting is 49valid. Although we do not know how many boards will be required in the 50optimal solution, we do have an upper bound on this number 51$K_{0}=\sum_{i=1}^{m}\left\lceil b_{i}/\left\lfloor 52l/l_{i}\right\rfloor\right\rceil$ and introduce the above variable 53sets and constraint for $K_{0}$ boards. The constraints 54$\sum_{j=1}^{K_{0}}x_{ij}\geq b_{i}$ specify the number of boards 55$b_{i}$ required for each length $l_{i}$. Since all $K_{0}$ boards may 56not be required we introduce a variable $x_{j}$ denoting whether a 57board is used and modify the valid cutting constraint 58\begin{displaymath} 59\sum_{i=1}^{m}l_{i}x_{ij}+w_{j}=lx_{j} 60\end{displaymath} 61so that unused boards have zero cost in the objective function. The complete problem formulation is then: 62\begin{displaymath} 63\begin{array}{rcl} 64\mathbf{P:}\ \mathrm{minimize\ }z&=&\displaystyle{\sum_{j=1}^{K_{0}}w_{j}}\\ 65&&\\ 66\begin{array}{r@{}} 67\mathrm{subject\ to\ }\sum_{j=1}^{K_{0}}x_{ij} 68\end{array}& 69\begin{array}{c} 70\geq 71\end{array}& 72\left.\begin{array}{@{}l} 73b_{i} 74\end{array}\right.\qquad\qquad\forall i\\ 75\begin{array}{r@{}} 76\sum_{i=1}^{m}l_{i}x_{i,j}+w_{j}\\ 77%x_{j}-\sum_{i=1}^{m}x_{i,j}\\ 78%h_{i}x_{j}-x_{i,j}\\ 79w_{j}\\ 80x_{i,j}\\ 81x_{j} 82\end{array}& 83\begin{array}{c} 84=\\ 85%\leq\\ 86%\geq\\ 87\in\\ 88\in\\ 89\in 90\end{array}& 91\left.\begin{array}{@{}l} 92%\left.\begin{array}{@{}l} 93lx_{j}\\ 94%\end{array}\right.\\ 95%\left.\begin{array}{@{}l} 96%0 97%\end{array}\right.\\ 98%\left.\begin{array}{@{}l} 99%0\\ 100\left\{0,\ldots,l\right\}\\ 101\left\{0,\ldots,h_{i}\right\}\quad\forall i\\ 102%\end{array}\quad\right\}\forall i\\ 103%\left.\begin{array}{@{}l} 104\left\{0,\,1\right\} 105%\end{array}\right. 106\end{array}\quad\right\}\forall j 107\end{array} 108\end{displaymath} 109where $h_{i}=\left\lfloor l/l_{i}\right\rfloor$. This problem formulation is modeled and solved in \eclipse\ as follows: 110\begin{verbatim} 111 :- lib(eplex). 112 113 % eplex instance creation 114 :- eplex_instance(cut_stock). 115 116 lp_cut_stock(Lengths, Demands, StockLength, Vars, Cost) :- 117 ( 118 foreach(Li, Lengths), 119 foreach(Bi, Demands), 120 foreach([], XijVars0), 121 foreach(Maxi, Bounds), 122 fromto(0, KIn, KOut, K0), 123 param(StockLength) 124 do 125 KOut is KIn + fix(ceiling(Bi/floor(StockLength/Li))), 126 Maxi is fix(floor(StockLength/Li)) 127 ), 128 ( 129 for(J, 1, K0), 130 foreach(Wj, Obj), 131 foreach(Xj:Used, Vars), 132 fromto(XijVars0, VIn, VOut, XijVars), 133 param(Lengths, StockLength, Bounds) 134 do 135 cut_stock:integers([Xj,Wj]), 136 % Xj variable bounds 137 cut_stock:(Xj::0..1), 138 % Wj variable bounds 139 cut_stock:(Wj::0..StockLength), 140 ( 141 foreach(Li, Lengths), 142 foreach(Xij, Used), 143 foreach(Li*Xij, Knapsack), 144 foreach(XiVars, VIn), 145 foreach([Xij|XiVars], VOut), 146 foreach(Maxi, Bounds), 147 param(Xj) 148 do 149 % Xij variable bounds 150 cut_stock:integers(Xij), 151 cut_stock:(Xij::0..Maxi) 152 ), 153 % cutting knapsack constraint 154 cut_stock:(sum(Knapsack) + Wj =:= StockLength*Xj) 155 ), 156 ( 157 foreach(Bi, Demands), 158 foreach(Xijs, XijVars) 159 do 160 % demand constraint 161 cut_stock:(sum(Xijs) >= Bi) 162 ), 163 cut_stock:eplex_solver_setup(min(sum(Obj))), 164 % optimization call 165 cut_stock:eplex_solve(Cost). 166\end{verbatim} 167\section{The Hybrid Colgen Model} 168The cutting stock problem can be decomposed into a master problem in which an optimum combination of existing cuttings is found and a subproblem in which new cuttings are generated which could improve upon the current combination. For clarity we denote by $Q$ the set of feasible cuttings and index variables $\lambda_{\mathbf{q}}$ by the column of master problem constraint coefficients $\mathbf{q}\in Q$ corresponding to the equivalent subproblem solution: 169\begin{displaymath} 170\begin{array}{rcl} 171\mathbf{MP:}\qquad\mathrm{minimize}\qquad z&=&\sum_{\mathbf{q}\in Q}c_{\mathbf{q}}\lambda_{\mathbf{q}}\\ 172\mathrm{subject\ to}\;\ \sum_{\mathbf{q}\in Q}\mathbf{q}\lambda_{\mathbf{q}}&\geq&\mathbf{b}\\ 173\sum_{\mathbf{q}\in Q}\lambda_{\mathbf{q}}&\geq&L_{0}\\ 174\sum_{\mathbf{q}\in Q}\lambda_{\mathbf{q}}&\leq&K_{0}\\ 175\lambda_{\mathbf{q}}&\in&{0,\,1}\qquad\mathbf{q}\in Q\\ 176&&\\ 177\mathbf{SP:}\qquad\mathrm{maximize}\qquad w&=&\sum_{i=1}^{m}{u_{i}q_{i}}-c_{\mathbf{q}}\\ 178\mathrm{subject\ to}\;\sum_{i=1}^{m}{l_{i}q_{i}}&\leq&l\\ 179q_{i}&\in&\left\{0,\ldots,\left\lfloor l/l_{i}\right\rfloor\right\}\qquad i=1,\ldots,m 180\end{array} 181\end{displaymath} 182where $L_{0}=\left\lceil\sum_{i=1}^{m}b_{i}l_{i}/l\right\rceil$ and $K_{0}=\sum_{i=1}^{m}\left\lceil b_{i}/\left\lfloor l/l_{i}\right\rfloor\right\rceil$ are initial bounds on the number of stock boards required, $c_{\mathbf{q}}=l-\sum_{i=1}^{m}{l_{i}q_{i}}$, the subproblem objective function coefficients $\mathbf{u}$ represent the benefit obtained by producing boards of each type, and the subproblem is simply a general integer knapsack problem maximizing the benefit due to the boards produced by a cutting. The problem is modeled and solved as follows: 183\begin{verbatim} 184 cg_cut_stock(Lengths, Demands, StockLength, Vars, Cost) :- 185 % column generation instance creation 186 colgen_instance(cut_stock), 187 ( 188 fromto(Ids, [demand(Li)|IRest], IRest, [lower, upper]), 189 foreach(Li, Lengths), 190 foreach(Bi, Demands), 191 fromto(Q, [Qi|Rest], Rest, [Lower, Upper]), 192 foreach(Li*Qi, Knapsack), 193 fromto(0, LIn, LOut, L), 194 fromto(0, KIn, KOut, K0), 195 fromto(StockLength, CIn, COut, CMax), 196 param(StockLength) 197 do 198 LOut is LIn + Bi*Li, 199 KOut is KIn + fix(ceiling(Bi/floor(StockLength/Li))), 200 COut is min(Li-1, CIn), 201 % subproblem variable bounds 202 Max is fix(floor(StockLength/Li)), 203 ic:(Qi::0..Max), 204 % master problem column generation constraint 205 % for demand i 206 cut_stock:identified_constraint(implicit_sum(Qi) >= Bi, 207 demand(Li)) 208 ), 209 % master problem initial lower and upper bound constraints 210 L0 is fix(ceiling(L/StockLength)), 211 cut_stock:identified_constraint(implicit_sum(Lower) >= L0, 212 lower), 213 cut_stock:identified_constraint(implicit_sum(Upper) =< K0, 214 upper), 215 % subproblem cost variable bounds 216 ic:(C::0..CMax), 217 % the subproblem knapsack constraint 218 ic:(sum(Knapsack) + C =:= StockLength), 219 % subproblem structure 220 SubProblem = sp_prob{ 221 cost:C, 222 coeff_vars:Q, 223 aux:[] 224 }, 225 % optimization call 226 cut_stock:solver_setup(cutting(SubProblem, Ids), implicit_sum(C)), 227 cut_stock:solve(Cost), 228 cut_stock:get(non_zero_vars, Vars). 229\end{verbatim} 230where we first create a {\tt colgen} instance {\tt cut\_stock}, set up the variable domains of the subproblem and the demand constraints of the master problem, set up the initial master problem bound constraints and subproblem knapsack constraint, then solve and return the variables with non-zero values in the optimal solution. The definition of cutting cost as waste has been combined with the knapsack constraint, while the bounds placed on this cost exclude cuttings with sufficient waste to produce further boards, thus limiting the amount of search in subproblem solution. The chosen method of subproblem solution is: 231\begin{verbatim} 232 cutting(SubProblem, Ids) :- 233 SubProblem = sp_prob{ 234 cost:Cost, 235 coeff_vars:Vars, 236 aux:[] 237 }, 238 % sort variables in descending order of dual value 239 ( 240 fromto(Ids, [Id|IRest], IRest, [lower, upper]), 241 fromto(Vars, [Var|Rest], Rest, [1, 1]), 242 foreach(Dual-Var, KeyedVars), 243 fromto(Soln, [Id-Var|SRest], SRest, [lower-1, upper-1]) 244 do 245 cut_stock:get(dual(Id), Dual) 246 ), 247 sort(1, >=, KeyedVars, Sorted), 248 % label vars with non-negative duals to maximum values, 249 % vars with negative duals to minimum 250 ( 251 foreach(Dual-Var, Sorted) 252 do 253 ( Dual >= 0 -> label_max(Var) ; label_min(Var) ) 254 ), 255 % create solution structure and post to problem instance 256 Sol = sp_sol{ 257 cost:Cost, 258 coeff_vars:Soln, 259 aux:[] 260 }, 261 cut_stock:subproblem_solution(Sol). 262 263 label_max(Var) :- 264 get_var_bounds(Var, Lo, Hi), 265 ( Var = Hi ; 266 Hi1 is Hi - 1, 267 set_var_bounds(Var, Lo, Hi1), 268 label_max(Var) ). 269 270 label_min(Var) :- 271 get_var_bounds(Var, Lo, Hi), 272 ( Var = Lo ; 273 Lo1 is Lo + 1, 274 set_var_bounds(Var, Lo1, Hi), 275 label_min(Var) ). 276\end{verbatim} 277we first rank the variables in order of decreasing dual value, label 278to maximize those with non-negative dual value and minimize those with 279negative dual value, then construct a {\tt sp\_sol} structure and post 280it to the master problem instance. 281\disableunderscores 282 283%HEVEA\cutend 284