Dantzig-Wolfe Decomposition for Monotone Two-Stage Stochastic Mixed-Integer Programs Applied to a Power Distribution System Resilience Problem

We develop a novel Dantzig-Wolfe (DW) decomposition algorithm for monotone two-stage stochastic mixed-integer programs (SMIPs). The key novelty in this algorithm is to relax the non-anticipativity constraints (NACs) in line with the monotonicity in the problem. We prove (i) that the relaxed restricted master problem (RMP) faster identifies dominated columns that cannot improve the RMP objective value, (ii) that our monotone DW algorithm does not increase the optimality gap in special cases, and (iii) that for SMIPs with pure-binary first-stage decisions, our DW algorithm can be embedded within a simple branch-and-bound procedure. Numerically, our DW algorithm may find solutions up to 92\% faster than the traditional DW algorithm. We apply our new algorithm to a power distribution system resilience problem in which nodes in the electricity network may be equipped with electricity apparatus, i.e., electricity adapters, such that mobile emergency power sources (e.g., generators or batteries) can be deployed following a disaster, to temporarily provide power while the electricity grid is being repaired. We find that installing such adapters may reduce expected power loss by up to 40%, and by up to 19% compared to installing them according to the highest loads policy, which is a popular heuristic.

Article

Download

View PDF