Paper Info
Title
Robust discrete optimization and network flows
Abstract
We propose an approach to address data uncertainty for discrete optimization and network ∞ow problems that allows controlling the degree of conservatism of the solution, and is computationally tractable both practically and theoretically. In particular, when both the cost coe-cients and the data in the constraints of an integer programming problem are subject to uncertainty, we propose a robust integer programming problem of moderately larger size that allows controlling the degree of conservatism of the solution in terms of probabilistic bounds on constraint violation. When only the cost coe-cients are subject to uncertainty and the problem is a 0 ¡ 1 discrete optimization problem on n variables, then we solve the robust counterpart by solving at most n+1 instances of the original problem. Thus, the robust counterpart of a polynomially solvable 0¡1 discrete optimization problem remains polynomially solvable. In particular, robust matching, spanning tree, shortest path, matroid intersection, etc. are polynomially solvable. We also show that the robust counterpart of an NP-hard fi-approximable 0 ¡ 1 discrete optimization problem, remains fi-approximable. Finally, we propose an algorithm for robust network ∞ows that solves the robust counterpart by solving a polynomial number of nominal minimum cost ∞ow problems in a modifled network.
Year
DOI
Venue
2003
10.1007/s10107-003-0396-4
Math. Program.
Keywords
Field
DocType
integer programming,robust optimization,network flows
Flow network,Discrete mathematics,Mathematical optimization,Shortest path problem,Discrete optimization,Robust optimization,Combinatorial optimization,Integer programming,Optimization problem,Minimum-cost flow problem,Mathematics
Journal
Volume
Issue
ISSN
98
1-3
0025-5610
Citations 
PageRank 
References 
406
25.18
11
Authors
2
Search Limit
100406
Name
Order
Citations
PageRank
Dimitris J. Bertsimas14513365.31
Melvyn Sim21909117.68