Partial Lagrangian in the Max-Flow problem

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.

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).

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.