@misc{SagnolBlancoSauvage, author = {Sagnol, Guillaume and Blanco, Marco and Sauvage, Thibaut}, title = {The Cone of Flow Matrices: Approximation Hierarchies and Applications}, issn = {1438-0064}, doi = {10.1002/net.21820}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-64399}, abstract = {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.}, language = {en} } @misc{SagnolBlancoSauvage, author = {Sagnol, Guillaume and Blanco, Marco and Sauvage, Thibaut}, title = {Approximation Hierarchies for the cone of flow matrices}, issn = {1438-0064}, doi = {10.1016/j.endm.2018.02.002}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-68424}, abstract = {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.}, language = {en} }