]> Revised Hock & Schittkowski models for automatable test scenarios

Revised Hock & Schittkowski models for automatable test scenarios

by Stephan K.H. Seidl

Version 8, Sun, 19 Feb 2017 21:30:08 +0100


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 treatment of the case #87-2 is described in [5].

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.

Regarding FMC, the tool that has been used to solve the present model suite, this software is now prepared by a recently founded company, Seidl Technologies, to be released into the market. On their homepage one can find out when FMC will finally be available as a product.


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] S. K. H. Seidl: On the Treatment of Jump Discontinuities in Nonlinear Programs.
http://www.stfmc.de/fmc/jdt/x/tlf.xhtml (2014)
[6] R. J. Vanderbei: AMPL: Nonlinear Optimization Models: Hock & Schittkowski Models.
http://www.princeton.edu/∼rvdb/ampl/nlmodels/hs/
[7] 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.6 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 [7]. Indeed, one should take into account that it is possible that the tarball version here is more recent than the one provided with [7]. 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. Further, from version 8 on, the table below has three more columns, APM, AMPL, and FMCMAP. They exhibit the appropriate revised files from the tarball. The files in the columns APM and AMPL have been processed with -Drevisedhs and -Uhavefsign2 and the files in the column FMCMAP with -Drevisedhs and -Dhavefsign2. All the files in the APM, AMPL and FMCMAP columns carry additional instructions to directly express the absolute and relative precision obtained on output. The names of the corresponding variables are zmyabsdevmax and zmyreldevmax.

