Nonlinear Optimization Examples

Example 15.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, 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} \quad , \quad j=1,\ldots ,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_{24} + x_{34}$

The boundary constraints are

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

and the flow constraints are

$\begin{eqnarray*} x_{13} & = & x_{32} + x_{34} \\ x_{24} & = & x_{12} + x_{32} \\ x_{12} + x_{13} & = & x_{24} + x_{34} \end{eqnarray*}$

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. The optimal solution is shown in Output 15.2.1.

proc iml;
start MAXFLOW(x);
   f = x[3] + x[4];
   return(f);
finish MAXFLOW;

/* constraints: lower and upper traffic limits; */
/* what flows into an intersection must flow out */
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 2};
ods select ParameterEstimates#2;
CALL NLPCG(xres,rc,"MAXFLOW",x,optn,con);

Output 15.2.1: Optimizing Flow

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

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:

$\begin{eqnarray*} t_{12} & = & 5 + 0.1 x_{12} / (1 - x_{12}/10) \\ t_{13} & = & x_{13} / (1 - x_{13}/30) \\ t_{32} & = & 1 + x_{32} / (1 - x_{32}/10) \\ t_{24} & = & x_{24} / (1 - x_{24}/30) \\ t_{34} & = & 5 + x_{34} / (1 - x_{34}/10) \end{eqnarray*}$

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

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

$\begin{eqnarray*} x_{13} & = & x_{32} + x_{34} \\ x_{24} & = & x_{12} + x_{32} \\ x_{24} + x_{34} & = & F = 5 \end{eqnarray*}$

In the following code, the NLPNRR subroutine is used to solve the minimization problem. The optimal solution is shown in Output 15.2.2.

title 'Minimize Total Delay in Network';
proc iml;
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);

Output 15.2.2: Parameter Estimates

Minimize Total Delay in Network

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.55112E-17	1.000000	Lower BC
4	X4	2.500001	5.702481
5	X5	2.499999	5.777778

The active constraints and corresponding Lagrange multiplier estimates (costs) are shown in Output 15.2.3.

Output 15.2.3: Constraints and Lagrange Multiplier Estimates

Linear Constraints Evaluated at Solution
1	ACT	-4.441E-16	=	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	4.4409E-16	=	-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