Revised Hock & Schittkowski models for automatable test scenarios

by Stephan K.H. Seidl

Version 6, Wed, 07 May 2014 15:09:23 +0200


Extended abstract

The classic Hock & Schittkowski model collection [2] is widely accepted as one of the mandatory test scenarios for Nonlinear Programming codes. The test models are small and more than a few of them are maliciously formulated.

Unfortunately, a number of models out of that suite only pursues the strategy of some kind of misguidance, provoking that the solver under test locks into a secondary minimum. Such a behavior is less desirable while algorithm development where one simply wants to know whether the solver implementation in hand does work or not. In addition there are models that actually exhibit a better solution than the so far documented one. And, after all, the solution to some examples is not unique. Taking all those things together, a potential new tester must appear as being left quite alone with his considerations because he knows neither what degree of difficulty a particular model actually has, nor where possible differences in data really come from, not mentioning the transmission bugs and typos.

To simplify a test scenario based on the H+S model suite the present work goes into the following direction. The models are firstly represented using a high-level and easy-to-parse language, to have them lucidly arranged and machine-readable at the same time. A subset of the language belonging to APMonitor has finally been chosen as the representation vehicle though one model, namely #67, cannot correctly be formulated therein. In contrast to Hedengren's work [1] the examples coded in such a way here make consequently use of bounds instead of inequalities wherever that is possible, and, they do not expect hidden semantic properties of APMonitor. So name space questions can only be an issue when the models run on APMonitor itself. Appropriate executions have therefore been performed by the author at some point, showing that there are no incompatibilities with APMonitor. While the source of the revised H+S model suite is represented and maintained in APM format, two other formats, AMPL and FMCMAP, have been derived by means of automatic translation. So the model suite is available in three different formats at all where each format comes with two branches, one for the strict or classic mode and one for some new and hence recommended mode.

Controlled through a global macro here, the feasible domain of certain models can be reduced such that unwanted secondary minima are hopefully completely removed, and so non-uniqueness, if some. The author further believes that the installed modifications are sufficiently inconsiderable in the sense that the so-treated models do not trivially turn out. As the result, the run of a solver under test can no longer be misunderstood, it yields the only existing solution or even not. Readers who find a hole still being open in the described scenario are invited to provide their knowledge. That way we shall have an outstanding test set someday.

There are two models that are special to a certain extent. For the model #67 that is frankly spoken an illegal case for many solvers, there are three formulations given. The first one, #67-1, ignores the basic idea of that model, namely, proving a solving software has procedure handling capabilities. #67-1 yields a solution that makes sense but that is not the exactly required one. #67-1 works with the discontinuities removed. #67-2 shows an exact implementation of #67, with all its immanent user function discontinuities left untouched, but with perfect derivatives on the other hand. #67-3 uses the same technique as #67-2 but provides the same intuitive result as #67-1 does. So, #67-1 serves to formally pass the H+S model collection while #67-2 and #67-3 exhibit some approach to treat models with procedures in such a manner that perfect derivatives can easily be provided.

The discontinuities of model #87, i.e. the ones of the other somewhat special model, have been softened on source level applying two different techniques. #87-1 uses small transition domains. The best known solution to #87-1 unfortunately lies inside such a transition domain such that the solution is sensible but not exact. Contrariwise, #87-2 applies some technique that is also known as Mathematical Programs with Equilibrium Constraints (MPEC), yielding the exact solution that is on top of everything better than the one given in [2].

The remainder of the models is more or less straightforwardly formulated. Solvers being able to master #25-1, #25-2, and #54-1 in IEEE 754 double precision floating-point arithmetic are probably equipped with some internal scaling mechanism. #120 through #128 are not part of the classic H+S model collection but the author believes that the right place where they should be presented as very good test cases, too, is here.

The revised and modified model suite in all has finally been solved using FMC in IEEE 754 quadruple precision floating-point arithmetic to obtain numerical reference results with at least 14 valid decimal digits. These numerical reference results can easily be picked up from the presented source files such that from now on a solver can not only be tested in an automatical manner but can also be checked with respect to the precision of the solution it yields.


Full text, change log

For the full text click revisedhsmodels.pdf (currently authentication required), for the change log click Changelog.
Comments, bug reports, and better solutions are welcome.


Acknowledgements

I am grateful to Klaus Schittkowski, Bayreuth, for pointing out the need for passing this model suite, and so for waking up my interest in the topic. I would also like to thank John D. Hedengren, Provo UT, and Robert J. Vanderbei, Princeton NJ, for providing machine-readable model files through the Internet, taken as the starting point for the present work.


References