# Source code APM AMPL FMCMAP Comments
1 tp001.apm APM AMPL FMCMAP differs from [1]
2 tp002r.apm.m4 APM AMPL FMCMAP macro-controllable, differs from [1]
3 tp003.apm APM AMPL FMCMAP  
4 tp004.apm APM AMPL FMCMAP  
5 tp005.apm APM AMPL FMCMAP  
6 tp006.apm APM AMPL FMCMAP  
7 tp007.apm APM AMPL FMCMAP  
8 tp008r.apm.m4 APM AMPL FMCMAP macro-controllable
9 tp009r.apm.m4 APM AMPL FMCMAP macro-controllable
10 tp010.apm APM AMPL FMCMAP  
11 tp011.apm APM AMPL FMCMAP erroneous solution formulæ in [2]
12 tp012.apm APM AMPL FMCMAP  
13 tp013.apm APM AMPL FMCMAP  
14 tp014.apm APM AMPL FMCMAP differs from [1]
15 tp015.apm APM AMPL FMCMAP differs from [1]
16 tp016r.apm.m4 APM AMPL FMCMAP macro-controllable, differs from [1]
17 tp017.apm APM AMPL FMCMAP differs from [1]
18 tp018.apm APM AMPL FMCMAP  
19 tp019.apm APM AMPL FMCMAP differs from [1]
20 tp020r.apm.m4 APM AMPL FMCMAP macro-controllable, differs from [1], erroneous solution formulæ in [6]
21 tp021.apm APM AMPL FMCMAP differs from [1]
22 tp022.apm APM AMPL FMCMAP  
23 tp023.apm APM AMPL FMCMAP  
24 tp024.apm APM AMPL FMCMAP  
25-1 tp025v1.apm APM AMPL FMCMAP exact formulation of #25, pretty small gradient at starting point, differs from [1]
25-2 tp025v2.apm APM AMPL FMCMAP some trial without mitigation, source-level scaling applied
25-3 tp025v3.apm APM AMPL FMCMAP poor man's formulation of #25, initialization improved
26 tp026r.apm.m4 APM AMPL FMCMAP macro-controllable
27 tp027.apm APM AMPL FMCMAP  
28 tp028.apm APM AMPL FMCMAP  
29 tp029r.apm.m4 APM AMPL FMCMAP macro-controllable
30 tp030.apm APM AMPL FMCMAP differs from [1]
31 tp031.apm APM AMPL FMCMAP differs from [1]
32 tp032.apm APM AMPL FMCMAP  
33 tp033r.apm.m4 APM AMPL FMCMAP macro-controllable, differs from [1]
34 tp034.apm APM AMPL FMCMAP differs from [1]
35 tp035.apm APM AMPL FMCMAP  
36 tp036.apm APM AMPL FMCMAP differs from [1]
37 tp037.apm APM AMPL FMCMAP  
38 tp038.apm APM AMPL FMCMAP  
39 tp039.apm APM AMPL FMCMAP  
40 tp040r.apm.m4 APM AMPL FMCMAP macro-controllable
41 tp041.apm APM AMPL FMCMAP differs from [1]
42 tp042.apm APM AMPL FMCMAP differs from [1]
43 tp043.apm APM AMPL FMCMAP  
44 tp044.apm APM AMPL FMCMAP  
45 tp045r.apm.m4 APM AMPL FMCMAP macro-controllable, erroneous initialization vector in [2]
46 tp046.apm APM AMPL FMCMAP not found in [3], found in [4]
47 tp047r.apm.m4 APM AMPL FMCMAP macro-controllable, better solution found
48 tp048.apm APM AMPL FMCMAP  
49 tp049.apm APM AMPL FMCMAP differs from [1]
50 tp050.apm APM AMPL FMCMAP  
51 tp051.apm APM AMPL FMCMAP  
52 tp052.apm APM AMPL FMCMAP  
53 tp053.apm APM AMPL FMCMAP  
54-1 tp054v1.apm APM AMPL FMCMAP exact formulation of #54, honors on-board scaling, errors in [2] and [4]
54-2 tp054v2.apm APM AMPL FMCMAP poor man's formulation of #54, source-level mapping applied and more
55 tp055r.apm.m4 APM AMPL FMCMAP macro-controllable, differs from [1] and [6], error in [2]
56 tp056r.apm.m4 APM AMPL FMCMAP macro-controllable, differs from [1] and [6]
57 tp057.apm APM AMPL FMCMAP differs from [1] and [6]
58 tp058.apm APM AMPL FMCMAP not found in [3], found in [4], differs from [1]
59 tp059.apm APM AMPL FMCMAP verification required, error in [2]
60 tp060.apm APM AMPL FMCMAP  
61 tp061r.apm.m4 APM AMPL FMCMAP macro-controllable
62 tp062.apm APM AMPL FMCMAP  
63 tp063.apm APM AMPL FMCMAP  
64 tp064.apm APM AMPL FMCMAP  
65 tp065.apm APM AMPL FMCMAP differs from [1] and [6]
66 tp066.apm APM AMPL FMCMAP differs from [1] and [6]
67-1 tp067v1.apm APM AMPL FMCMAP poor man's formulation of #67, discontinuities removed
67-2 tp067v2.map, tp067v2x.c     FMCMAP 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     FMCMAP not representable in APM, so also not available in AMPL here, free and intuitive formulation of #67, without discontinuities
68-1 tp068r1.apm.m4 APM   FMCMAP macro-controllable, differs from [1], erfc() not directly supported in AMPL
68-2 tp068r2.apm.m4 APM AMPL   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     FMCMAP macro-controllable, equivalent to #68-2 but written for FMC
69-1 tp069r1.apm.m4 APM   FMCMAP macro-controllable, differs from [1], erfc() not directly supported in AMPL
69-2 tp069r2.apm.m4 APM AMPL   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     FMCMAP macro-controllable, equivalent to #69-2 but written for FMC
70 tp070.apm APM AMPL FMCMAP verification required, errors in [2]
71 tp071.apm APM AMPL FMCMAP differs from [1]
72 tp072.apm APM AMPL FMCMAP differs from [1]
73 tp073.apm APM AMPL FMCMAP  
74 tp074.apm APM AMPL FMCMAP  
75 tp075.apm APM AMPL FMCMAP  
76 tp076.apm APM AMPL FMCMAP  
77 tp077.apm APM AMPL FMCMAP erroneous initialization vector in [2]
78 tp078.apm APM AMPL FMCMAP  
79 tp079.apm APM AMPL FMCMAP  
80 tp080.apm APM AMPL FMCMAP  
81 tp081.apm APM AMPL FMCMAP typo in solution in [2]
82         does not exist
83 tp083.apm APM AMPL FMCMAP  
84 tp084.apm APM AMPL FMCMAP  
85 tp085.apm APM AMPL FMCMAP verification required, differs from [1]
86 tp086.apm APM AMPL FMCMAP verification required, differs from [1] and [6]
87-1 tp087r1.apm.m4 APM AMPL FMCMAP macro-controllable, verification required, typo in solution in [2], better solution found, transition domains, differs from [1] and [2]
87-2 tp087r2.apm.m4 APM AMPL FMCMAP macro-controllable, verification required, typo in solution in [2], better solution found, MPEC, see [5], differs from [1] and [2]
88 tp088r.apm.m4 APM AMPL FMCMAP macro-controllable
89 tp089r.apm.m4 APM AMPL FMCMAP macro-controllable, indetermined solution presented in [2]
90 tp090r.apm.m4 APM AMPL FMCMAP macro-controllable, indetermined solution presented in [2]
91 tp091r.apm.m4 APM AMPL FMCMAP macro-controllable, indetermined solution presented in [2]
92 tp092r.apm.m4 APM AMPL FMCMAP macro-controllable, indetermined solution presented in [2]
93 tp093.apm APM AMPL FMCMAP differs from [1]
94         does not exist
95 tp095.apm APM AMPL FMCMAP  
96 tp096.apm APM AMPL FMCMAP  
97 tp097.apm APM AMPL FMCMAP  
98 tp098.apm APM AMPL FMCMAP  
99 tp099.apm APM AMPL FMCMAP strange definitions in [1]
100 tp100.apm APM AMPL FMCMAP  
101 tp101.apm APM AMPL FMCMAP differs from [1] and [6]
102 tp102.apm APM AMPL FMCMAP  
103 tp103.apm APM AMPL FMCMAP  
104 tp104.apm APM AMPL FMCMAP differs from [1] and [6]
105 tp105.apm APM AMPL FMCMAP better solution found, differs from [1] and [6]
106 tp106.apm APM AMPL FMCMAP  
107 tp107.apm APM AMPL FMCMAP erroneous initialization vector in [2], differs from [1] and [6]
108 tp108r.apm.m4 APM AMPL FMCMAP macro-controllable, indetermined solution presented in [2], differs from [1] and [6]
109 tp109.apm APM AMPL FMCMAP verification required, sign error in [2], differs from [1] and [6]
110 tp110.apm APM AMPL FMCMAP missing bracket in objective function in [2]
111 tp111.apm APM AMPL FMCMAP  
112 tp112.apm APM AMPL FMCMAP verification required, error in equation 3 in [2], improvable solution in [2]
113 tp113.apm APM AMPL FMCMAP  
114 tp114.apm APM AMPL FMCMAP  
115         does not exist
116 tp116.apm APM AMPL FMCMAP differs from [1] and [6]
117-1 tp117r1.apm.m4 APM AMPL FMCMAP macro-controllable, exact formulation of #117r, verification required, differs from [1] and [6]
117-2 tp117r2.apm.m4 APM AMPL FMCMAP macro-controllable, condensed formulation of #117r for human readers, verification required, differs from [1] and [6]
117-3 tp117r3.apm.m4 APM AMPL FMCMAP macro-controllable, benevolent formulation of #117r, verification required
118 tp118.apm APM AMPL FMCMAP  
119 tp119.apm APM AMPL FMCMAP typo in solution in [2]
120 tp120.apm APM AMPL FMCMAP not part of the classic H+S model collection, 3 balls in a spheric cage, benevolent initialization, rcage = 0.1
121 tp121.apm APM AMPL FMCMAP not part of the classic H+S model collection, 3 balls in a spheric cage, traditional initialization, rcage = 0.1
122 tp122.apm APM AMPL FMCMAP not part of the classic H+S model collection, 3 balls in a spheric cage, benevolent initialization, rcage = 1
123 tp123.apm APM AMPL FMCMAP not part of the classic H+S model collection, 3 balls in a spheric cage, traditional initialization, rcage = 1
124 tp124.apm APM AMPL FMCMAP not part of the classic H+S model collection, 3 balls in a spheric cage, benevolent initialization, rcage = 10
125 tp125.apm APM AMPL FMCMAP not part of the classic H+S model collection, 3 balls in a spheric cage, traditional initialization, rcage = 10
126 tp126.apm APM AMPL FMCMAP not part of the classic H+S model collection, all is going to vanish
127 tp127.apm APM AMPL FMCMAP not part of the classic H+S model collection, all is going to vanish
128 tp128.apm APM AMPL FMCMAP not part of the classic H+S model collection, all is going to vanish

Sun, 19 Feb 2017 21:30:08 +0100

Stephan K.H. Seidl