I know that the strong duality holds for linear programming and the optimal values of the objective functions in the primal and dual linear programming problems are equal.

I am wondering whether the optimal value of minimum cost flow problem is equal to the optimal value of its dual problem or not, when the cost and capacity of the edges are integer. I am asking this because for a graph with integer cost and capacities for the edges, I have found the optimal flow with minimum cost and from that I have obtained feasible node potentials as the optimal value of the dual variables. But the optimal value of the objective function in the dual problem is less than the objective function in the primal problem and the difference is equal to 1.

I would be thankful for your help.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.