Worst case analysis of Relax and Fix heuristics for lot-sizing problems
We analyze the worst case behavior of Relax and Fix heuristics, which are often used to solve mixed integer linear programming problems. In these heuristics the integer variables are fixed in an iterative way, while having relaxed part of the integer variables in each iteration. In particular, we analyze Relax and Fix heuristics for lot-sizing problems. We show that even for simple instances with time-invariant parameters, the worst case ratio may be unbounded. Furthermore, we show some counterintuitive behavior of Relax and Fix heuristics from computational experiments.
|Keywords||Lot-sizing, Production, Relax and Fix heuristics, Worst case analysis|
|Persistent URL||dx.doi.org/10.1016/j.ejor.2019.06.010, hdl.handle.net/1765/117494|
|Journal||European Journal of Operational Research|
Absi, N, & van den Heuvel, W. (2019). Worst case analysis of Relax and Fix heuristics for lot-sizing problems. European Journal of Operational Research, 279(2), 449–458. doi:10.1016/j.ejor.2019.06.010