A polynomial-time algorithm for optimizing over N-fold 4-block decomposable integer programs

Raymond Hemmecke, Matthias Köppe, Robert Weismantel

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

14 Scopus citations

Abstract

In this paper we generalize N-fold integer programs and two-stage integer programs with N scenarios to N-fold 4-block decomposable integer programs. We show that for fixed blocks but variable N, these integer programs are polynomial-time solvable for any linear objective. Moreover, we present a polynomial-time computable optimality certificate for the case of fixed blocks, variable N and any convex separable objective function. We conclude with two sample applications, stochastic integer programs with second-order dominance constraints and stochastic integer multi-commodity flows, which (for fixed blocks) can be solved in polynomial time in the number of scenarios and commodities and in the binary encoding length of the input data. In the proof of our main theorem we combine several non-trivial constructions from the theory of Graver bases. We are confident that our approach paves the way for further extensions.

Original languageEnglish
Title of host publicationInteger Programming and Combinatorial Optimization - 14th International Conference, IPCO 2010, Proceedings
Pages219-229
Number of pages11
DOIs
StatePublished - 2010
Event14th International Conference on Integer Programming and Combinatorial Optimization, IPCO 2010 - Lausanne, China
Duration: 9 Jun 201011 Jun 2010

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume6080 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference14th International Conference on Integer Programming and Combinatorial Optimization, IPCO 2010
Country/TerritoryChina
CityLausanne
Period9/06/1011/06/10

Keywords

  • Graver basis
  • N-fold integer programs
  • augmentation algorithm
  • polynomial-time algorithm
  • stochastic integer programming
  • stochastic multi-commodity flow

Fingerprint

Dive into the research topics of 'A polynomial-time algorithm for optimizing over N-fold 4-block decomposable integer programs'. Together they form a unique fingerprint.

Cite this