Nonlinear Optimization Examples: Example 11.2: Network Flow and Delay

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 et al. 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, vehicles enter and leave the network. The parameter $x_{ij}$ refers to the flow from node to node . The requirement that traffic that flows into each intersection must also flow out is described by the linear equality constraint

$\sum_i x_{ij} = \sum_i x_{ji} , j=1, ... ,n$

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:

$0 \le x_{ij} \le c_{ij}$

The goal in this problem is to maximize the flow, which is equivalent to maximizing the objective function

, where

$f(x) = x_{24} + x_{34}$

The boundary constraints are

$0 \le & x_{12}, x_{32}, x_{34} & \le 10 \ 0 \le & x_{13}, x_{24} & \le 30 \$

and the flow constraints are

$x_{13} & = & x_{32} + x_{34} \ x_{24} & = & x_{12} + x_{32} \ x_{12} + x_{13} & = & x_{24} + x_{34}$

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. The following code finds the maximum flow:

  
    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.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 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 and assume that the following formulas describe the travel time as decreasing functions of the amount of traffic:

$t_{12} & = & 5 + 0.1 x_{12} / (1 - x_{12}/10) \ t_{13} & = & x_{13} / (1 - x_{1... ...24} & = & x_{24} / (1 - x_{24}/30) \ t_{34} & = & 5 + x_{34} / (1 - x_{34}/10)$

These formulas use the road capacities (upper bounds), and you can assume that 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

$0 \le & x_{12}, x_{32}, x_{34} & \le 10 \ 0 \le & x_{13}, x_{24} & \le 30 \$

$x_{13} & = & x_{32} + x_{34} \ x_{24} & = &x_{12} + x_{32} \ x_{24} + x_{34} & = & f = 5$

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

Top of Page