Robust discrete optimization and network flows (Q1424278)

The authors propose an approach to address data uncertainty for discrete optimization and network flow problems that allows to control the degree of conservation of the solution and is computationally tractable both theoretically and practically. Main results: (1) A robust integer programming (IP) problem of moderately size is suggested for an IP problem where both the cost coefficients and the data in the constraints are subject to uncertainty. (2) When only the cost coefficients are subject to uncertainty and the problem is a 0-1 discrete optimization problem on \(n\) variables, then they solve the robust counterpart by solving \(n+1\) nominal problems. Moreover, if such a problem is an \(\alpha\)-approximable NP-hard problem, then the robust counterpart remains \(\alpha\)-approximable. (3) When only the cost coefficients are subject to uncertainty and the problem is a minimum cost flow problem, then the authors proposed a polynomial time algorithm for the robust counterpart by solving a collection of minimum cost flow problems in a modified network.