The OPTLSO Procedure

Function Value Caching

To improve performance, the OPTLSO procedure implements a caching system. This caching system helps reduce the overall workload of the solver by eliminating duplicate function evaluations. As the individual optimizers (citizens) submit new trial points for evaluation, the points are saved in the cache along with their function evaluation values. Then, before beginning the potentially expensive function evaluations for a new trial point, PROC OPTLSO determines whether a similar point already exists within the cache. If a similar point is found in the cache, its function values are immediately returned for the newly submitted point. Returning function values from the cache instead of duplicating the effort of computing new function values can lead to significant performance improvements for the overall procedure.

The cache is implemented as a splay tree, similar to that used in Gray and Kolda (2006); Hough, Kolda, and Patrick (2000). The splay tree rebalances itself as new points are added to the cache. This rebalancing ensures that recently added or accessed points are maintained at the root of the tree and are therefore available for quick retrieval. This splay tree data structure lends itself nicely to the needs of a caching system.

When determining whether a newly submitted trial point has a similar point already in the cache, PROC OPTLSO compares the new trial point to all previous trial points by using the value of the CACHETOL= option in the PROC OPTLSO statement. This value specifies a tolerance to use in comparing two points and determining whether the two points are similar enough. In addition to the CACHETOL= value, the cache comparison also takes into account the _SCALE_ values that are specified as part of the variable data set that is specified in the VARIABLES= option.

Two points $x$ and $y$ are considered cache equivalent if

$|x_ i - y_ i| \le s_ i \epsilon , \text { for } i= 1,\ldots ,n$

where $s$ denotes the corresponding scaling vector. Thus, if a point $x$ has been evaluated (or is being evaluated) and a point $y$ is submitted for evaluation and satisfies the preceding criteria, $y$ is “cache evaluated” instead of being evaluated directly. In this case, $y$ is associated with $f(x)$ and $c(x)$ . Although the splay tree is very efficient, the cache lookup time for quick evaluation might eventually dominate the evaluation process time. You can use the CACHEMAX= option to limit the size of the cache.

Even when the FCMP functions are not defined, the cache system helps to avoid redundant computations when the linear constraints are explicitly handled.