Chapter Contents Previous Next
 Nonlinear Optimization Examples

Example 11.2: Network Flow and Delay

The following example is taken from the user's guide of the GINO program (Liebman, Lasdon, Schrage, and Waren 1986). A simple network of five roads (arcs) can be illustrated by a path diagram.

The five roads connect four intersections illustrated by numbered nodes. Each minute, F vehicles enter and leave the network. The parameter xij refers to the flow from node i to node j. The requirement that traffic that flows into each intersection j must also flow out is described by the linear equality constraint

In general, roads also have an upper limit on the number of vehicles that can be handled per minute. These limits, denoted cij, can be enforced by boundary constraints:
The goal in this problem is to maximize the flow, which is equivalent to maximizing the objective function f(x), where f(x) is
f(x) = x24 + x34
The boundary constraints are
and the flow constraints are

The three linear equality constraints are linearly dependent. One of them is deleted automatically by the optimization subroutine. The following notation is used in this example:

X1=x12,   X2=x13,   X3=x32,   X4=x24,   X5=x34
Even though the NLPCG subroutine is used, any other optimization subroutine would also solve this small problem.

   proc iml;
title 'Maximum Flow Through a Network';
start MAXFLOW(x);
f = x[4] + x[5];
return(f);
finish MAXFLOW;

con = {  0.  0.  0.  0.  0.   .   . ,
10. 30. 10. 30. 10.   .   . ,
0.  1. -1.  0. -1.  0.  0. ,
1.  0.  1. -1.  0.  0.  0. ,
1.  1.  0. -1. -1.  0.  0. };
x = j(1,5, 1.);
optn = {1 3};
call nlpcg(xres,rc,"MAXFLOW",x,optn,con);


The optimal solution is shown in the following output.

 Optimization Results Parameter Estimates N Parameter Estimate GradientObjectiveFunction ActiveBoundConstraint 1 X1 10.000000 0 Upper BC 2 X2 10.000000 0 3 X3 10.000000 1.000000 Upper BC 4 X4 20.000000 1.000000 5 X5 -1.11022E-16 0 Lower BC

 Value of Objective Function = 30

Finding the maximum flow through a network is equivalent to solving a simple linear optimization problem, and for large problems, the LP procedure or the NETFLOW procedure of the SAS/OR product can be used. On the other hand, finding a traffic pattern that minimizes the total delay to move F vehicles per minute from node 1 to node 4 includes nonlinearities that need nonlinear optimization techniques. As traffic volume increases, speed decreases. Let tij be the travel time on arc (i,j) and assume that the following formulas describe the travel time as decreasing functions of the amount of traffic:
These formulas use the road capacities (upper bounds), and you can assume that F=5 vehicles per minute have to be moved through the network. The objective is now to minimize
f =f(x)= t12 x12 + t13 x13 + t32 x32 + t24 x24 + t34 x34
The constraints are

In the following code, the NLPNRR subroutine is used to solve the minimization problem:

   proc iml;
title 'Minimize Total Delay in Network';
start MINDEL(x);
t12 = 5. + .1 * x[1] / (1. - x[1] / 10.);
t13 = x[2] / (1. - x[2] / 30.);
t32 = 1. + x[3] / (1. - x[3] / 10.);
t24 = x[4] / (1. - x[4] / 30.);
t34 = 5. + .1 * x[5] / (1. - x[5] / 10.);
f = t12*x[1] + t13*x[2] + t32*x[3] + t24*x[4] + t34*x[5];
return(f);
finish MINDEL;

con = {  0.  0.  0.  0.  0.   .   . ,
10. 30. 10. 30. 10.   .   . ,
0.  1. -1.  0. -1.  0.  0. ,
1.  0.  1. -1.  0.  0.  0. ,
0.  0.  0.  1.  1.  0.  5. };

x = j(1,5, 1.);
optn = {0 3};
call nlpnrr(xres,rc,"MINDEL",x,optn,con);


The optimal solution is shown in the following output.

 Optimization Results Parameter Estimates N Parameter Estimate GradientObjectiveFunction ActiveBoundConstraint 1 X1 2.500001 5.777778 2 X2 2.499999 5.702478 3 X3 5.551115E-17 1.000000 Lower BC 4 X4 2.500001 5.702481 5 X5 2.499999 5.777778

 Value of Objective Function = 40.303030303

The active constraints and corresponding Lagrange multiplier estimates (costs) are shown in the following output.

 Linear Constraints Evaluated at Solution 1 ACT 0 = 0 + 1.0000 * X2 - 1.0000 * X3 - 1.0000 * X5 2 ACT 4.4409E-16 = 0 + 1.0000 * X1 + 1.0000 * X3 - 1.0000 * X4 3 ACT 0 = -5.0000 + 1.0000 * X4 + 1.0000 * X5

 First Order Lagrange Multipliers Active Constraint LagrangeMultiplier Lower BC X3 0.924702 Linear EC [1] 5.702479 Linear EC [2] 5.777777 Linear EC [3] 11.480257

 Chapter Contents Previous Next Top