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ⁿa_ijx_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^ml_ix_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₀=∑_i=1^m⌈b_i/⌊l/l_i⌋⌉ and introduce the above variable sets and constraint for K₀ boards. The constraints ∑_j=1^K₀x_ij≥ b_i specify the number of boards b_i required for each length l_i. Since all K₀ 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ⁱ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).