We study this problem in the more general framework of so-called Integer Minkowski Programs. The formulation of such problems involves finitely many integer variables and nonlinear constraints involving functionals defined on families of discrete or polyhedral sets. This is done in a two-stage process. In a first step, we consider a set-valued, super-additive mapping depending on finitely many integer variables. Then we define Minkowski-additive and antitone functionals on the sets obtained in the first step.
The crucial issue in this framework is that under certain assumptions it is possible to reformulate the programs obtained in this way as integer linear programs by making use of integral generating sets. It turns out that complicated nonlinear constraints are exactly linearized and much easier to deal with. We apply this reformulation-technique to the network design problem for integer or fractional flows and linearize the arc-survivability constraints in this way.
In the more general framework we show that we may truncate the discrete or polyhedral sets by ideals of the underlying vector-space without affecting the reformulation theory.
We will present a new class of algorithms to compute integral generating sets of families of discrete sets via a project-and-lift approach.