## 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).