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.

Large Model of Type : MINLP

Category : GAMS Model library

Main file : bchtlbas.gms   includes :  bchtlheu.inc

$title Trim Loss Minimization with Heuristic using BCH Facility (BCHTLBAS,SEQ=286)

$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.


Harjunkoski, I, Application of MINLP Methods on a Scheduling Problem
in the Paper Converting Industry. PhD thesis, Abo Akademi University,
1997.

Harjunkoski, I, Westerlund, T, Porn, R, and Skrifvars, H,
Different Transformations for Solving Non-Convex Trim Loss Problems by
MINLP. European Journal of Operational Research 105, 3 (1998), 594-603.

Keywords: mixed integer nonlinear programming, cutting stock, trim loss
          minimization, branch and cut and heuristic facility, paper industry
$offText

Set
   i 'product roll'   / 1*12 /
   j 'pattern number' / 1*12 /;

Scalar
   Bmax  'width of entire roll'     / 2100 /
   delta 'maximum loss in pattern'  /  100 /
   Nkmax 'maximum number of knives' /    5 /;

Parameter
   n(i) 'number of orders of each product roll'
        / 1  10, 2  28, 3  48,  4  28,  5  40,  6  30
          7  21, 8  22, 9   8, 10   8, 11   9, 12   8 /
   b(i) 'width of each roll'
        / 1  350.0, 2  450.0, 3  550.0,  4  650.0,  5   700.0,  6   740.0
          7  800.0, 8  840.0, 9  910.0, 10  960.0, 11  1010.0, 12  1060.0 /;

Parameter mupp(j) 'upper bound on repeats of pattern j';
mupp(j) = smax(i,n(i));

* Unload common data for heuristic
execute_unload "trimloss.gdx", i, j, Bmax, delta, Nkmax, n, b, mupp;

Variable
   r(i,j) 'number of products of type i in pattern j'
   y(j)   'existence of pattern j'
   m(j)   'repeats of pattern j'
   objval 'objective function variable';

Free    Variable objval;
Binary  Variable y;
Integer Variable r, m;

Equation
   f          'objective function'
   numroll(i) 'order constraints ensuring sufficient production'
   widthL(j)  'width lower bound constraint'
   widthU(j)  'width upper bound constraint'
   rL(j)      'logical constraint on r'
   sumr(j)    'logical constraint on r'
   mL(j)      'logical constraint on m'
   mU(j)      'logical constraint on m'
   sumbil     'lower bound on total number of patterns made'
   yy(j)      'ordering of y variables to reduce degeneracy'
   lmm(j)     'ordering of m variables to reduce degeneracy';

f..          objval =e= sum(j, m(j) + ord(j)/10*y(j));

numroll(i).. sum(j, m(j)*r(i,j)) =g= n(i);

widthL(j)..  sum(i,b(i)*r(i,j))  =g= (Bmax - delta)*y(j);

widthU(j)..  sum(i,b(i)*r(i,j))  =l= Bmax*y(j);

rL(j)..      y(j) =l= sum(i,r(i,j));

sumr(j)..    sum(i,r(i,j)) =l= Nkmax*y(j);

mL(j)..      y(j) =l= m(j);

mU(j)..      m(j) - mupp(j)*y(j) =l= 0;

sumbil..     sum(j, m(j)) =g= max(ceil(sum(i,n(i))/Nkmax), ceil(sum(i,b(i)*n(i))/Bmax)) + 1;

yy(j+1)..    y(j+1) =l= y(j);

lmm(j+1)..   m(j+1) =l= m(j);

r.up(i,j) = Nkmax;
m.up(j)   = mupp(j);

Model trimloss / all /;

$echo userHeurCall bchtlheu.inc mip cplex resLim 5> sbb.opt

option minlp = sbb;
trimloss.optFile = 1;

solve trimloss using minlp minimizing objval;