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.

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 > cplex.opt

execute_unload 'data', i, w, d, r;
z.lo = 0; // We need to prevent reformulation for now

option rmip = cplex, 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)), 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