ties that look nothing like dots, lines, and stuff flowing along those lines. The reason decision analysts make a strong effort to put business problems into the form of a network flow problem is that these problems are computationally easier to solve than similar-sized problems without the network flow structure. Also, the solu- tions that come from network flow optimization have one extremely nice property: If the constraints and objective are linear functions, which we call a linear network Figure 26.4 Tree graph represents a fan-out backhaul network. Downloaded from Digital Engineering Library @ McGraw-Hill (www.digitalengineeringlibrary.com) Copyright © 2004 The McGraw-Hill Companies. All rights reserved. Any use is subject to the Terms of Use as given at the website. Capacity Calculations for Cellular Networks Capacity and Quality Principles flow problem, and the constraints have integer (whole number) coefficients, then the optimum calculated by a method known as the network simplex method will have integer values. There may be equally valid optimal solutions, not integer solutions, that other optimization algorithms will find as their solutions. However, the network sim- plex method runs fast and finds whole-number optimal solutions to whole-number problems. The network flow formulation is a graph with arcs that can carry flow from one node to another. The arc from node i to node j carries flow Xij. Each arc can have a minimum flow Aij, zero or some specified lower bound, and may have a maximum flow bij or may be unbounded. Each arc also has a cost Cij(Xij) that is a function of the flow Xij. The ob- ject of the network flow problem is to get a specific flow from a source node S to a tar- get node T for the minimum cost. In the case of backhaul, the lower bounds are all zero because there are no required links that we have to use. There are no upper bounds be- cause we can use as much transport as we are willing to pay for. When we solve the linear network flow problem, the arcs that have flow Xij not at 