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, 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

$\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 f(x), where f(x) is

f(x) = x₂₄ + x₃₄

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₁₂, X2=x₁₃, X3=x₃₂, X4=x₂₄, X5=x₃₄

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.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 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:

$t_{12} & = & 5 + 0.1 x_{12} / (1 - x_{12}/10) \t_{13} & = & x_{13} / (1 - x_{13}... ...t_{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 F=5 vehicles per minute have to be moved through the network. The objective is now to minimize

f =f(x)= t₁₂ x₁₂ + t₁₃ x₁₃ + t₃₂ x₃₂ + t₂₄ x₂₄ + t₃₄ x₃₄

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

Chapter Contents
Previous
Next
Top