FICO
FICO Xpress Optimization Examples Repository
FICO Optimization Community FICO Xpress Optimization Home
Back to examples browserPrevious exampleNext example

Column generation for a cutting stock problem

Description
  • creating new variables and adding them to constraints and objective
  • basis in- and output
  • sorting and single knapsack algorithms
  • repeat-until statement
  • use of functions
  • hiding / unhiding constraints
  • resetting (deleting) constraints
The first version of this model (cutstk.mos) solves the knapsack subproblem heuristically, the second version (paper.mos) solves it as a second optimization problem, hiding (blending out) the constraints of the main problem. The third version defines the subproblem as a separate problem with the same model, repeatedly creating new problems (papersn.mos) or re-using/redefining the same problem (papers.mos), that is:
  • defining multiple problems within a model
  • switching between problems
A fourth version (main model: paperp[r].mos, submodel: knapsack[r].mos) shows how to implement the algorithm with two separate models, illustrating the following features of Mosel:
  • working with multiple models
  • executing a sequence of models
  • passing data via shared memory


Further explanation of this example: paper.mos, papers.mos, papersn.mos: 'Mosel User Guide', Section 11.2 Column generation, and the Xpress Whitepaper 'Embedding Optimization Algorithms', Section 'Column generation for cutting-stock' (also discusses a generalization to bin-packing problems); for the multiple model versions paperp.mos, paperms.mos see the Xpress Whitepaper 'Multiple models and parallel solving with Mosel', Section 'Column generation: solving different models in sequence'.

colgen.zip[download all files]

Source Files
By clicking on a file name, a preview is opened at the bottom of this page.
cutstk.mos[download]
papersn.mos[download]
paper.mos[download]
papers.mos[download]
paperp.mos[download]
knapsack.mos[download]
paperpr.mos[download]
knapsackr.mos[download]




knapsackr.mos

(!*******************************************************
   Mosel User Guide Examples
   =========================

   file knapsackr.mos
   ``````````````````
   Knapsack (sub)model of the for a paper cutting example,
   reading data from shared memory.
   Communication of data from/to parent model
   using 'shmem' IO driver with 'raw'.

   *** Not intended to be run standalone - run from paperpr.mos ***

   Solve the integer knapsack problem                              
     z = max{Cx : Ax<=B, x<=D, x in Z^N}  

   (c) 2008 Fair Isaac Corporation
       author: S. Heipcke, 2004, rev. July 2010
*******************************************************!)

model "Knapsack"
 uses "mmxprs"

 parameters
  NWIDTHS=5                            ! Number of different widths
 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 "raw:noindex"
  A as "shmem:A" B as "shmem:B" C as "shmem:C"  D as "shmem: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)

! Integrality condition and bounds
 forall(j in WIDTHS) x(j) is_integer
 forall(j in WIDTHS) x(j) <= D(j)    ! These bounds can be omitted

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

 initializations to "raw:"
  xbest as "shmem:xbest" z as "shmem:zbest"
 end-initializations

end-model
Back to examples browserPrevious exampleNext example
© Copyright 2023 Fair Isaac Corporation.