A global optimization algorithm for reliable network design |
| |
Authors: | Jitamitra Desai Suvrajeet Sen |
| |
Affiliation: | 1. Department of Industrial and Systems Engineering, Lehigh University, 200 West Packer Avenue, #325 Mohler Lab, Bethlehem, PA 18015, USA;2. Department of Industrial, Welding, and Systems Engineering, The Ohio State University, 1971 Neil Avenue, Columbus, OH 43210, USA |
| |
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&ndash Linearization Technique (RLT) Convexification techniques Resource allocation |
本文献已被 ScienceDirect 等数据库收录! |
|