(Dealing with Infeasibility) Consider the relaxation algorithm applied to a minimum cost flow problem with initial prices p0
(a) Assume that the problem is feasible. Show that the total price increase pi - p0i of any node i prior to termination of the algorithm satisfies
(b) Discuss how the result of part (a) can be used to detect infeasibility.
(c) Suppose we introduce some artificial arcs to guarantee that the problem is feasible. Discuss how to select the cost coefficients of the artificial arcs so that optimal solutions are not affected in the case where the original problem is feasible.