FICO Xpress Optimization Examples Repository
 FICO Optimization Community FICO Xpress Optimization Home

Lot sizing

Description
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. The model implements a configurable cutting plane algorithm for this problem.

Further explanation of this example: 'Xpress teaching material', Section 2.7 'Branch-and-Cut'; Xpress Whitepaper 'Embedding Optimization Algorithms'; 'Mosel User Guide', Section 11.1 'Cut generation'

Source Files
By clicking on a file name, a preview is opened at the bottom of this page.

Data Files

els_graph.mos

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

file els.mos

TYPE:         Lot sizing problem
DIFFICULTY:   4
FEATURES:     MIP problem, implementation of Branch-and-Cut and
Cut-and-Branch algorithms, definition of Optimizer callbacks,
Optimizer and Mosel parameter settings, case', procedure',
function', time measurement
DESCRIPTION:  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.
The model implements a configurable cutting plane algorithm
for this problem.
FURTHER INFO: Applications of optimization with Xpress-MP teaching
material', Section 2.7 Branch-and-Cut';
Mosel User Guide', Section 11.1 Cut generation'

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

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

model "ELS"
uses "mmxprs","mmsystem", "mmsvg"

parameters
ALG = 6                             ! Algorithm choice [default settings: 0]
CUTDEPTH = 10                       ! Maximum tree depth for cut generation
EPS = 1e-6                          ! Zero tolerance
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
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

! Uncomment to get detailed MIP output
setparam("XPRS_VERBOSE", true)

! All cost data are integer, we therefore only need to search for integer
! solutions

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

writeln("**************ALG=",ALG,"***************")

starttime:=gettime
SEVERALROUNDS:=false; TOPONLY:=false

case ALG of
1: setparam("XPRS_CUTSTRATEGY", 0)  ! No cuts
2: setparam("XPRS_PRESOLVE", 0)     ! No presolve
3: tree_cut_gen                     ! User branch-and-cut + automatic cuts
4: do                               ! User branch-and-cut (several rounds),
tree_cut_gen                    ! no automatic cuts
setparam("XPRS_CUTSTRATEGY", 0)
SEVERALROUNDS:=true
end-do
5: do                               ! User cut-and-branch (several rounds)
tree_cut_gen                    ! + automatic cuts
SEVERALROUNDS:=true
TOPONLY:=true
end-do
6: do                               ! User branch-and-cut (several rounds)
tree_cut_gen                    ! + automatic cuts
SEVERALROUNDS:=true
end-do
end-case

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

! Draw the solution
forall(p in PRODUCTS) do
svgsetstyle(SVG_FILL, SVG_CURRENT)
svgsetstyle(SVG_STROKEWIDTH, 0)
end-do
forall(t in TIMES) do
cum:=0.0
forall(p in PRODUCTS | produce(p,t).sol>0) do
svgsetstyle(svggetlastobj, SVG_OPACITY, 0.5)
cum+=setup(p,t).sol
cum+=produce(p,t).sol
end-do
end-do
! svgsetgraphviewbox(0, 0, TIMES.last+1, max(t in TIMES) CAP(t) +1)
svgsetgraphlabels("Time", "Production amounts and setup")

svgsave("els.svg")
svgrefresh
svgwaitclose("Close browser window to terminate model execution.", 1)

!*************************************************************************
!  Cut generation loop:
!    get the solution values
!    identify and set up violated constraints
!*************************************************************************

function cb_node:boolean
declarations
ncut:integer                        ! Counter for cuts
cut: array(range) of linctr         ! Cuts
cutid: array(range) of integer      ! Cut type identification
type: array(range) of integer       ! Cut constraint type
objval,ds: real
end-declarations

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

depth:=getparam("XPRS_NODEDEPTH")
cnt:=getparam("XPRS_CALLBACKCOUNT_OPTNODE")

if ((TOPONLY and depth<1) or (not TOPONLY and depth<=CUTDEPTH)) and
(SEVERALROUNDS or cnt<=1) 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 getparam("XPRS_VERBOSE")=true then
writeln("Cuts added : ", ncut, " (depth ", depth, ", node ",
getparam("XPRS_NODES"), ", obj. ", getparam("XPRS_LPOBJVAL"), ")")
end-if
end-if
end-if
end-function

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

procedure tree_cut_gen
setparam("XPRS_PRESOLVE", 0)        ! Switch presolve off
setparam("XPRS_ROOTPRESOLVE", 0)    ! Switch B&B root 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

`