Benders decomposition with adaptive oracles for large scale optimization
- PDF / 872,243 Bytes
- 21 Pages / 439.37 x 666.142 pts Page_size
- 28 Downloads / 205 Views
Benders decomposition with adaptive oracles for large scale optimization Nicolò Mazzi1 · Andreas Grothey1 · Ken McKinnon1 · Nagisa Sugishita1 Received: 5 April 2019 / Accepted: 21 October 2020 © The Author(s) 2020
Abstract This paper proposes an algorithm to efficiently solve large optimization problems which exhibit a column bounded block-diagonal structure, where subproblems differ in right-hand side and cost coefficients. Similar problems are often tackled using cutting-plane algorithms, which allow for an iterative and decomposed solution of the problem. When solving subproblems is computationally expensive and the set of subproblems is large, cutting-plane algorithms may slow down severely. In this context we propose two novel adaptive oracles that yield inexact information, potentially much faster than solving the subproblem. The first adaptive oracle is used to generate inexact but valid cutting planes, and the second adaptive oracle gives a valid upper bound of the true optimal objective. These two oracles progressively “adapt” towards the true exact oracle if provided with an increasing number of exact solutions, stored throughout the iterations. These adaptive oracles are embedded within a Benders-type algorithm able to handle inexact information. We compare the Benders with adaptive oracles against a standard Benders algorithm on a stochastic investment planning problem. The proposed algorithm shows the capability to substantially reduce the computational effort to obtain an -optimal solution: an illustrative case is 31.9 times faster for a 1.00% convergence tolerance and 15.4 times faster for a 0.01% tolerance. Keywords Benders decomposition · Inexact oracles · Adaptive oracles · Stochastic investment planning Mathematics Subject Classification 90-08 Computational methods for problems pertaining to operations research and mathematical programming · 90-04 Software, source code, etc. for problems pertaining to operations research and mathematical programming · 90C06 Large-scale problems in mathematical programming · 90C15 Stochastic programming
Research is supported by the Engineering and Physical Sciences Research Council (EPSRC) through the CESI Project (EP/P001173/1). Extended author information available on the last page of the article
123
N. Mazzi et al.
1 Introduction In this paper we consider problems that can be expressed in the form min
x∈X
f (x) +
πi g(xi , ci ),
i∈I
(1)
where g(xi , ci ) is the optimal solution of the LP subproblem SP :
g(xi , ci ) := min {ciC yi | Ayi ≤ Bxi }. yi ∈Y
(2)
The set of problems I is finite, the xi are (possibly overlapping) subvectors of x, Y is a convex polyhedron, and the πi are non-negative constants. The coefficient matrices A, B, and C are the same in every subproblem so the subproblems differ only through the value of their parameters, xi and ci . The ci are vectors of coefficients and the xi are vectors of variables for (1) and parameters for (2). However, elements of xi may be set to fixed values in x ∈ X , so become equivalent to parame
Data Loading...
