We have m communication terminals, each to be connected to one out of a given collection of concentrators. Suppose that there is a cost aij for connecting terminal i to concentrator j, and that each concentrator j has an upper bound bj on the number of terminals it can be connected to. Also, each terminal i can be connected to only a given subset of concentrators.
(a) Formulate the problem of finding the minimum cost connection of terminals to concentrators as a minimum cost flow problem. Hint: You may use the fact that there exists an integer optimal solution to a minimum cost flow problem with integer supplies and arc flow bounds. (This will be shown in Chapter 5.)
(b) Suppose that a concentrator j can operate in an overload condition with a number of connected terminals greater than bj , up to a number bj > bj . In this case, however, the cost per terminal connected becomes aij > aij . Repeat part (a).
(c) Suppose that when no terminals are connected to concentrator j there is a given cost savings cj > 0. Can you still formulate the problem as a minimum cost flow problem?