Column-Generation for Design of Survivable Electricity Distribution Networks

摘要

We investigate the problem of designing survivable electricity distribution networks subject to multiple, non-simultaneous link failures under a radial-network operating configuration. We formulate this problem as a two- stage stochastic mixed-integer program in which first-stage decisions expand capacity; recourse decisions configure the network to operate as a tree and to meet demand, by opening and closing electrical switches. Dantzig-Wolfe decomposition of this formulation leads to (a) a master problem comprising binary capacity-expansion and high-level operating decisions; and (b) mixed- integer, column-generating subproblems which represent deterministic capacity- expansion models. A 'super-arc representation' of the network significantly reduces the number of binary variables, and provides a tighter linear- programming relaxation for the subproblems. Column generation with super-arc subproblems solves the model significantly faster than CPLEX can solve the original, extensive model.