ABSTRACT
Communication on the Internet or via phones, satellites, or landlines; distribution of goods over a supply chain; transmission of blood through veins; movement of traffic on roads, connection of towns by roads, connection of yards by railroads, flight of planes between airports, and the like, have something in common: all can be modeled as networks. Taha (2002) reported that as much as 70% of the real-world mathematical programming problems can be represented by network-related models. These models are widely utilized in real life for many reasons. First, networks are excellent visualization tools and easy to understand as problems can be presented pictorially over networks. Second, network models have several computationally efficient and easy-to-implement algorithms that take advantage of the special structure of networks, thus providing a key advantage for researchers to handle large-size real-life combinatorial problems. Furthermore, network flow problems appear as subproblems when mathematical programming techniques such as decomposition, column generation, or Lagrangian relaxation are utilized to solve large-scale complex mathematical models. This is a key advantage because using efficient network algorithms results in
and Science
faster convergence when the above-mentioned techniques are utilized. For example, shortest path problems, one of the simplest network flow models that can be solved quite efficiently, appear in many networks: transportation, communication, logistics, supply chain management, Internet routing, molecular biology, physics, sociology, and so on.
