apis/examples_python/cutstock__class_8py_source.html

from gams import *


class Cutstock():


    def __init__(self, ws):

        self._ws = ws

        self.opt = ws.add_options()

        self._cutstock_data = ws.add_database(in_model_name = "gdxincname")


        self.opt.solvelink = SolveLink.LoadLibrary

        self.opt.defines["dbOut1"] = "dbOut1"


        self.widths = self._cutstock_data.add_set("i", 1, "widths")

        self.raw_width = self._cutstock_data.add_parameter("r", 0, "raw width")

        self.demand = self._cutstock_data.add_parameter_dc("d", [self.widths], "demand")

        self.width = self._cutstock_data.add_parameter_dc("w", [self.widths], "width")


        self._job = ws.add_job_from_string(self.get_model_source())


    def run(self, output = None):

        self._job.run(self.opt, None, output, databases=self._cutstock_data)

        self._dbout = self._ws.add_database_from_gdx(self.opt.defines["dbOut1"] + ".gdx")

        self.pat_rep = self._dbout.get_parameter("patrep")


    def get_model_source(self):

        return '''

$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

Parameter

     r    raw width

     w(i) width

     d(i) demand ;


$if not set gdxincname $abort 'no include file name for data file provided'

$gdxin %gdxincname%

$load r i w d

$gdxin


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


Scalar done  loop indicator /0/

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(not done and card(pp)<card(p),

   solve master using rmip minimizing z;

   solve pricing using mip minimizing z;


* pattern that might improve the master model found?

   if(z.l < -0.001,

      aip(i,pi) = round(y.l(i));

      pp(pi) = yes; pi(p) = pi(p-1);

   else

      done = 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;


$if not set dbOut1 $abort 'no file name for out-database 1 file provided'

execute_unload '%dbOut1%', patrep;

'''