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 x_{ij} 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 c_{ij}, 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) = x_{24} + x_{34}
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=x_{12}, X2=x_{13}, X3=x_{32}, X4=x_{24}, X5=x_{34}
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 
Gradient Objective Function 
Active Bound Constraint 
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.11022E16 
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 t_{ij} 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)= t_{12} x_{12} + t_{13} x_{13} + t_{32} x_{32} +
t_{24} x_{24} + t_{34} x_{34}
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 
Gradient Objective Function 
Active Bound Constraint 
1 
X1 
2.500001 
5.777778 

2 
X2 
2.499999 
5.702478 

3 
X3 
5.551115E17 
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.4409E16 
= 
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 
Lagrange Multiplier 
Lower BC 
X3 
0.924702 
Linear EC 
[1] 
5.702479 
Linear EC 
[2] 
5.777777 
Linear EC 
[3] 
11.480257 

Copyright © 1999 by SAS Institute Inc., Cary, NC, USA. All rights reserved.