Refine
Document Type
- ZIB-Report (2)
Language
- English (2)
Has Fulltext
- yes (2)
Is part of the Bibliography
- no (2)
Keywords
- Flows in graphs (2) (remove)
Institute
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.
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.