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

Branch-and-Price for the Generalized Assignment Problem

Description
The model implements a branch-and-price algorithm that solves a disaggregated formulation of the Generalized Assignment Problem (GAP) where columns represent feasible assignments of batches to machines. Column generation is applied at every node of the branch-and-bound tree. The branching algorithm is completely implemented in Mosel, and the optimizer is used only to solve the LP relaxation at each node.

The model implementation shows the following features of Mosel:
  • user type definitions for data structures (records)
  • concurrent solving of a set of subproblems coordinated via events and exchanging data (including data with user type) via shared memory
Data instances for this problem are generated by executing the model genGapDataD.mos. The branch-and-price algorithm is started by running the main model GAPbp3.mos. This model triggers the solving of the submodels (file GAPsubDP.mos). The present implementation of branch-and-price can be extended by the definition of a heuristic that will be called at every node of the branching tree (subroutine 'heuristic') and it can also be configured to use other branching variable choice strategies.

gabbp.zip[download all files]

Source Files
By clicking on a file name, a preview is opened at the bottom of this page.
GAPbp3.mos[download]
GAPsubDP.mos[download]
genGapDataD.mos[download]

Data Files
Dtestx5_30_1.dat[download]




genGapDataD.mos

(!************************************************************
   Mosel Example Problems
   ====================== 

   file genGapDataD.mos
   ````````````````````   
   Generate random instances of the Generalized Assignment
   Problem (GAP) of type D
     
   (c) 2008 Fair Isaac Corporation
       author: Hernan Wurgaft, 2007
**************************************************************!)
model GenGAPData
  uses "mmsystem"
 
  parameters
    NM = 5     ! Number of machines
    NP = 30    ! Number of production batches
    NI = 6     ! Number of problem instances
  end-parameters

  declarations
    DATAFILE: string
    RM = 1..NM
    RP = 1..NP
    DUR: array(RM,RP) of integer
    PROFIT: array(RM,RP) of integer
    CAP: array(RM) of integer
  end-declarations

  setrandseed(666)

  forall(inst in 1..NI) do
  ! Generate data
    DATAFILE:=
      string(text("Dtestx")+text(NM)+"_"+text(NP)+"_"+text(inst)+".dat")
    forall(i in RM) do
      tot:=0
      forall(j in RP) do
        DUR(i,j):= integer(round((100*random)+0.5)) ! Random integer in [1,100]
        tot+=DUR(i,j)
        e1:= integer(round((20*random)))-10        ! Random integer in [-10,10]
        PROFIT(i,j):= 111-DUR(i,j)+e1
      end-do
      CAP(i):=integer(round(.8*tot/NM))
    end-do
    maxprofit:=0
    forall(i in RM,j in RP) do
      if PROFIT(i,j)>maxprofit then
        maxprofit:=PROFIT(i,j)
      end-if
    end-do        
  
    maxprofit+=1
    forall(i in RM,j in RP) PROFIT(i,j):=maxprofit-PROFIT(i,j)
 
  ! Write data to file
    initializations to DATAFILE
      NM NP
      DUR CAP PROFIT
    end-initializations

  end-do

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