18.1 The LP Model
In modeling this problem as a MILP we could choose to introduce a
variable x_{j} for each feasible way of cutting a board of length
l into boards of length l_{i} with coefficients a_{ij}
representing the number of boards of length l_{i} obtained from the
cutting associated with x_{j} and a constraint
∑_{j=1}^{n}a_{ij}x_{j}≥ b_{i} specifying the number of boards
b_{i} required for each length l_{i}; for realistic problems there
will frequently be very many feasible cuttings and associated
variables x_{j} and as these must be enumerated before problem
solution can begin this approach may be impractical. We could instead
introduce for each stock board used a set of variables x_{i,j} for
each demand i indicating the cutting required, a variable w_{j}
representing the resulting waste and a constraint
∑_{i=1}^{m}l_{i}x_{i,j} + w_{j} = l ensuring the cutting is
valid. Although we do not know how many boards will be required in the
optimal solution, we do have an upper bound on this number
K_{0}=∑_{i=1}^{m}⌈b_{i}/⌊l/l_{i}⌋⌉ and introduce the above variable
sets and constraint for K_{0} boards. The constraints
∑_{j=1}^{K0}x_{ij}≥ b_{i} specify the number of boards
b_{i} required for each length l_{i}. Since all K_{0} boards may
not be required we introduce a variable x_{j} denoting whether a
board is used and modify the valid cutting constraint
so that unused boards have zero cost in the objective function. The complete problem formulation is then:
where h_{i}=⌊l/l_{i}⌋. This problem formulation is modeled and solved in ECL^{i}PS^{e} as follows:
:- lib(eplex).
% eplex instance creation
:- eplex_instance(cut_stock).
lp_cut_stock(Lengths, Demands, StockLength, Vars, Cost) :-
(
foreach(Li, Lengths),
foreach(Bi, Demands),
foreach([], XijVars0),
foreach(Maxi, Bounds),
fromto(0, KIn, KOut, K0),
param(StockLength)
do
KOut is KIn + fix(ceiling(Bi/floor(StockLength/Li))),
Maxi is fix(floor(StockLength/Li))
),
(
for(J, 1, K0),
foreach(Wj, Obj),
foreach(Xj:Used, Vars),
fromto(XijVars0, VIn, VOut, XijVars),
param(Lengths, StockLength, Bounds)
do
cut_stock:integers([Xj,Wj]),
% Xj variable bounds
cut_stock:(Xj::0..1),
% Wj variable bounds
cut_stock:(Wj::0..StockLength),
(
foreach(Li, Lengths),
foreach(Xij, Used),
foreach(Li*Xij, Knapsack),
foreach(XiVars, VIn),
foreach([Xij|XiVars], VOut),
foreach(Maxi, Bounds),
param(Xj)
do
% Xij variable bounds
cut_stock:integers(Xij),
cut_stock:(Xij::0..Maxi)
),
% cutting knapsack constraint
cut_stock:(sum(Knapsack) + Wj =:= StockLength*Xj)
),
(
foreach(Bi, Demands),
foreach(Xijs, XijVars)
do
% demand constraint
cut_stock:(sum(Xijs) >= Bi)
),
cut_stock:eplex_solver_setup(min(sum(Obj))),
% optimization call
cut_stock:eplex_solve(Cost).