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

Cut generation for an economic lot-sizing (ELS) problem

Description
This model implements various forms of cut-and-branch and branch-and-cut algorithms. In its simplest form (looping over LP solving) it illustrates the following features:
  • adding new constraints and resolving the LP-problem (cut-and-branch)
  • basis in- and output
  • if statement
  • repeat-until statement
  • procedure
The model els.mos also implements a configurable cutting plane algorithm:
  • defining the cut manager node callback function,
  • defining and adding cuts during the MIP search (branch-and-cut), and
  • using run-time parameters to configure the solution algorithm.
The version elsglobal.mos shows how to implement global cuts. And the model version elscb.mos defines additional callbacks for extended logging and user stopping criteria based on the MIP gap.

Another implementation (main model: runels.mos, submodel: elsp.mos) parallelizes the execution of several model instances, showing the following features:
  • parallel execution of submodels
  • communication between different models (for bound updates on the objective function)
  • sending and receiving events
  • stopping submodels
The fourth implementation (main model: runelsd.mos, submodel: elsd.mos) is an extension of the parallel version in which the solve of each submodels are distributed to various computing nodes.

Further explanation of this example: elscb.mos, elsglobal.mos, runels.mos: Xpress Whitepaper 'Multiple models and parallel solving with Mosel', Section 'Solving several model instances in parallel'.

els.zip[download all files]

Source Files
By clicking on a file name, a preview is opened at the bottom of this page.
els.mos[download]
runels.mos[download]
runels_graph.mos[download]
runelst.mos[download]
elsp.mos[download]
elspg.mos[download]
elsc.mos[download]
elscb.mos[download]
elscb_graph.mos[download]
elsglobal.mos[download]
runelsd.mos[download]
elsd.mos[download]

Data Files
els.dat[download]
els4.dat[download]
els5.dat[download]




elsglobal.mos

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

   file elsglobal.mos
   ``````````````````
   Economic lot sizing, ELS, problem
   (Cut generation algorithm adding (l,S)-inequalities 
    in several rounds at tree nodes)
   
   Model version with (optional) global tree cuts

   Economic lot sizing (ELS) considers production planning 
   over a given planning horizon. In every period, there is 
   a given demand for every product that must be satisfied by 
   the production in this period and by inventory carried over 
   from previous periods.
   A set-up cost is associated with production in a period, 
   and the total production capacity per period is limited. 
   The unit production cost per product and time period is 
   given. There is no inventory or stock-holding cost.

   *** This model cannot be run with a Community Licence 
       for the provided data instance ***

   (c) 2008 Fair Isaac Corporation
       author: N. Verma, 2006, rev. July 2023
  *******************************************************!)

model "ELS (global cuts)"
 uses "mmxprs","mmsystem"

 parameters
  CUTDEPTH = 10                  ! Maximum tree depth for cut generation
  EPS = 1e-6                     ! Zero tolerance
  GLOBAL = true                  ! Apply global cuts
 end-parameters 

 forward function cb_node:boolean
 forward procedure tree_cut_gen

 declarations
  TIMES = 1..15                              ! Range of time
  PRODUCTS = 1..4                            ! Set of products

  DEMAND: array(PRODUCTS,TIMES) of integer   ! Demand per period
  SETUPCOST: array(TIMES) of integer         ! Setup cost per period
  PRODCOST: array(PRODUCTS,TIMES) of integer ! Production cost per period
  CAP: array(TIMES) of integer               ! Production capacity per period
  D: array(PRODUCTS,TIMES,TIMES) of integer  ! Total demand in periods t1 - t2

  produce: array(PRODUCTS,TIMES) of mpvar    ! Production in period t
  setup: array(PRODUCTS,TIMES) of mpvar      ! Setup in period t

  solprod: array(PRODUCTS,TIMES) of real     ! Sol. values for var.s produce
  solsetup: array(PRODUCTS,TIMES) of real    ! Sol. values for var.s setup
  starttime: real
  num_cuts_added:integer
 end-declarations

 initializations from "els.dat"
  DEMAND SETUPCOST PRODCOST CAP
 end-initializations

 forall(p in PRODUCTS,s,t in TIMES) D(p,s,t):= sum(k in s..t) DEMAND(p,k)

! Objective: minimize total cost
 MinCost:= sum(t in TIMES) (SETUPCOST(t) * sum(p in PRODUCTS) setup(p,t) + 
                            sum(p in PRODUCTS) PRODCOST(p,t) * produce(p,t) )

! Satisfy the total demand
 forall(p in PRODUCTS,t in TIMES) 
   Dem(p,t):= sum(s in 1..t) produce(p,s) >= sum (s in 1..t) DEMAND(p,s)

! If there is production during t then there is a setup in t
 forall(p in PRODUCTS, t in TIMES) 
  ProdSetup(p,t):= produce(p,t) <= D(p,t,getlast(TIMES)) * setup(p,t)

! Capacity limits
 forall(t in TIMES) Capacity(t):= sum(p in PRODUCTS) produce(p,t) <= CAP(t)

