Integer Minkowski Programs and the Design of Survivable Networks

Authors Elke Eisenschmidt, Matthias Köppe, A. Laugier

Publication date 27 October 2006

Network design and communication in computer systems (68M10) Communication networks in operations research (90B18) Integer programming (90C10) Mixed integer programming (90C11) Programming involving graphs or networks (90C35)

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.

This page was built for publication: Integer Minkowski Programs and the Design of Survivable Networks

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6478120)