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