The 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 λq by the column of master problem constraint coefficients q∈ Q corresponding to the equivalent subproblem solution:
|
where L0=⌈∑i=1mbili/l⌉ and K0=∑i=1m⌈bi/⌊l/li⌋⌉ are initial bounds on the number of stock boards required, cq=l−∑i=1mliqi, the subproblem objective function coefficients 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:
cg_cut_stock(Lengths, Demands, StockLength, Vars, Cost) :-
% column generation instance creation
colgen_instance(cut_stock),
(
fromto(Ids, [demand(Li)|IRest], IRest, [lower, upper]),
foreach(Li, Lengths),
foreach(Bi, Demands),
fromto(Q, [Qi|Rest], Rest, [Lower, Upper]),
foreach(Li*Qi, Knapsack),
fromto(0, LIn, LOut, L),
fromto(0, KIn, KOut, K0),
fromto(StockLength, CIn, COut, CMax),
param(StockLength)
do
LOut is LIn + Bi*Li,
KOut is KIn + fix(ceiling(Bi/floor(StockLength/Li))),
COut is min(Li-1, CIn),
% subproblem variable bounds
Max is fix(floor(StockLength/Li)),
ic:(Qi::0..Max),
% master problem column generation constraint
% for demand i
cut_stock:identified_constraint(implicit_sum(Qi) >= Bi,
demand(Li))
),
% master problem initial lower and upper bound constraints
L0 is fix(ceiling(L/StockLength)),
cut_stock:identified_constraint(implicit_sum(Lower) >= L0,
lower),
cut_stock:identified_constraint(implicit_sum(Upper) =< K0,
upper),
% subproblem cost variable bounds
ic:(C::0..CMax),
% the subproblem knapsack constraint
ic:(sum(Knapsack) + C =:= StockLength),
% subproblem structure
SubProblem = sp_prob{
cost:C,
coeff_vars:Q,
aux:[]
},
% optimization call
cut_stock:solver_setup(cutting(SubProblem, Ids), implicit_sum(C)),
cut_stock:solve(Cost),
cut_stock:get(non_zero_vars, Vars).
where we first create a colgen instance 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:
cutting(SubProblem, Ids) :-
SubProblem = sp_prob{
cost:Cost,
coeff_vars:Vars,
aux:[]
},
% sort variables in descending order of dual value
(
fromto(Ids, [Id|IRest], IRest, [lower, upper]),
fromto(Vars, [Var|Rest], Rest, [1, 1]),
foreach(Dual-Var, KeyedVars),
fromto(Soln, [Id-Var|SRest], SRest, [lower-1, upper-1])
do
cut_stock:get(dual(Id), Dual)
),
sort(1, >=, KeyedVars, Sorted),
% label vars with non-negative duals to maximum values,
% vars with negative duals to minimum
(
foreach(Dual-Var, Sorted)
do
( Dual >= 0 -> label_max(Var) ; label_min(Var) )
),
% create solution structure and post to problem instance
Sol = sp_sol{
cost:Cost,
coeff_vars:Soln,
aux:[]
},
cut_stock:subproblem_solution(Sol).
label_max(Var) :-
get_var_bounds(Var, Lo, Hi),
( Var = Hi ;
Hi1 is Hi - 1,
set_var_bounds(Var, Lo, Hi1),
label_max(Var) ).
label_min(Var) :-
get_var_bounds(Var, Lo, Hi),
( Var = Lo ;
Lo1 is Lo + 1,
set_var_bounds(Var, Lo1, Hi),
label_min(Var) ).
we first rank the variables in order of decreasing dual value, label to maximize those with non-negative dual value and minimize those with negative dual value, then construct a sp_sol structure and post it to the master problem instance.