[1] J. D. Hedengren: APMonitor Documentation: Hock & Schittkowski Models.
http://www.apmonitor.com/wiki/index.php/Apps/HockSchittkowski/
[2] W. Hock and K. Schittkowski: Test Examples for Nonlinear Programming Codes.
Vol 187 of Lecture Notes in Economics and Mathematical Systems (Springer, 1981)
[3] K. Schittkowski: Test Examples for Nonlinear Programming Codes:
All Problems from the Hock-Schittkowski-Collection.
http://www.ai7.uni-bayreuth.de/test_problem_coll.pdf (2009)
[4] K. Schittkowski: An Updated Set of 306 Test Problems for Nonlinear
Programming with Validated Optimal Solutions, User's Guide.
http://www.ai7.uni-bayreuth.de/test_problems.pdf and
http://www.ai7.uni-bayreuth.de/test_probs_src.zip, file PROB.FOR (2011)
[5] R. J. Vanderbei: AMPL: Nonlinear Optimization Models: Hock & Schittkowski Models.
http://www.princeton.edu/∼rvdb/ampl/nlmodels/hs/
[6] R. J. Vanderbei: AMPL: Nonlinear Optimization Models: Revised Hock & Schittkowski Models.
http://orfe.princeton.edu/∼rvdb/ampl/nlmodels/hs_new/

All models

For the files found in the source code column below, stored in a single archive, click revisedhsmodels.tar.gz (0.5 MByte). The tarball contains a directory structure where each directory consists of the files in question represented in some format, namely APM, AMPL or FMCMAP, and expanded for a particular macro definition state. There is one more directory for the unprocessed files themselves. Macro definitions are binary here. Hence, the tarball contains all the possible cases such that there is no need for running the macro processor anymore. The AMPL branch out of the tar archive, as it comes from a macro expansion in accordance with -Drevisedhs and -Uhavefsign2, can also be seen in [6]. Indeed, one should take into account that it is possible that the tarball version here is more recent than the one provided with [6]. From version 4 on, it is furthermore sure that there is, on the one hand, at least one description available per model and format, and, that there is, on the other hand, no description provided that can a priori not be executed for some reason. So the AMPL branch, for example, does contain #68-2 and #69-2, but does not contain #68-1, #69-1, #68-3 and #69-3.

# Source code Comments
1 tp001.apm differs from [1]
2 tp002r.apm.m4 macro-controllable, differs from [1]
3 tp003.apm  
4 tp004.apm  
5 tp005.apm  
6 tp006.apm  
7 tp007.apm  
8 tp008r.apm.m4 macro-controllable
9 tp009r.apm.m4 macro-controllable
10 tp010.apm  
11 tp011.apm erroneous solution formulæ in [2]
12 tp012.apm  
13 tp013.apm  
14 tp014.apm differs from [1]
15 tp015.apm differs from [1]
16 tp016r.apm.m4 macro-controllable, differs from [1]
17 tp017.apm differs from [1]
18 tp018.apm  
19 tp019.apm differs from [1]
20 tp020r.apm.m4 macro-controllable, differs from [1], erroneous solution formulæ in [5]
21 tp021.apm differs from [1]
22 tp022.apm  
23 tp023.apm  
24 tp024.apm  
25-1 tp025v1.apm exact formulation of #25, pretty small gradient at starting point, differs from [1]
25-2 tp025v2.apm some trial without mitigation, source-level scaling applied
25-3 tp025v3.apm poor man's formulation of #25, initialization improved
26 tp026r.apm.m4 macro-controllable
27 tp027.apm  
28 tp028.apm  
29 tp029r.apm.m4 macro-controllable
30 tp030.apm differs from [1]
31 tp031.apm differs from [1]
32 tp032.apm  
33 tp033r.apm.m4 macro-controllable, differs from [1]
34 tp034.apm differs from [1]
35 tp035.apm  
36 tp036.apm differs from [1]
37 tp037.apm  
38 tp038.apm  
39 tp039.apm  
40 tp040r.apm.m4 macro-controllable
41 tp041.apm differs from [1]
42 tp042.apm differs from [1]
43 tp043.apm  
44 tp044.apm  
45 tp045r.apm.m4 macro-controllable, erroneous initialization vector in [2]
46 tp046.apm not found in [3], found in [4]
47 tp047r.apm.m4 macro-controllable, better solution found
48 tp048.apm  
49 tp049.apm differs from [1]
50 tp050.apm  
51 tp051.apm  
52 tp052.apm  
53 tp053.apm  
54-1 tp054v1.apm exact formulation of #54, honors on-board scaling, errors in [2] and [4]
54-2 tp054v2.apm poor man's formulation of #54, source-level mapping applied and more
55 tp055r.apm.m4 macro-controllable, differs from [1] and [5], error in [2]
56 tp056r.apm.m4 macro-controllable, differs from [1] and [5]
57 tp057.apm differs from [1] and [5]
58 tp058.apm not found in [3], found in [4], differs from [1]
59 tp059.apm verification required, error in [2]
60 tp060.apm  
61 tp061r.apm.m4 macro-controllable
62 tp062.apm  
63 tp063.apm  
64 tp064.apm  
65 tp065.apm differs from [1] and [5]
66 tp066.apm differs from [1] and [5]
67-1 tp067v1.apm poor man's formulation of #67, discontinuities removed
67-2 tp067v2.map, tp067v2x.c not representable in APM, so also not available in AMPL here, exact formulation of #67, with discontinuities; FMC line search merit function behavior during major iteration step

