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

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 … Read more

Composition of Near-Planar Infrastructure Network Instances with Certified Skewness Bounds

Computational studies of optimization problems on infrastructure networks may require more suitable instances than are available. We propose a method to obtain additional instances by extracting and joining connected parts of existing networks, reusing their topology and parameters. Many infrastructure networks are near-planar, so added connections should preserve this property. We measure near-planarity by skewness, … Read more

Benders Cut Filtering for Affine Potential-Based Flow Problems with Robustness Scenarios and Topology Switching

Many large-scale optimization problems decompose into a master problem and scenario subproblems, a structure that can be exploited by Benders decomposition. In Benders decomposition, each iteration may generate many cuts from scenario subproblems, and adding all of them as constraints then causes the master problem to grow rapidly. These are constraints that may need to … Read more

Adaptive Subproblem Selection in Benders Decomposition for Survivable Network Design Problems

Scenario-based optimization problems can be solved via Benders decomposition, which separates first-stage (master problem) decisions from second-stage (subproblem) recourse actions and iteratively refines the master problem with Benders cuts. In conventional Benders decomposition, all subproblems are solved at each iteration. For problems with many scenarios, solving only a selected subset can reduce computation. We quantify … Read more