Elke Eisenschmidt

Title:
Integral decomposition of discrete/polyhedral sets and the design of survivable networks

Abstract:
We introduce a new class of optimization problems called integer Minkowski programs. The formulation of these problems involves finitely many integer variables and nonlinear constraints depending on functionals defined on families of discrete or polyhedral sets.

The crucial result in this framework is, that under certain assumptions, one may reformulate the integer Minkowski programs as integer linear programs by making use of integral generating systems. This way, complicated nonlinear constraints may be exactly linearized.

We apply this technique to the network design problem subject to survivability constraints being formulated as integer Minkowski program. The general reformulation theorem applied to this formulation gives a new formulation of the survivable network design problem as integer linear program, this way linearizing the survivability constraints.