next up previous
Next: Generalized Networks Up: Network Optimization for Consultants Previous: Assignment Problem

Unifying Model: Minimum Cost Network Flows

All of the above models are special types of network flow problems: they each have a specialized algorithm that can find solutions hundreds of times faster than plain linear programming.

They can all also be seen as examples of a much broader model, the minimum cost network flow model. This model represents the broadest class of problem that can be solved much faster than linear programming while still retaining such nice properties as integrality of solution and appeal of concept.

Like the maximum flow problem, it considers flows in networks with capacities. Like the shortest path problem, it considers a cost for flow through an arc. Like the transportation problem, it allows multiple sources and destinations. In fact, all of these problems can be seen as special cases of the minimum cost flow problem.

Consider a directed network with n nodes. The decision variables are tex2html_wrap_inline318 , the flow through arc (i,j). The given information includes:

This last value has a sign convention: The objective is to minimize the total cost of sending the supply through the network to satisfy the demand.

Note that for this model, it is not necessary that every arc exists. We will use the convention that summations are only taken over arcs that exist. The linear programming formulation for this problem is:

displaymath314

Again, we will assume that the network is balanced, so tex2html_wrap_inline354 , since dummies can be added as needed. We also still have a nice integrality property. If all the tex2html_wrap_inline334 and tex2html_wrap_inline328 are integral, then the resulting solution to the linear program is also integral.

Minimum cost network flows are solved by a variation of the simplex algorithm and can be solved more than 100 times faster than equivalently sized linear programs. From a modeling point of view, it is most important to know the sort of things that can and cannot be modeled in a single network flow problem:

Can do
  1. Lower bounds on arcs. If a variable tex2html_wrap_inline318 has a lower bound of tex2html_wrap_inline362 , upper bound of tex2html_wrap_inline328 , and cost of tex2html_wrap_inline322 , change the problem as follows:
    • Replace the upper bound with tex2html_wrap_inline368 ,
    • Replace the supply at i with tex2html_wrap_inline372 ,
    • Replace the supply at j with tex2html_wrap_inline376 ,
    Now you have a minimum cost flow problem. Add tex2html_wrap_inline378 to the objective after solving and tex2html_wrap_inline362 to the flow on arc (i,j) to obtain a solution of the original problem.
  2. Upper bounds on flow through a node. Replace the node i with nodes i' and i''. Create an arc from i' to i'' with the appropriate capacity, and cost 0. Replace every arc (j,i) with one from j to i' and every arc (i,j) with one from i'' to j. Lower bounds can also be handled this way.
  3. Convex, piecewise linear costs on arc flows (for minimization). This is handled by introducing multiple arcs between the nodes, one for each portion of the piecewise linear function. The convexity will assure that costs are handled correctly in an optimal solution.

Can't do
  1. Fixed cost to use a node.
  2. Fixed cost to use an arc.
  3. ``Proportionality of flow.'' That is, if one unit enters node i, then you insist that .5 units go to node j and .5 to node k.
  4. Gains and losses of flow along arcs, as in power distribution.

Note that although these cannot be done in a single network, it may be possible to use the solutions to multiple networks to give you an answer. For instance, if there is only one arc with a fixed cost, you can solve both with and without the arc to see if it is advantageous to pay the fixed cost.

Here is an example of a problem that doesn't look like a network flow problem, but it really is:

A company must meet the following demands for cash at the beginning of each of the next six months:

tabular153

At the beginning of month 1, the company has $150 in cash and $200 worth of bond 1, $100 worth of bond 2 and $400 worth of bond 3. Of course, the company will have to sell some bonds to meet demands, but a penalty will be charged for any bonds sold before the end of month 6. The penalties for selling $1 worth of each bond are shown in the table below.

tabular158

(a)
Assuming that all bills must be paid on time, formulate a balanced transportation problem that can be used to minimize the cost of meeting the cash demands for the next six months.

(b)
Assume that payment of bills can be made after they are due, but a penalty of $0.02 per month is assessed for each dollar of cash demands that is postponed for one month. Assuming all bills must be paid by the end of month 6, develop a transshipment model that can be used to minimize the cost of paying the next six months' bills.

[ Hint: Transshipment points are needed, in the form tex2html_wrap_inline412 cash available at beginning of month t after bonds for month t have been sold, but before month t demand is met. Shipments into tex2html_wrap_inline420 occur from bond sales and tex2html_wrap_inline422 . Shipments out of tex2html_wrap_inline420 occur to tex2html_wrap_inline426 and demands for months tex2html_wrap_inline428 .]


next up previous
Next: Generalized Networks Up: Network Optimization for Consultants Previous: Assignment Problem

Michael A. Trick
Mon Nov 11 15:13:01 EST 1996