Given an optimal solution to the LP, show how it can be used to construct a directed cycle with minimal directed cycle mean cost

Question

Let $\mathcal G = (\mathcal V, \mathcal A)$ be directed graph with associated edge costs $c_{i,j}$ that has at least one directed cycle.

Define the directed cycle mean cost to be $\frac {\{\text {sum of cost of arcs}\}} { \text {# arcs}}$.

Consider the LP:

$\max \lambda$

s.t: $p_i + \lambda \le p_j + c_{i,j}$ where $(i,j)\in \mathcal A$.

I've shown:

• The LP is feasible.

• If $(\lambda,p)$ is a feasible solution then the directed cycle mean cost of every directed cycle is at least $\lambda$.

• The LP has an optimal solution (doesn't contain a line and $\lambda$ can't be greater than the maximum cost).

Now, I want to show given an optimal solution to the LP, it can be used to construct a directed cycle with minimal directed cycle mean cost.

I really don't have a clue on how to proceed. I don't see how an optimal solution give me the required information ?

Answer 1

I traced the LP back to this article. Here you can find the answer to your question presented in Theorem 2.

It might be helpful to look at the dual problem of your LP. This is analyzed in the above paper in Theorem 1. In this dual program your variables are defined as variables $z_e\ge 0$ for the edges. Then they show that the optimal cycle is given by the edges for which $z_e>0$ in the optimal solution. Then you can use the complementary slackness condition. It follows that the tight inequalities in your program define the optimal cycle.

Note also that the author provide an interpretation for the variables in your LP. The value of $p_i$ of a vertex not in the optimal cycle denotes the "least length of the path from the vertex $v_i$ to the optimal cycle".