by Stephan K.H. Seidl
Version 7, Thu, 06 Nov 2014 00:08:56 +0100
The classic Hock & Schittkowski model collection  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  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 .
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.
For the full text click revisedhsmodels.pdf
(currently authentication required),
for the change log click Changelog.
Comments, bug reports, and better solutions are welcome.
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.
|||J. D. Hedengren:
APMonitor Documentation: Hock & Schittkowski Models.
|||W. Hock and K. Schittkowski:
Test Examples for Nonlinear Programming Codes.
Vol 187 of Lecture Notes in Economics and Mathematical Systems (Springer, 1981)
Test Examples for Nonlinear Programming Codes:
All Problems from the Hock-Schittkowski-Collection.
An Updated Set of 306 Test Problems for Nonlinear
Programming with Validated Optimal Solutions, User's Guide.
http://www.ai7.uni-bayreuth.de/test_probs_src.zip, file PROB.FOR (2011)
|||R. J. Vanderbei:
AMPL: Nonlinear Optimization Models: Hock & Schittkowski Models.
|||R. J. Vanderbei:
AMPL: Nonlinear Optimization Models: Revised Hock & Schittkowski 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 . Indeed, one should take into account that it is possible that the tarball version here is more recent than the one provided with . 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.
|1||tp001.apm||differs from |
|2||tp002r.apm.m4||macro-controllable, differs from |
|11||tp011.apm||erroneous solution formulæ in |
|14||tp014.apm||differs from |
|15||tp015.apm||differs from |
|16||tp016r.apm.m4||macro-controllable, differs from |
|17||tp017.apm||differs from |
|19||tp019.apm||differs from |
|20||tp020r.apm.m4||macro-controllable, differs from , erroneous solution formulæ in |
|21||tp021.apm||differs from |
|25-1||tp025v1.apm||exact formulation of #25, pretty small gradient at starting point, differs from |
|25-2||tp025v2.apm||some trial without mitigation, source-level scaling applied|
|25-3||tp025v3.apm||poor man's formulation of #25, initialization improved|
|30||tp030.apm||differs from |
|31||tp031.apm||differs from |
|33||tp033r.apm.m4||macro-controllable, differs from |
|34||tp034.apm||differs from |
|36||tp036.apm||differs from |
|41||tp041.apm||differs from |
|42||tp042.apm||differs from |
|45||tp045r.apm.m4||macro-controllable, erroneous initialization vector in |
|46||tp046.apm||not found in , found in |
|47||tp047r.apm.m4||macro-controllable, better solution found|
|49||tp049.apm||differs from |
|54-1||tp054v1.apm||exact formulation of #54, honors on-board scaling, errors in  and |
|54-2||tp054v2.apm||poor man's formulation of #54, source-level mapping applied and more|
|55||tp055r.apm.m4||macro-controllable, differs from  and , error in |
|56||tp056r.apm.m4||macro-controllable, differs from  and |
|57||tp057.apm||differs from  and |
|58||tp058.apm||not found in , found in , differs from |
|59||tp059.apm||verification required, error in |
|65||tp065.apm||differs from  and |
|66||tp066.apm||differs from  and |
|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|
|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 , 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 , 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 |
|71||tp071.apm||differs from |
|72||tp072.apm||differs from |
|77||tp077.apm||erroneous initialization vector in |
|81||tp081.apm||typo in solution in |
|82||does not exist|
|85||tp085.apm||verification required, differs from |
|86||tp086.apm||verification required, differs from  and |
|87-1||tp087r1.apm.m4||macro-controllable, verification required, typo in solution in , better solution found, transition domains, differs from  and |
|87-2||tp087r2.apm.m4||macro-controllable, verification required, typo in solution in , better solution found, MPEC, differs from  and |
|89||tp089r.apm.m4||macro-controllable, indetermined solution presented in |
|90||tp090r.apm.m4||macro-controllable, indetermined solution presented in |
|91||tp091r.apm.m4||macro-controllable, indetermined solution presented in |
|92||tp092r.apm.m4||macro-controllable, indetermined solution presented in |
|93||tp093.apm||differs from |
|94||does not exist|
|99||tp099.apm||strange definitions in |
|101||tp101.apm||differs from  and |
|104||tp104.apm||differs from  and |
|105||tp105.apm||better solution found, differs from  and |
|107||tp107.apm||erroneous initialization vector in , differs from  and |
|108||tp108r.apm.m4||macro-controllable, indetermined solution presented in , differs from  and |
|109||tp109.apm||verification required, sign error in , differs from  and |
|110||tp110.apm||missing bracket in objective function in |
|112||tp112.apm||verification required, error in equation 3 in , improvable solution in |
|115||does not exist|
|116||tp116.apm||differs from  and |
|117-1||tp117r1.apm.m4||macro-controllable, exact formulation of #117r, verification required, differs from  and |
|117-2||tp117r2.apm.m4||macro-controllable, condensed formulation of #117r for human readers, verification required, differs from  and |
|117-3||tp117r3.apm.m4||macro-controllable, benevolent formulation of #117r, verification required|
|119||tp119.apm||typo in solution in |
|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|