Robust integer programming

DOI10.1016/J.ORL.2014.10.002MaRDI QIDQ1785307zbMATH OpenOpenAlexFDO

Authors Shmuel Onn

Publication date 28 September 2018

Published in Operations Research Letters (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1402.2852

zbMATH Keywords

graver basisinteger programmingmulticommodity flowrobust optimizationstatistical table

Mathematics Subject Classification ID

Integer programming (90C10) Abstract computational complexity for mathematical programming problems (90C60)

Abstract: We provide a complexity classification of four variants of robust integer programming when the underlying Graver basis is given. We discuss applications to robust multicommodity flows and multidimensional transportation, and describe an effective parametrization of robust integer programming.

Recommendations

• Optimization over integers with robustness in cost and few constraints
• K-adaptability in two-stage robust binary programming
• The Graver complexity of integer programming
• On the complexity of robust geometric programming with polyhedral uncertainty
• Strong formulations of robust mixed 0-1 programming

Cites work

• \(N\)-fold integer programming
• A polynomial oracle-time algorithm for convex integer minimization
• All Linear and Integer Programs Are Slim 3‐Way Transportation Programs
• Nonlinear discrete optimization. An algorithmic theory
• Robust discrete optimization and its applications
• Theory and applications of robust optimization

Cited in

(4)

• Parameterized resiliency problems
• A note on \(\Sigma_2^p\)-completeness of a robust binary linear program with binary uncertainty set
• On robust solutions to uncertain linear complementarity problems and their variants
• Optimization over integers with robustness in cost and few constraints

This page was built for publication: Robust integer programming

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1785307)