cutstock.gms : Cutting Stock - A Column Generation Approach

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

**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 :** cutstock.gms

$Title Cutting Stock - A Column Generation Approach (CUTSTOCK,SEQ=294) $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. 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. $offtext Set i widths /w1*w4/ 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/ * Gilmore-Gomory column generation algorithm Set p possible patterns /p1*p1000/ pp(p) dynamic subset of p Parameter 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.. z =e= sum(pp, xp(pp)); demand(i).. sum(pp, aip(i,pp)*xp(pp)) =g= d(i); model master /numpat, demand/; * Pricing problem - Knapsack model Variable y(i) new pattern; Integer variable y; y.up(i) = ceil(r/w(i)); Equation defobj knapsack knapsack constraint; defobj.. z =e= 1 - sum(i, demand.m(i)*y(i)); knapsack.. sum(i, w(i)*y(i)) =l= r; model pricing /defobj, knapsack/; * Initialization - the initial patterns have a single width pp(p) = ord(p)<=card(i); aip(i,pp(p))$(ord(i)=ord(p)) = floor(r/w(i)); *display aip; Set pi(p) set of the last pattern; pi(p) = ord(p)=card(pp)+1; option optcr=0,limrow=0,limcol=0,solprint=off; While(card(pp)<card(p), solve master using rmip minimizing z; solve pricing using mip minimizing z; break$(z.l >= -0.001); * pattern that might improve the master model found aip(i,pi) = round(y.l(i)); pp(pi) = yes; pi(p) = pi(p-1); ); display 'lower bound for number of rolls', master.objval; option solprint=on; solve master using mip minimizing z; Parameter patrep Solution pattern report demrep Solution demand supply report; patrep('# produced',p) = round(xp.l(p)); patrep(i,p)$patrep('# produced',p) = aip(i,p); patrep(i,'total') = sum(p, patrep(i,p)); patrep('# produced','total') = sum(p, patrep('# produced',p)); demrep(i,'produced') = sum(p,patrep(i,p)*patrep('# produced',p)); demrep(i,'demand') = d(i); demrep(i,'over') = demrep(i,'produced') - demrep(i,'demand'); display patrep, demrep;