Approximation Hierarchies for the cone of flow matrices

Please always quote using this URN: urn:nbn:de:0297-zib-68424
  • Let $G$ be a directed acyclic graph with $n$ arcs, a source $s$ and a sink $t$. We introduce the cone $K$ of flow matrices, which is a polyhedral cone generated by the matrices $1_P 1_P^T \in R^{n\times n}$, where $1_P\in R^n$ is the incidence vector of the $(s,t)$-path $P$. Several combinatorial problems reduce to a linear optimization problem over $K$. This cone is intractable, but we provide two convergent approximation hierarchies, one of them based on a completely positive representation of $K$. We illustrate this approach by computing bounds for a maximum flow problem with pairwise arc-capacities.

Download full text files

Export metadata

Metadaten
Author:Guillaume Sagnol, Marco Blanco, Thibaut Sauvage
Document Type:ZIB-Report
Tag:Approximation hierarchies; Copositive programming; Flows in graphs
MSC-Classification:90-XX OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING / 90Cxx Mathematical programming [See also 49Mxx, 65Kxx] / 90C25 Convex programming
90-XX OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING / 90Cxx Mathematical programming [See also 49Mxx, 65Kxx] / 90C35 Programming involving graphs or networks [See also 90C27]
Date of first Publication:2018/04/23
Series (Serial Number):ZIB-Report (18-20)
ISSN:1438-0064
Published in:Appeared in: Electronic Notes in Discrete Mathematics Volume 64, February 2018, Pages 275–284 INOC 2017 – 8th International Network Optimization Conference
DOI:https://doi.org/10.1016/j.endm.2018.02.002