Optimal solution corresponds to a strongly connected component Is there a way to ensure that the non-zero entries of the optimal solution to a linear program with variables defined over the edges of a directed graph correspond to a strongly connected component. To be more specific, here is the formulation I came up with for my question: 
I have a directed graph $G = (V,E)$. The edge $e$ has weight $w_e, e\in E$. I would like to maximize a linear function $f(x_1,\ldots, x_{|E|}) := \sum_{e\in E} w_e x_e$ over variables $x_e\in[0,1], e\in E$ defined for each edge subject to some other linear constraints in $x:=(x_1,\ldots, x_{|E|})$. Suppose $x^*$ is an optimal solution. Is there some way to derive a condition on the weights $w_e$ under which the digraph formed from the edges in the set $\{e\in E: x^*_e > 0\}$ (i.e., the support of $x$) would be strongly connected? I am looking for some directions to solve that problem when the constraints are such that the problem admits such condition.      
 A: Let me begin by giving a terrible solution that involves exponentially many constraints.
The digraph formed by a set of edges is strongly connected if there's no cut: no nonempty set $S \subsetneq V$ for which there are no edges going from $S$ to $V \setminus S$. There's a traditional way to enforce this in the case where $\mathbf x$ is an integer vector:
$$
    \sum_{i \in S} \sum_{j \notin S} x_{ij} \ge 1.
$$
But in our case, we just care about edges $e$ where $x_e > 0$, even if this is only $0.0001$. Really, we want to ask that the sum above is $>0$, but that's not a traditional linear-programming constraint.
Instead, we can ask that
$$
    \sum_{i \in S} \sum_{j \notin S} x_{ij} \ge \epsilon \qquad \qquad \forall S \subsetneq V, S \ne \emptyset
$$
where we can deal with $\epsilon$ in two ways:


*

*As a really small number; just set it to $10^{-9}$ or whatever. This has the advantage that you don't have to do anything weird, and can just use an out-of-the-box LP solver. The disadvantage is that you're discarding some solutions where this constraint is violated even though the LHS is positive.

*As a symbolic, infinitesimal number: whenever you have to compare two numbers $a + b\epsilon, c + d\epsilon$ as you're solving the LP, first compare $a$ versus $c$, and don't even bother looking at $b$ versus $d$ unless $a=c$. This makes $\epsilon$ "as small as it needs to be" and may remind you of the lexicographic pivoting technique. The downside is I'm not sure you can get an LP solver to do this for you.



There are $2^{|V|}-2$ constraints here, which seems pretty bad. In practice, we can often use row generation together with the dual simplex method to avoid having to think about all of them at once.
Start by solving your LP with none of these extra constraints. When you get a solution $\mathbf x^*$, if the digraph corresponding to the support of $\mathbf x^*$ is not strongly connected, find a cut $S$, and add the constraint corresponding to $S$. If you add it as a row to your optimal tableau, then it will remain dual feasible, but stop being primal feasible (since we've added a constraint that $\mathbf x^*$ violates). The dual simplex method can reoptimize it with, hopefully, not too many steps.
Then, we repeat until we get a strongly connected solution.

Here's another potential approach; I think it's better in most cases. The idea is: if we find a solution $\mathbf x$ with $x_e > 0$ for all $e$, it will definitely be strongly connected. So let's do our best to do that.
For each edge $e$, find a solution $\mathbf x^e$ that just maximizes $x_e$ subject to your usual constraints. Depending on your constraints, it's possible that $x_e = 0$ in all solutions; we may still be fine if this happens, depending. We have to solve $|E|$ different linear programs here, but that's all the work we'll have to do.
Now, take the point
$$
   \mathbf x^* = \frac1{|E|} \sum_{e \in E} \mathbf x^e
$$
If it's possible to set $x_e > 0$, then $\mathbf x^e$ will do it, and therefore $\mathbf x^*$ will do it: $\mathbf x^*$ has all the possible positive edges. Also, because we took a convex combination of feasible solutions, the result is still feasible.
Now, check if $\mathbf x^*$ gives us a strongly connected graph. Either it does, or else it's not possible to do it at all.
Moreover, if you have to optimize some objective function subject to the strongly connected condition, you can first find the optimal solution $\mathbf x^{**}$ that optimizes your objective function. Then, for any $\epsilon >0$, $(1-\epsilon)\mathbf x^{**} + \epsilon \mathbf x^{*}$ will nearly optimize your objective function, but still be strongly connected.
(The thing that the exponentially-many-constraints approach will do that this approach won't is find an optimal strongly-connected solution in this case. This approach just gets arbitrarily close to optimal.)