! Variables setup are 0/1
 forall(p in PRODUCTS, t in TIMES) setup(p,t) is_binary 

! Without this setting behaviour of B&B is somewhat non-deterministic
 setparam("XPRS_THREADS", 1)

! Uncomment to get detailed MIP output
 setparam("XPRS_VERBOSE", true)
 
! All cost data are integer, we therefore only need to search for integer
! solutions
 setparam("XPRS_MIPADDCUTOFF", -0.999)

! Set Mosel comparison tolerance to a sufficiently small value
 setparam("ZEROTOL", EPS/100)
 
 starttime:=gettime

 tree_cut_gen                         ! User branch-and-cut (several rounds)
 setparam("XPRS_CUTSTRATEGY", 0)      ! No automatic cuts

 minimize(MinCost)                    ! Solve the problem
                                       
 writeln("Time: ", gettime-starttime, "sec,  Nodes: ", getparam("XPRS_NODES"),
         ",  Solution: ", getobjval) 
 write("Period  setup    ")
 forall(p in PRODUCTS) write(strfmt(p,-7))
 forall(t in TIMES) do
  write("\n ", strfmt(t,2), strfmt(getsol(sum(p in PRODUCTS) setup(p,t)),8), "     ")
  forall(p in PRODUCTS) write(getsol(produce(p,t)), " (",DEMAND(p,t),")  ")
 end-do
 writeln

!*************************************************************************
!  Cut generation loop:
!    get the solution values
!    identify and set up violated constraints
!    load the modified problem and load the saved basis
!*************************************************************************

 function cb_node:boolean
  declarations
    ncut:integer
    CutRange: range                        ! Counter for cuts
    cut: array(CutRange) of linctr         ! Cuts
    cutid: array(CutRange) of integer      ! Cut type identification
    type: array(CutRange) of integer       ! Cut constraint type
    ndx_cuts: set of integer               ! Index of cuts
    active_cuts,violated_cuts: set of integer
    objval,ds: real
    cut_indices: set of integer
    viol: dynamic array(range) of real 
  end-declarations

  returned:=false                      ! OPTNODE: This node is not infeasible

  node:=getparam("XPRS_NODES")
  depth:=getparam("XPRS_NODEDEPTH")

  if depth<=CUTDEPTH then
    ncut:=0 
 
  ! Get the solution values
    forall(t in TIMES, p in PRODUCTS) do
      solprod(p,t):=getsol(produce(p,t))
      solsetup(p,t):=getsol(setup(p,t))
    end-do
   
  ! Search for violated constraints
    forall(p in PRODUCTS,l in TIMES) do
     ds:=0 
     forall(t in 1..l)
       if (solprod(p,t) < D(p,t,l)*solsetup(p,t) + EPS) then ds += solprod(p,t)
       else  ds += D(p,t,l)*solsetup(p,t)
       end-if
   
    ! Generate the violated inequality
     if ds < D(p,1,l) - EPS then
       cut(ncut):= sum(t in 1..l) 
        if(solprod(p,t)<(D(p,t,l)*solsetup(p,t))+EPS, produce(p,t), 
           D(p,t,l)*setup(p,t)) - D(p,1,l)
       cutid(ncut):= 1
       type(ncut):= CT_GEQ
       ncut+=1
     end-if   
   end-do
        
  ! Add cuts to the problem
    if ncut>0 then    
      if GLOBAL then
        storecuts(0,cutid,type,cut,ndx_cuts)
        writeln("Stored cuts at node ", node, " -> ", getsize(ndx_cuts))
        
        getcplist(1,1,0, violated_cuts,viol)
        writeln("Current violated cuts in the cutpool after solving node ", 
                node, " -> ", getsize(violated_cuts))
        
        loadcuts(1,1,violated_cuts)
      else    
        addcuts(cutid, type, cut);
        num_cuts_added+=ncut
        if(getparam("XPRS_VERBOSE")=true) then
          writeln("Cuts added : ", ncut, " (depth ", depth, ", node ", 
                  node, ", obj. ", getparam("XPRS_LPOBJVAL"), ") count=",
	          num_cuts_added)
        end-if   
      end-if
       
    else
     
      getcplist(1,1,0, violated_cuts,viol)
      if getsize(violated_cuts)>0 then
        writeln("All violated cuts in the cutpool after solving node ", node,
	        " -> ", getsize(violated_cuts))
        writeln("######################### VIOLATED #########################")
      end-if
      
      delcuts(true,0,-1,-MAX_REAL) ! Delete all cuts from problem at current node that are not required
   !   writeln("Cuts with non-basic slack are deleted at node ", node)
    end-if   
  end-if
 end-function

! ****Optimizer settings for using the cut manager****

 procedure tree_cut_gen
  setparam("XPRS_PRESOLVEOPS",2270)       ! Non-destructive presolve only
 ! setparam("XPRS_PRESOLVE", 0)           ! Switch presolve off
  setparam("XPRS_EXTRAROWS", 5000)        ! Reserve extra rows in matrix
 
  setcallback(XPRS_CB_OPTNODE, ->cb_node)  ! Set the optnode callback function
 end-procedure

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