$title Trim Loss Minimization (TRIMLOSS,SEQ=204)

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

Floudas, C A, Pardalos, P M, Adjiman, C S, Esposito, W R, Gumus, Z H,
Harding, S T, Klepeis, J L, Meyer, C A, and Schweiger, C A, Handbook
of Test Problems in Local and Global Optimization. Kluwer Academic
Publishers, 1999.

The entire collection of models can found at
http://titan.princeton.edu/TestProblems/

Keywords: mixed integer nonlinear programming, cutting stock, trim loss minimization
          paper industry, engineering
$offText

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

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

Parameter
   n(i)    'number of orders of each product roll'
           / 1  8, 2 16, 3 12, 4  7, 5 14, 6 16 /
   b(i)    'width of each roll'
           / 1  330, 2  360, 3  380, 4  430, 5  490, 6  530 /
   mupp(j) 'upper bound on repeats of pattern j'
           / 1 15, 2 12, 3  8, 4  7, 5  4, 6  2 /;

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 /;

option optCr = 0.0;

solve trimloss using minlp minimizing objval;

execError = 0;

* Did we find the global solution?
Parameter rep 'solution report';
rep(i,j,'local')   = r.L(i,j);
rep('y',j,'local') = y.L(j);
rep('m',j,'local') = m.L(j);

Table gs(j,*) 'global solution'
       1  2  3  4  5  6  y  m
   1      2     1  1  1  1  8
   2   1     2     1  1  1  8;

rep(i,j,'global')   = gs(j,i);
rep('y',j,'global') = gs(j,'y');
rep('m',j,'global') = gs(j,'m');
rep(i,j,'diff')     = rep(i,j,'global')   - rep(i,j,'local');
rep('y',j,'diff')   = rep('y',j,'global') - rep('y',j,'local');
rep('m',j,'diff')   = rep('m',j,'global') - rep('m',j,'local');

option  rep:8:2:1;
display rep;