The Cone of Flow Matrices: Approximation Hierarchies and Applications
Please always quote using this URN: urn:nbn:de:0297-zib-64399
- 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 $\vec{1}_P\vec{1}_P^T\in\RR^{n\times n}$, where $\vec{1}_P\in\RR^n$ is the incidence vector of the (s,t)-path P. We show that several hard flow (or path) optimization problems, that cannot be solved by using the standard arc-representation of a flow, reduce to a linear optimization problem over $\mathcal{K}$. This cone is intractable: we prove that the membership problem associated to $\mathcal{K}$ is NP-complete. However, the affine hull of this cone admits a nice description, and we give an algorithm which computes in polynomial-time the decomposition of a matrix $X\in \operatorname{span} \mathcal{K}$ as a linear combination of some $\vec{1}_P\vec{1}_P^T$'s. Then, 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 the quadratic shortest path problem, as well as a maximum flow problem with pairwise arc-capacities.
Author: | Guillaume Sagnol, Marco Blanco, Thibaut Sauvage |
---|---|
Document Type: | ZIB-Report |
Tag: | Approximation Hierarchies; Copositive Programming; Flows in graphs; Semidefinite Programming |
MSC-Classification: | 05-XX COMBINATORICS (For finite fields, see 11Txx) / 05Cxx Graph theory (For applications of graphs, see 68R10, 81Q30, 81T15, 82B20, 82C20, 90C35, 92E10, 94C15) / 05C21 Flows in graphs |
90-XX OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING / 90Cxx Mathematical programming [See also 49Mxx, 65Kxx] / 90C22 Semidefinite programming | |
Date of first Publication: | 2017/06/28 |
Series (Serial Number): | ZIB-Report (17-32) |
ISSN: | 1438-0064 |
Published in: | Appeared in: Networks 72(1): 128-150 |
DOI: | https://doi.org/10.1002/net.21820 |