Implementation

The implementation is divided into two parts: the master model (file paperp.mos) with the definition of the cutting stock problem and the column generation algorithm, and the knapsack model (file knapsack.mos) that is run from the master.

Master model

The main part of the cutting stock model looks as follows:

model "Papermill (multi-model)"
 uses "mmxprs", "mmjobs"

 forward procedure column_gen
 forward 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
  NWIDTHS = 5                          ! Number of different widths
  WIDTHS = 1..NWIDTHS                  ! Range of widths
  RP: range                            ! Range of cutting patterns
  MAXWIDTH = 94                        ! Maximum roll width
  EPS = 1e-6                           ! Zero tolerance

  WIDTH: array(WIDTHS) of real         ! Possible widths
  DEMAND: array(WIDTHS) of integer     ! Demand per width
  PATTERNS: array(WIDTHS, WIDTHS) of integer  ! (Basic) cutting patterns

  use: dynamic array(RP) of mpvar      ! Rolls per pattern
  soluse: dynamic array(RP) of real    ! Solution values for variables `use'
  Dem: array(WIDTHS) of linctr         ! Demand constraints
  MinRolls: linctr                     ! Objective function

  Knapsack: Model                      ! Reference to the knapsack model
 end-declarations

 WIDTH::  [ 17, 21, 22.5,  24, 29.5]
 DEMAND:: [150, 96,   48, 108,  227]

 forall(j in WIDTHS)                   ! Make basic patterns
   PATTERNS(j,j) := minlist(floor(MAXWIDTH/WIDTH(j)),DEMAND(j))

 forall(j in WIDTHS) do
  create(use(j))                       ! Create NWIDTHS variables `use'
  use(j) is_integer                    ! Variables are integer and bounded
  use(j) <= integer(ceil(DEMAND(j)/PATTERNS(j,j)))
 end-do

 MinRolls:= sum(j in WIDTHS) use(j)    ! Objective: minimize no. of rolls

                                       ! Satisfy all demands
 forall(i in WIDTHS)
  Dem(i):= sum(j in WIDTHS) PATTERNS(i,j) * use(j) >= DEMAND(i)

 res:= compile("knapsack.mos")         ! Compile the knapsack model
 load(Knapsack, "knapsack.bim")        ! Load the knapsack model
 column_gen                            ! Column generation at top node

 minimize(MinRolls)                    ! Compute the best integer solution
                                       ! for the current problem (including
                                       ! the new columns)
 writeln_("Best integer solution: ", getobjval, " rolls")
 write_("  Rolls per pattern: ")
 forall(i in RP) write(getsol(use(i)),", ")
 writeln
end-model

Before starting the column generation heuristic (the definition of procedure column_gen is left out here since it remains unchanged from the User Guide example) the knapsack model is compiled and loaded so that at every column generation loop we merely need to run it with new data. The knapsack model is run from the function knapsack that takes as its parameters the data for the knapsack problem and its solution values. The function saves all data to shared memory, then runs the knapsack model and retrieves the solution from shared memory. Its return value is the objective value (zbest) of the knapsack 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

  INDATA  := "bin:shmem:indata"
  RESDATA := "bin:shmem:resdata"

  initializations to INDATA
   A  B  C  D
  end-initializations

  run(Knapsack, "NWIDTHS=" + NWIDTHS + ",INDATA=" + INDATA +
      ",RESDATA=" + RESDATA)           ! Start knapsack (sub)model
  wait                                 ! Wait until subproblem finishes
  dropnextevent                        ! Ignore termination message

  initializations from RESDATA
   xbest  returned as "zbest"
  end-initializations
 end-function

To enforce a sequential execution of the two models (we need to retrieve the results from the knapsack problem before we may continue with the master) we must add a call to the procedure wait immediately after the run statement. Otherwise the execution of the master model continues concurrently to the child model. On termination, the child model sends a `termination' event (an event of class EVENT_END). Since our algorithm does not require this event we simply remove it from the model's event queue with a call to dropnextevent.

Knapsack model

The implementation of the knapsack model is straightforward. All problem data is obtained from shared memory and after solving the problem its solution is saved into shared memory.

model "Knapsack"
 uses "mmxprs"

 parameters
  NWIDTHS=5                            ! Number of different widths
  INDATA = "knapsack.dat"              ! Input data file
  RESDATA = "knresult.dat"             ! Result data file
 end-parameters

 declarations
  WIDTHS = 1..NWIDTHS                  ! Range of widths
  A,C: array(WIDTHS) of real           ! Constraint + obj. coefficients
  B: real                              ! RHS value of knapsack constraint
  D: array(WIDTHS) of integer          ! Variables bounds (demand quantities)
  KnapCtr, KnapObj: linctr             ! Knapsack constraint+objective
  x: array(WIDTHS) of mpvar            ! Knapsack variables
  xbest: array(WIDTHS) of integer      ! Solution values
 end-declarations

 initializations from INDATA
  A  B  C  D
 end-initializations

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

 forall(j in WIDTHS) x(j) is_integer
 forall(j in WIDTHS) x(j) <= D(j)

! Solve the problem and retrieve the solution
 maximize(KnapObj)
 z:=getobjval
 forall(j in WIDTHS) xbest(j):=round(getsol(x(j)))

 initializations to RESDATA
  xbest  z as "zbest"
 end-initializations

end-model