Journal
JOURNAL OF OPTIMIZATION THEORY AND APPLICATIONS
Volume 161, Issue 2, Pages 506-532Publisher
SPRINGER/PLENUM PUBLISHERS
DOI: 10.1007/s10957-013-0378-5
Keywords
Multicommodity flow; Integer programming; Cutting planes; Node reliabilities; Congestion
Funding
- National Science Foundation [CMMI-1100765]
- Defense Threat Reduction Agency [HDTRA-10-01-0050]
- Air Force Office of Scientific Research [FA9550-12-1-0353]
- Office of Naval Research [N000141310036]
- Div Of Civil, Mechanical, & Manufact Inn
- Directorate For Engineering [1100765] Funding Source: National Science Foundation
Ask authors/readers for more resources
In this paper, we consider the problem of sending a set of multiple commodities from their origin to destination nodes via intermediate hubs. Each hub node is associated with a reliability function, which depends on the total flow that crosses that hub. The probability that each commodity is successfully relayed from its origin to its destination is given by the product of hub reliabilities on the commodity's path. The problem we consider seeks to find minimum-cost commodity paths such that each commodity reaches its destination with a sufficiently large probability. We first formulate the problem as a nonlinear multicommodity network-flow problem and prove that it is strongly NP-hard. We then present two linearization techniques for this formulation, and propose a pair of lower- and upper-bounding formulations, which can then be used within an exact cutting-plane algorithm to solve the problem. Finally, we analyze the computational effectiveness of our proposed strategies on a set of randomly generated instances.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available