06-52

Integer Minkowski Programs and the Design of Survivable Networks

by Eisenschmidt, Elke; Köppe, Matthias; Laugier, Alexandre

 

Preprint series: 06-52, Preprints

MSC:
90C35 Programming involving graphs or networks
90C10 Integer programming
90C11 Mixed integer programming
68M10 Computer networks, See also {90B12}

 

Abstract: We introduce a new class of optimization problems 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. We show that, under certain assumptions, it is possible to reformulate them as integer linear programs, by making use of integral generating sets. We then apply this technique to the network design problem for fractional and integral flows subject to survivability constraints.


The author(s) agree, that this abstract may be stored asfull text and distributed as such by abstracting services.

Letzte Änderung: 01.03.2018 - Ansprechpartner: Webmaster