A Polynomial-Time Algorithm for Optimizing over N-Fold 4-Block Decomposable Integer Programs

DOI10.1007/978-3-642-13036-6_17zbMath1285.90022arXiv0911.4055OpenAlexW1588457598MaRDI QIDQ3569820

Raymond Hemmecke, Robert Weismantel, Matthias Köppe

Publication date: 22 June 2010

Published in: Integer Programming and Combinatorial Optimization (Search for Journal in Brave)

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

zbMATH Keywords

stochastic integer programmingpolynomial-time algorithmGraver basisaugmentation algorithm\(N\)-fold integer programsstochastic multi-commodity flow

Mathematics Subject Classification ID

Integer programming (90C10) Stochastic programming (90C15)

Related Items

Huge Unimodular $n$-Fold Programs, A colorful Steinitz lemma with application to block-structured integer programs, Block-structured integer programming: can we parameterize without the largest coefficient?, \(n\)-fold integer programming in cubic time, Convex integer optimization by constantly many linear counterparts, The complexity landscape of decompositional parameters for ILP: programs with few global variables and constraints, Graver basis and proximity techniques for block-structured separable convex integer minimization problems, The double exponential runtime is tight for 2-stage stochastic ILPs, Subset Selection in Sparse Matrices, The double exponential runtime is tight for 2-stage stochastic ILPs, Huge multiway table problems