Nonlinear Optimization Examples |
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
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
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:
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
be the travel time on arc
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 vehicles
per minute have to be moved through the network.
The objective is now to minimize
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.
Copyright © 2009 by SAS Institute Inc., Cary, NC, USA. All rights reserved.