bchstock.gms : Cutting Stock - A Column Generation Approach with BCH

**Description**

The task is to cut out some paper products of different sizes from a large raw paper roll, in order to meet a customer's order. The objective is to minimize the required number of paper rolls. The CG method is implemented using BCH. The running LP solver calls out to a BCH pricing call and that supplies new columns.

**References**

- Gilmore, P C, and Gomory, R E, A Linear Programming Approach to the Cutting Stock Problem, {Part I}. Operations Research 9 (1961), 849–859.
- Gilmore, P C, and Gomory, R E, A Linear Programming Approach to the Cutting Stock Problem, {Part II}. Operations Research 11 (1963), 863–888.

**Small Model of Type :** MIP

**Category :** GAMS Model library

**Main file :** bchstock.gms

```
$title Cutting Stock - A Column Generation Approach with BCH (BCHSTOCK,SEQ=349)
$onText
The task is to cut out some paper products of different sizes from a
large raw paper roll, in order to meet a customer's order. The objective
is to minimize the required number of paper rolls.
The CG method is implemented using BCH. The running LP solver calls
out to a BCH pricing call and that supplies new columns.
P. C. Gilmore and R. E. Gomory, A linear programming approach to the
cutting stock problem, Part I, Operations Research 9 (1961), 849-859.
P. C. Gilmore and R. E. Gomory, A linear programming approach to the
cutting stock problem, Part II, Operations Research 11 (1963), 863-888.
Keywords: mixed integer linear programming, cutting stock, column generation,
branch and cut and heuristic faciliy, paper industry
$offText
$eolCom //
Set
i 'widths' / w1*w4 /
p 'patterns' / p1*p10 /;
Parameter
r 'raw width' / 100 /
w(i) 'width' / w1 45, w2 36, w3 31, w4 14 /
d(i) 'demand' / w1 97, w2 610, w3 395, w4 211 /
aip(i,p) 'number of width i in pattern growing in p';
* Master model
Variable
xp(p) 'patterns used'
z 'objective variable';
Integer Variable xp;
xp.up(p) = sum(i, d(i));
Equation
numpat 'number of patterns used'
demand(i) 'meet demand';
numpat.. sum(p, xp(p)) =e= z;
demand(i).. sum(p, aip(i,p)*xp(p)) =g= d(i);
Model master / numpat, demand /;
* Initialization - the initial patterns have a single width
aip(i,p)$(ord(i) = ord(p)) = floor(r/w(i));
$echo userpricingcall pricing.gms > cplexd.opt
execute_unload 'data', i, w, d, r;
z.lo = 0; // We need to prevent reformulation for now
option rmip = cplexd, optCr = 0; master.optFile = 1;
solve master using rmip minimizing z;
* Read back the additional columns
Set
cols 'column' / 1*1000 /
cc(cols) 'new columns'
info 'column info' / level, lower, upper /;
Parameter
demand_c(cols,i) 'patterns generated'
col_info(cols, info);
execute_load 'bchsol.gdx', col_info, demand_c;
option cc < col_info;
* Fill the aip data with the new patters
loop((cc(cols),p)$(ord(cols) = ord(p) - card(i) + 1), aip(i,p) = demand_c(cols,i));
master.optFile = 0;
solve master using mip minimizing z;
abort$(master.modelStat <> 1 or abs(z.l - 453) > 1e-6) 'wrong solution';
$onEchoV > pricing.gms
Set i;
Parameter w(i), d(i), r;
$gdxIn data
$load i w d r
Equation demand(i);
$gdxIn bchout
$load demand
* Pricing problem - Knapsack model
Variable
z
y(i) 'new pattern';
Integer Variable y;
y.up(i) = ceil(r/w(i));
Equation defobj, knapsack;
defobj.. z =e= 1 - sum(i, demand.m(i)*y(i));
knapsack.. sum(i, w(i)*y(i)) =l= r;
Model pricing / defobj, knapsack /;
option optCr = 0;
solve pricing using mip minimizing z;
Set cc / 1 /;
Parameter
numcols 'number of columns generated' / 0 /
* level, lower, upper, type: 0 cont, 1 bin, 2 int, 3 semicont, 4 semiint
col_info(cc,*) 'column information'
numpat_c(cc), demand_c(cc,i) 'matrix entries';
* pattern that might improve the master model found?
if(z.l < -0.001,
numcols = numcols + 1;
numpat_c(cc) = 1;
demand_c(cc,i) = round(y.l(i));
col_info(cc,'lower') = 0;
col_info(cc,'upper') = smax(i$demand_c(cc,i), d(i)/demand_c(cc,i));
col_info(cc,'type') = 2;
);
$offEcho
```