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.

Additional Metadata
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
Citation
Absi, N. (Nabil), & van den Heuvel, W. (2019). Worst case analysis of Relax and Fix heuristics for lot-sizing problems. European Journal of Operational Research. doi:10.1016/j.ejor.2019.06.010