|
|
|
|
|
If one, however, is interested in algorithms that provably lead to an optimal solution, this leads, in the context of integer optimization, to the study of the algorithmic theory of generating sets of various kinds, including Hilbert bases of cones, Gröbner bases of toric ideals, and Graver bases of matrices.
Recently several breakthroughs in the theory of Graver bases have been obtained. These allow to study families of highly structured problems, so called N-fold integer programs, which have a block structure similar to multi-commodity flow problems. One obtains polynomial-time algorithms for linear and nonlinear integer optimization problems in these families.
I present an overview of these ideas and a recent result (joint work with Raymond Hemmecke and Robert Weismantel, appeared in IPCO 2010), which generalizes N-fold integer programs and two-stage integer programs with N scenarios to N-fold 4-block decomposable integer programs. This is a structure that appears in stochastic integer multi-commodity flow problems.
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.