×

zbMATH — the first resource for mathematics

Robust discrete optimization and network flows. (English) Zbl 1082.90067
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.

MSC:
90C10 Integer programming
90B10 Deterministic network models in operations research
90C35 Programming involving graphs or networks
PDF BibTeX XML Cite
Full Text: DOI