Partial Lagrangian in the Max-Flow problem

Question

In the question: "Partial" Lagrangian Dual in LP

It is argued that considering a partial Lagrangian $L_{partial}$, where we Dualize only some of the constraints, results in a tighter relaxation. Therefore optimizing w.r.t. the dual variables in the partial relaxation should result in a $0$ duality gap.

If there is 0 duality gap, for the optimal lagrange multiplier $\lambda^\star$, by optimizing $\max_{x\in D} L_{partial}(x,\lambda^\star)$ (with $D$ corresponding to the region that is not dualized), one would expect to find the optimal primal solution $x^\star$ (which is true in standard duality with 0 duality gap).

However, that leads to the confusing following argument: Dualizing only the capacity constraints in the max flow problem, results in a problem which is the uncapacited max-flow problem (for given multipliers $\lambda$). Then by finding $\lambda^\star$, one can solve the max-flow problem by solving a shortest-path problem. Of course this doesn't make a lot of sense, since the max-flow solution would typically not be a single-path. Therefore there should be some error in the above reasoning.

Answer 1

The error comes in assuming that, given a zero duality gap, the solution to the relaxed LP (which I agree becomes a shortest path problem) would be the optimal flow solution.

Let $X$ the set of all nonnegative flow vectors $x$ that satisfy the flow conservation constraints on the network, ignoring capacities, let $c\in\mathbb{R}_{+}^{n}$ be the vector of arc capacities, and let $a'x$ be the original objective function (any expression that computes the total flow out of the source or into the sink). Note that $X$ is a pointed cone, since $x=0$ is a feasible flow and, for any valid flow $x$ and scalar $t>0,$ $t\cdot x$ is also a valid flow. The relaxed problem becomes

$$ \min_{\lambda\ge0}\max_{x\in X}\left[a'x-\lambda'(x-c)\right] $$ or equivalently $$ \min_{\lambda\ge0}\max_{x\in X}\left[(a-\lambda)'x+\lambda'c\right] $$

where $\lambda$ is the vector of Lagrange multipliers for the capacity limits.

For fixed $\lambda$ one of two things happens. If a unit flow $x\in X$ on any path from source to sink satisfies $(a-\lambda)'x>0,$ the inner problem is unbounded, since we can scale $x$ upward indefinitely. On the other hand, if every unit flow from source to sink has $(a-\lambda)'x\le0,$ the optimal solution to the inner problem is $x=0,$ resulting in objective value $\lambda'c.$

So Lagrangian relaxation will search, among just those $\lambda$ for which no path has positive objective value, for the one that minimizes $\lambda'c.$ That will turn out to be the capacity portion of the optimal solution to the dual of the original max flow LP. Using that $\lambda$, $\lambda'c$ is the objective value of the dual to the full LP (since the dual multipliers of the flow balance constraints are multiplied by 0 in the dual objective), meaning $\lambda'c$ equals the maximum flow. The optimal solution to the relaxed flow problem will be 0, or at least $x=0$ will be an optimal solution.

So, bottom line, relaxation gives you the objective value (the maximum possible flow volume) but not the solution (the flow producing that result).

Answer 2

Unfortunately, there is NO guarantee to find the primal feasible solution in the context of Lagrangian relaxation, especially when it comes to solving integer programming.

In order to get a feasible primal solution, at least as far as I know, you would need to repair the achieved solution (usually an infeasible one) in each iteration by using some manipulations. This is what the so-called Lagrangian heuristic. For more details please, see the following links. Also, you could find more useful topics either by searching in the community or by googling.

• Using LR-based method to solve mixed integer programming
• Lagrangian relaxation and network optimization