Bounds on penalties for dummy arcs in transportation networks (Q1117136)

In several resource allocation problems, one encounters transportation networks which may or may not be feasible, and which may also be accompanied by side constraints. In such contexts, one typically constructs some dummy transportation arcs with associated penalties, which either serve the role of facilitating a convenient starting solution, or seeking a solution to an infeasible problem which minimizes the total flow on the dummy arcs. In either case, particularly when the original transportation problem is infeasible, one would like to know a preferably small lower bound on the dummy arc penalties which could be validly employed. This paper derives such a bound. Extensions to more general networks are also addressed.