Optimization Online


Benders Decomposition with Adaptive Oracles for Large Scale Optimization

Nicoḷ Mazzi(nicolo.mazzi***at***ed.ac.uk)
Andreas Grothey(A.Grothey***at***ed.ac.uk)
Ken McKinnon(K.McKinnon***at***ed.ac.uk)
Nagisa Sugishita(s1576972***at***sms.ed.ac.uk)

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 epsilon-optimal solution: an illustrative case is 25.2 times faster for a 1.00\% convergence tolerance and 11.6 times faster for a 0.01\% tolerance.

Keywords: Benders decomposition, inexact oracles, adaptive oracles, stochastic investment planning

Category 1: Applications -- OR and Management Sciences

Citation: 2019

Download: [PDF]

Entry Submitted: 08/05/2019
Entry Accepted: 08/05/2019
Entry Last Modified: 08/05/2019

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society