betaFeedback

WorksMathematics

Fast Subproblem Solving in Benders Decomposition for Affine Potential-Based Flow Problems with Topology Switching and Scenarios

Abstract

Potential-based flow problems arise for a range of practical problems, like the operation of lossless power networks. The distribution of flows through the network is governed by the potential equation, which relates arc flows and node potentials following arc potential functions. We consider a general variant with affine potential functions, topology switching, and scenarios. It can be solved using a Benders decomposition algorithm, with each scenario corresponding to a subproblem. Subproblem solving time can then significantly contribute to overall running time. We present a fast algorithm to obtain Benders optimality and feasibility cuts from fixed master solutions. Problems with affine potential functions are reduced to equivalent problems where every potential function is the identity function. Optimal primal and dual solutions as well as unbounded dual rays are determined by systems of linear equations (SLE), resulting in a constant number of SLEs solved per subproblem. SLEs are solved using LU-factorizations, with the similarity between primal and dual, scenarios, and master solutions exploited by reusing factorizations via low-rank updates to significantly reduce theoretical complexity. We demonstrate the method on security-constrained optimal transmission switching instances, where subproblem solve time reductions of 97.98 percent compared to a standard LP solver are observed.

Paper details

vlnc:W_pp6nqanq
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
arXiv nonexclusive license
Usage

views · 0

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Mathematics

Not recorded for this paper

View statement
Looking for related papers…