Column-Generation for Design of Survivable Electricity Distribution Networks

Abstract

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.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Aug 31, 2004
Accession Number
ADA487349

Entities

People

  • Andy Philpott
  • Kavinesh Singh
  • R. Kevin Wood

Organizations

  • Naval Postgraduate School

Tags

DTIC Thesaurus Topics

  • Algorithms
  • Capital Investments
  • Computer Programming
  • Decomposition
  • Demographic Cohorts
  • Electricity
  • Failure Mode And Effect Analysis
  • High Voltage
  • Integer Programming
  • Linear Programming
  • Load Monitoring
  • Mesh Networks
  • New Zealand
  • Operations Research
  • Standards
  • Urban Areas
  • Voltage

Fields of Study

  • Computer science

Readers

  • Operations Research
  • Systems Analysis and Design