A loose Benders decomposition algorithm for approximating two-stage mixed-integer recourse models
- PDF / 513,008 Bytes
- 34 Pages / 439.37 x 666.142 pts Page_size
- 66 Downloads / 191 Views
Series A
A loose Benders decomposition algorithm for approximating two-stage mixed-integer recourse models · Ward Romeijnders1
Niels van der Laan1
Received: 3 December 2018 / Accepted: 28 August 2020 © The Author(s) 2020
Abstract We propose a new class of convex approximations for two-stage mixed-integer recourse models, the so-called generalized alpha-approximations. The advantage of these convex approximations over existing ones is that they are more suitable for efficient computations. Indeed, we construct a loose Benders decomposition algorithm that solves large problem instances in reasonable time. To guarantee the performance of the resulting solution, we derive corresponding error bounds that depend on the total variations of the probability density functions of the random variables in the model. The error bounds converge to zero if these total variations converge to zero. We empirically assess our solution method on several test instances, including the SIZES and SSLP instances from SIPLIB. We show that our method finds near-optimal solutions if the variability of the random parameters in the model is large. Moreover, our method outperforms existing methods in terms of computation time, especially for large problem instances. Keywords Stochastic programming · Mixed-integer recourse · Convex approximations · Error bounds Mathematics Subject Classification 90C15 · 90C11
1 Introduction Consider the two-stage mixed-integer recourse model with random right-hand side η∗ := min cx + Q(x) : x
B 1
Ax = b, x ∈ X ⊆ Rn+1 ,
(1)
Niels van der Laan [email protected] Department of Operations, University of Groningen, P.O. Box 800, 9700 AV Groningen, The Netherlands
123
N. van der Laan, W. Romeijnders
where the recourse function Q is defined as Q(x) := Eω min qy : y
W y = ω − T x, y ∈ Y ⊆ Rn+2
, x ∈ X.
(2)
This model represents a two-stage decision problem under uncertainty. In the first stage, a decision x has to be made here-and-now, subject to deterministic constraints Ax = b and random goal constraints T x = ω. Here, ω is a continuous or discrete random vector whose probability distribution is known. In the second stage, the realization of ω becomes known and any infeasibilities with respect to T x = ω have to be repaired. This is modelled by the second-stage problem v(ω, x) := min qy : y
W y = ω − T x, y ∈ Y ⊆ Rn+2 .
(3)
The objective in this two-stage recourse model is to minimize the sum of immediate costs cx and expected second-stage costs Q(x) = Eω [v(ω, x)], x ∈ X . Frequently, integrality restrictions are imposed on the first- and second-stage decip n −p p n −p sions. That is, X and Y are of the form X = Z+1 × R+1 1 and Y = Z+2 × R+2 2 . Such restrictions arise naturally when modelling real-life problems, for example to model on/off decisions or batch size restrictions. The resulting model is called a mixedinteger recourse (MIR) model. Such models have many practical applications in for example energy, telecommunication, production planning, and environmental control, see
Data Loading...
