A rolling-horizon approach for multi-period optimization

Mathematical optimization problems including a time dimension abound. For example, logistics, process optimization and production planning tasks must often be optimized for a range of time periods. Usually, these problems incorporating time structure are very large and cannot be solved to global optimality by modern solvers within a reasonable period of time. Therefore, the so-called rolling-horizon approach is often adopted. This approach aims to solve the problem periodically, including additional information from proximately following periods. In this paper, we first investigate several drawbacks of this approach and develop an algorithm that compensates for these drawbacks both theoretically and practically. As a result, the rolling-horizon decomposition methodology is adjusted to enable large scale optimization problems to be solved efficiently. In addition, we introduce conditions that guarantee the quality of the solutions. We further demonstrate the applicability of the method to a variety of challenging optimization problems. We substantiate the findings with computational studies on the lot-sizing problem in production planning, as well as for large-scale real-world instances of the tail-assignment problem in aircraft management. It proves possible to solve large-scale realistic tail-assignment instances efficiently, leading to solutions that are at most a few percent away from a globally optimal solution.