2, Major iteration 2 , 3, Major iteration 3 , 4, Major iteration 4 , and the last one, 30, Major iteration 30

67-3 tp067v3.map, tp067v3x.c not representable in APM, so also not available in AMPL here, free and intuitive formulation of #67, without discontinuities
68-1 tp068r1.apm.m4 macro-controllable, differs from [1], erfc() not directly supported in AMPL
68-2 tp068r2.apm.m4 macro-controllable, high-quality Chebyshev approximation substituted for erfc(), well-suited for APMonitor and AMPL, unacceptable conversion times with FMC due to symbolic differentiation
68-3 tp068r3.map.m4, tp068r3x.c macro-controllable, equivalent to #68-2 but written for FMC
69-1 tp069r1.apm.m4 macro-controllable, differs from [1], erfc() not directly supported in AMPL
69-2 tp069r2.apm.m4 macro-controllable, high-quality Chebyshev approximation substituted for erfc(), well-suited for APMonitor and AMPL, unacceptable conversion times with FMC due to symbolic differentiation
69-3 tp069r3.map.m4, tp069r3x.c macro-controllable, equivalent to #69-2 but written for FMC
70 tp070.apm verification required, errors in [2]
71 tp071.apm differs from [1]
72 tp072.apm differs from [1]
73 tp073.apm  
74 tp074.apm  
75 tp075.apm  
76 tp076.apm  
77 tp077.apm erroneous initialization vector in [2]
78 tp078.apm  
79 tp079.apm  
80 tp080.apm  
81 tp081.apm typo in solution in [2]
82   does not exist
83 tp083.apm  
84 tp084.apm  
85 tp085.apm verification required, differs from [1]
86 tp086.apm verification required, differs from [1] and [5]
87-1 tp087r1.apm.m4 macro-controllable, verification required, typo in solution in [2], better solution found, transition domains, differs from [1] and [2]
87-2 tp087r2.apm.m4 macro-controllable, verification required, typo in solution in [2], better solution found, MPEC, differs from [1] and [2]
88 tp088r.apm.m4 macro-controllable
89 tp089r.apm.m4 macro-controllable, indetermined solution presented in [2]
90 tp090r.apm.m4 macro-controllable, indetermined solution presented in [2]
91 tp091r.apm.m4 macro-controllable, indetermined solution presented in [2]
92 tp092r.apm.m4 macro-controllable, indetermined solution presented in [2]
93 tp093.apm differs from [1]
94   does not exist
95 tp095.apm  
96 tp096.apm  
97 tp097.apm  
98 tp098.apm  
99 tp099.apm strange definitions in [1]
100 tp100.apm  
101 tp101.apm differs from [1] and [5]
102 tp102.apm  
103 tp103.apm  
104 tp104.apm differs from [1] and [5]
105 tp105.apm better solution found, differs from [1] and [5]
106 tp106.apm  
107 tp107.apm erroneous initialization vector in [2], differs from [1] and [5]
108 tp108r.apm.m4 macro-controllable, indetermined solution presented in [2], differs from [1] and [5]
109 tp109.apm verification required, sign error in [2], differs from [1] and [5]
110 tp110.apm missing bracket in objective function in [2]
111 tp111.apm  
112 tp112.apm verification required, error in equation 3 in [2], improvable solution in [2]
113 tp113.apm  
114 tp114.apm  
115   does not exist
116 tp116.apm differs from [1] and [5]
117-1 tp117r1.apm.m4 macro-controllable, exact formulation of #117r, verification required, differs from [1] and [5]
117-2 tp117r2.apm.m4 macro-controllable, condensed formulation of #117r for human readers, verification required, differs from [1] and [5]
117-3 tp117r3.apm.m4 macro-controllable, benevolent formulation of #117r, verification required
118 tp118.apm  
119 tp119.apm typo in solution in [2]
120 tp120.apm not part of the classic H+S model collection, 3 balls in a spheric cage, benevolent initialization, rcage = 0.1
121 tp121.apm not part of the classic H+S model collection, 3 balls in a spheric cage, traditional initialization, rcage = 0.1
122 tp122.apm not part of the classic H+S model collection, 3 balls in a spheric cage, benevolent initialization, rcage = 1
123 tp123.apm not part of the classic H+S model collection, 3 balls in a spheric cage, traditional initialization, rcage = 1
124 tp124.apm not part of the classic H+S model collection, 3 balls in a spheric cage, benevolent initialization, rcage = 10
125 tp125.apm not part of the classic H+S model collection, 3 balls in a spheric cage, traditional initialization, rcage = 10
126 tp126.apm not part of the classic H+S model collection, all is going to vanish
127 tp127.apm not part of the classic H+S model collection, all is going to vanish
128 tp128.apm not part of the classic H+S model collection, all is going to vanish

Wed, 07 May 2014 15:09:23 +0200
Stephan K.H. Seidl