Network problems arise, as the name indicates, in applications that can be represented as the flow of a commodity in a network. The resulting programs can be linear or non-linear, however, we only discuss the linear case. Due to the network structure of the model, we can develop fast techniques for solving these problems.

For example, assume that you are the manager of a company that has different production lines in different locations. The goods produced by your company (in these different locations) are shipped to the distribution centers. In order to simplify the problem, let us say that there are two production lines and two distribution centers. The cost of shipping a unit of product from a production center to each distribution center is known. We also assume that we know the demand at each center and the production level of each production line. In other words, we have a table of the form:

You want to minimize the cost of shipping your product to the different distribution centers while meeting the demand of the customers. Remember, your company produces items or units that cannot be broken down into fractions (cars for example); i.e., some of the decision variables representing your shipping problem must be integer.

One can build a mathematical model for solving the previous problem. An integer variable, , indicates the number of items that need to be shipped from location to distribution center . Mathematically, our model is

and all variables are integer. The first two constraints indicate that production centers 1 and 2 supply exactly 30 and 25 units of the product, respectively. The last two constraints indicate that we must meet the demand of each of the distribution lines. Note that we can formulate the first two constraints as constraints and the last two constraints as constraints; that is, we can produce at most 30 and 25 units and we do not want to exceed the demand of 20 and 35 units. However, since the total supply is equal to the total demand, it is clear that any feasible solution must satisfy all constraints as equality constraints (if the total demand is not equal to the total supply, we can add dummy production lines or distribution centers to the problem to make it balanced).

Note that only two entries appear in the column of a decision variable and that all the coefficients are equal to 1 (or -1 if we multiply a constraint by -1). In general, this constraint-matrix structure arises in optimization problems that can be modeled as directed network problems. For example, the previous model has the following network representation:

This is why, in such models, the constraint matrix is called the node-arc incidence matrix. It can be shown that every non-singular square sub-matrix of the node-arc incidence matrix is triangular and has a determinant that is either 1 or -1. Given this property along with integer demand and supply vectors, there is an integer optimal solution for the previous problem. That is, we can ignore the integer restriction on the variables and solve our problem as a linear program. As a matter of fact, the special structure of this class of problems permits developing special algorithms for solving these problems efficiently.

Network problems cover a large number of applications. Here, we describe some of them:

Transportation Problem. We have a commodity that can be produced in different locations and needs to be shipped to different distribution centers. Given the cost of shipping a unit of commodity between each two points, the capacity of each production center, and the demand at each distribution center, find the minimal cost shipping plan. Note that the example that we described above is a transportation model.

Assignment Problem. There are individuals that need to be assigned to different tasks. Each individual is assigned to one job only and each job is performed by one person. Given the cost that each individual charges for performing each of the jobs, find a minimal cost assignment. Clearly, this problem is a special case of the transportation problem. Many techniques are developed for solving this class of problems since it is often encountered in application (for example, relaxing the tour constraint in a traveling salesman problem results in an assignment problem).

Maximum Value Flow. Given a directed network of roads that connects two cities and the capacities of these roads, find the maximum number of units (cars) that can be routed from one city to another. Here, the constraints are the equilibrium or balance equations at each node (or road intersection); i.e., flow of the cars into a node is equal to the flow of the cars out of that node.

Shortest Path Problem. Given a directed network and the length of each arc in this network, find a shortest between two given nodes.

Minimum Cost Flow Problem. Given a directed network with upper and lower capacities on each of its arcs, and given a set of external flows (positive or negative) that need to be routed through this network, find the minimal cost routing of the given flows through this network. Here, the cost per unit of flow on each arc is assumed to be known.

The NEOS SERVER operates a linear network optimization facility containing the codes NETFLOW and RELAX-IV to solve these problems remotely over the Internet.

• References

Up To:

Constrained Optimization.

[ OTC Home Page | NEOS Guide | NEOS Server | Optimization Tree ]

Updated 28 March 1996