Paper Info
Title
Minimizing the maximum network flow: models and algorithms with resource synergy considerations.
Abstract
In this paper, we model and solve the network interdiction problem of minimizing the maximum flow through a network from a given source node to a terminus node, while incorporating different forms of superadditive synergy effects of the resources applied to the arcs in the network. Within this context, we examine linear, concave, and convex-concave synergy relationships, illustrate their relative effect on optimal solution characteristics, and accordingly develop and test effective solution procedures for the underlying problems. For a concave synergy relationship, which yields a convex programme, we propose an inner-linearization procedure that significantly outperforms the competitive commercial solver SBB by improving the quality of solutions found by the latter by 6.2% (within a time limit of 1800 CPUs), while saving 84.5% of the required computational effort. For general non-concave synergy relationships, we develop an outer-approximation-based heuristic that achieves solutions of objective value 0.20% better than the commercial global optimization software BARON, with a 99.3% reduction in computational effort for the subset of test problems for which BARON could identify a feasible solution within the set time limit. Journal of the Operational Research Society (2012) 63, 1693-1707. doi:10.1057/jors.2012.8 Published online 7 March 2012
Year
DOI
Venue
2012
10.1057/jors.2012.8
JORS
Keywords
Field
DocType
network interdiction,synergy,resource allocation,inner-linearization,outer-approximation
Flow network,Heuristic,Global optimization,Scheduling (computing),Computer science,Algorithm,Resource allocation,Maximum flow problem,Time limit,Solver,Management science,Operations management
Journal
Volume
Issue
ISSN
63
12
0160-5682
Citations 
PageRank 
References 
0
0.34
11
Authors
2
Name
Order
Citations
PageRank
Brian J. Lunday15510.08
Hanif D. Sherali23403318.40