bc-prod: a specialized branch-and-cut system for lot-sizing problems

MOSEL: the extended modelling and optimization subroutine library


y,z,w: (machine k, item i, period t) is, starts, ends,


remodelling safety stock


cutting planes: 
klSI inequality :  summing mass balance constraints over interval t -> l
+ simple (mixed integer rounding) inequality 


multiple machines with backlogging: 
surrogate constraint


Belvaux 1999, six other families of inequalities with capacities and start-ups


Relax and fix heuristics


Remodelling of multilevel problems


An example


========================================

MODEL setlch 
LET NI=20 
LET NK=1 
LET NT=12 
TABLES 
CAP (NI,NK,NT) 
DEM (NI,NT) 
DD(NI,NT) ! Present and future demand for item i in t 


B(NT) ! Total machine capacity in period t 
f(NI) ! the set-up cost for item i 
h(NI) ! the storage cost for item i 
!--------------------------------- 
!Read demand and cost data DEM, f, h 
LET LL=1161 ! Machine capacity constraint in each period 
LET CO=5 ! Unit cost of exceeding machine capacity 
!---------------------------------


ASSIGN 
!Calculate DD 
CAP (i=l:NI,k=l:NK,t=l:NT) = DD(i,t) 
B(t=l:NT) = LL 


VARIABLES 
x(i=l:NI,k=l:NK, t=l:NT) 
s(i=1:NI ,t=1:NT-1) 
y(i=l:NI,k=l:NK,t=l:NT) 
o(t=l:NT) ! Amount of machine overtime in period t 


CONSTRAINTS 
! Flow Balance Constraints 
FLOW(i=l:NI,t=l:NT): sum(It .ne. 1)s(i,t-1) + sum(k=l:NK) x(i,k,t) = DEM(i,t) + sum( t .ne. NT)s(i,t) 
! Individual Set-up and Capacity Constraint 
VUB(i=l:NI,k=l:NK,t=l:NT): x(i,k,t) < CAP(i,k,t)*y(i,k,t) 
! Machine Capacity Constraint 
CC(k=l:NK,t=l:NT): sum(i=l:NI) x(i,k,t) < B(t) + o(t) 
! Objective Function 
MINCOST: sum(i=l:NI,k=l:NK,t=l:NT)f(i)*y(i,k,t) + sum(t=l:NT) CO*o(t) + sum(i=l:NI,t=l:NT-1) h(i)*s(i,t) $ 
! BOUNDS 
y(i=l:NI,k=l:NK,t=l:NT) .BV. ! binary variables 


END