2019
Worst case analysis of Relax and Fix heuristics for lot-sizing problems
Publication
Publication
European Journal of Operational Research , Volume 279 - Issue 2 p. 449- 458
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 | |
|---|---|
| , , , | |
| doi.org/10.1016/j.ejor.2019.06.010, hdl.handle.net/1765/117494 | |
| 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 |
|
