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 (master 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 (master 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'.


Source Files

Data Files





elscb.mos

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

   file elscb.mos
   ``````````````
   Economic lot sizing, ELS, problem

   Basic version with large data set and logging callbacks.

   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.
       
   - Using the GAPNOTIFY callback -    
       
   (c) 2012 Fair Isaac Corporation
       author: S. Heipcke, Sep. 2012, rev. Sep. 2014
  *******************************************************!)

model "ELS with logging callbacks"
 uses "mmxprs","mmsystem"

 parameters
  DATAFILE = "els4.dat"
  T = 60
  P = 4
 end-parameters 

 forward public function cb_node: boolean 
 forward public procedure cb_intsol
 forward public procedure cb_gapnotify(rt,at,aot,abt:real)

 declarations
  TIMES = 1..T                               ! Range of time
  PRODUCTS = 1..P                            ! 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,logtime, objval, mipgap: real
 end-declarations

 initializations from DATAFILE
  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 

! 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)


! Setting callbacks for logging
 setcallback(XPRS_CB_INTSOL, "cb_intsol")
 setcallback(XPRS_CB_PRENODE, "cb_node") 
 mipgap:= 0.10
 setparam("XPRS_MIPRELGAPNOTIFY", mipgap)
 setcallback(XPRS_CB_GAPNOTIFY, "cb_gapnotify")  


 starttime:=gettime
 logtime:=starttime

 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

!*****************************************************************

! Function called at every B&B node, return value 'true' marks node as infeasible
 public function cb_node: boolean 
   timeNow:=gettime
   if timeNow-logtime>=5 then
     bbound:= getparam("XPRS_BESTBOUND")
     actnodes:= getparam("XPRS_ACTIVENODES")
     writeln(timeNow-starttime, "sec. Best bound:", bbound, "  best sol.:",
             if(getparam("XPRS_MIPSTATUS")=XPRS_MIP_SOLUTION, 
                text(objval), text(" - ")), 
             "  active nodes: ", actnodes)
     logtime:=timeNow
   end-if 
   returned:= false 
 end-function

! Store and display new solution
 public procedure cb_intsol
   lastobjval:=objval
   objval:= getparam("XPRS_LPOBJVAL")   ! Retrieve current objective value
    writeln(gettime-starttime, "sec. New solution: ", objval)
   
   ! If model runs for more than 60sec and new solution is just slightly
   ! better, then interrupt search
   if gettime-starttime>60 and abs(lastobjval-objval)<=5 then 
     writeln("Stopping search")
     stopoptimize(XPRS_STOP_USER)
   end-if
 end-procedure

! Notify about gap changes
! With the setting XPRS_MIPRELGAPNOTIFY=0.10 this routine will be called first
! when gap reaches 10%. We then reset the target, so that it gets called
! once more at a 2% smaller gap
 public procedure cb_gapnotify(rt,at,aot,abt:real)
   writeln(gettime-starttime, "sec. Reached ",
           100*mipgap, "% gap.")
   mipobj:= getparam("XPRS_MIPOBJVAL")
   bbound:= getparam("XPRS_BESTBOUND")
   relgap:= abs( (mipobj-bbound)/mipobj )
   if relgap<=0.1 then
     ! Call "setgndata" to return new target value to the Optimizer
     mipgap-=0.02
     setgndata(XPRS_GN_RELTARGET, mipgap)
   end-if
   if relgap<=0.02 then
     setgndata(XPRS_GN_RELTARGET, -1)  ! Don't call gapnotify callback any more
   end-if
 end-procedure
 
end-model

Back to examples browserPrevious exampleNext example