A global optimization algorithm for reliable network design

Jitamitra Desai and Suvrajeet Sen

European Journal of Operational Research, 2010, vol. 200, issue 1, pages 1-8

Abstract: In this paper, we consider the problem of designing reliable networks that satisfy supply/demand, flow balance, and capacity constraints, while simultaneously allocating certain resources to mitigate the arc failure probabilities in such a manner as to minimize the total cost of network design and resource allocation. The resulting model formulation is a nonconvex mixed-integer 0-1 program, for which a tight linear programming relaxation is derived using RLT-based variable substitution strategies and a polyhedral outer-approximation technique. This LP relaxation is subsequently embedded within a specialized branch-and-bound procedure, and the proposed approach is proven to converge to a global optimum. Various alternative partitioning strategies that could potentially be employed in the context of this branch-and-bound framework, while preserving the theoretical convergence property, are also explored. Computational results are reported for a hypothetical scenario based on different parameter inputs and alternative branching strategies. Related optimization models that conform to the same class of problems are also briefly presented.

Keywords: Reliable; network; design; Global; optimization; Branch-and-bound; Reformulation-Linearization; Technique; (RLT); Convexification; techniques; Resource; allocation (search for similar items in EconPapers)
Date: 2010

Downloads: (external link)
http://www.sciencedirect.com/science/article/B6VCT ... 60bcc15e04ee44639248
Full text for ScienceDirect subscribers only

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: http://EconPapers.repec.org/RePEc:eee:ejores:v:200:y:2010:i:1:p:1-8

Access Statistics for this article

European Journal of Operational Research is edited by Roman Slowinski, Jesus Artalejo, Jean-Charles. Billaut, Robert Dyson and Lorenzo Peccati

More articles in European Journal of Operational Research from Elsevier
Series data maintained by Heidi Boesdal ().