Alternative implementation with multiple problems

The solving of the master model and the knapsack subproblem is sequential. An alternative implementation of the column generation algorithm therefore uses several problems (in the place of several models). Since the different problems are contained in a single model file, all Mosel code referring to data transfer between models is removed in this version; the mathematical part of the model remains the same. The complete Mosel program is somewhat shorter

Master problem

The main model body now simply defines the cutting stock problem, starts the column generation loop followed by the MIP optimization, and prints out the results, just like the model version documented in the Mosel User Guide.

The definition of the column generation algorithm in subroutine column_gen remains entirely unchanged and we therefore omit its listing here .

Knapsack problem

The complete formulation of the knapsack problem is now contained in the function knapsack, where the submodel is re-defined and re-solved at every call to the function. The line with mpproblem do indicates that we switch to a new problem, created locally at this point. After the do block we return automatically to the main (cutting stock master) problem.

 function knapsack(C:array(range) of real,
                   A:array(range) of real,
                   B:real, D:array(range) of integer,
                   xbest:array(range) of integer):real

  declarations
   x: array(WIDTHS) of mpvar            ! Knapsack variables
  end-declarations

  with mpproblem do                     ! Create a local subproblem

 ! Define the knapsack problem
   forall(j in WIDTHS) x(j) is_integer
   forall(j in WIDTHS) x(j) <= D(j)
   sum(j in WIDTHS) A(j)*x(j) <= B

   maximize(sum(j in WIDTHS) C(j)*x(j))
   returned:=getobjval
   forall(j in WIDTHS) xbest(j):=round(getsol(x(j)))

  end-do

 end-function

Slightly more efficient is the following version where the declaration of the knapsack problem has been moved into the main model body, that is, the problem is declared globally instead of being re-created and deleted at every call to the subroutine knapsack.

 declarations
  Knapsack: mpproblem                  ! Knapsack subproblem
  KnapCtr, KnapObj: linctr             ! Knapsack constraint+objective
  x: array(WIDTHS) of mpvar            ! Knapsack variables
 end-declarations


 function knapsack(C:array(range) of real,
                   A:array(range) of real,
                   B:real, D:array(range) of integer,
                   xbest:array(range) of integer,
                   pass: integer):real

  with Knapsack do

 ! Redefine the knapsack problem
   KnapCtr := sum(j in WIDTHS) A(j)*x(j) <= B
   KnapObj := sum(j in WIDTHS) C(j)*x(j)

 ! Integrality condition
   if pass=1 then
    forall(j in WIDTHS) x(j) is_integer
    forall(j in WIDTHS) x(j) <= D(j)
   end-if

   maximize(KnapObj)
   returned:=getobjval
   forall(j in WIDTHS) xbest(j):=round(getsol(x(j)))

  end-do

 end-function