A Benders squared ( $$B^2$$ B 2 ) framework for infinite-horizon stochastic linear programs
- PDF / 496,987 Bytes
- 37 Pages / 439.37 x 666.142 pts Page_size
- 92 Downloads / 183 Views
A Benders squared (B2 ) framework for infinite-horizon stochastic linear programs Giacomo Nannicini1 · Emiliano Traversi2 · Roberto Wolfler Calvo2 Received: 27 April 2017 / Accepted: 17 September 2020 © Springer-Verlag GmbH Germany, part of Springer Nature and Mathematical Optimization Society 2020
Abstract We propose a nested decomposition scheme for infinite-horizon stochastic linear programs. Our approach can be seen as a provably convergent extension of stochastic dual dynamic programming to the infinite-horizon setting: we explore a sequence of finite-horizon problems of increasing length until we can guarantee convergence with a given confidence level. The methodology alternates between a forward pass to explore sample paths and determine trial solutions, and a backward pass to generate a polyhedral approximation of the optimal value function by computing subgradients from the dual of the scenario subproblems. A computational study on a large set of randomly generated instances for two classes of problems shows that the proposed algorithm is able to effectively solve instances of moderate size to high precision, provided that the instance structure allows the construction of what we call constant-statepolicies with satisfactory objective function value. Keywords Benders decomposition · Stochastic programming · Cutting planes Mathematics Subject Classification Benders decomposition 49M27 · Stochastic programming 90C15 · Branch and cut 90C57
1 Introduction In the context of optimal planning under uncertainty, there are many situations in which the decision maker is interested in solving a steady-state planning problem.
B
Emiliano Traversi [email protected] Giacomo Nannicini [email protected] Roberto Wolfler Calvo [email protected]
1
IBM T.J. Watson, Yorktown Heights, NY, USA
2
Laboratoire d’Informatique de Paris Nord, Université de Paris 13; and Sorbonne Paris Cité, CNRS (UMR 7538), 93430 Villetaneuse, France
123
G. Nannicini et al.
Such a scenario arises whenever there are repeated decisions that have to be taken over an infinite (i.e., unbounded) time horizon, for example if production of a given set of items has to be planned every day under uncertain demands, and this process is repeated indefinitely. In this type of model there is a discrete time index t that ranges from zero (present time) to infinity, and a decision problem must be solved for every integer value of t (called a stage). The decision problem at each stage depends on the state of the system, which is influenced by both the realization of uncertain events, and previous decisions (often called actions). For example, the state of the system could be the inventory of the items at hand, and the actions could be the set of items ordered from a supplier at that point in time. Each action incurs a cost, and the objective is to find a rule that maps states into actions (called a policy) in order to minimize the total expected cost over the time horizon t = 0, . . . , ∞. A geometric discount factor for the cost is typically introduced, to
Data Loading...
