Internet Info 1997 December/Internet_Info_CD-ROM_Walnut_Creek_December_1997.iso/faqs/sci/answers/nonlinear-programming-faq

Internet Message Format | 1997-10-05 | 42KB

Path: senator-bedfellow.mit.edu!bloom-beacon.mit.edu!nntprelay.mathworks.com!news.maxwell.syr.edu!newsfeed.acns.nwu.edu!news.acns.nwu.edu!4er
From: [e-mail] (Robert Fourer)
Newsgroups: sci.op-research,sci.answers,news.answers
Subject: Nonlinear Programming FAQ
Followup-To: sci.op-research
Date: 4 Oct 1997 20:20:09 GMT
Organization: Northwestern University, Evanston, IL, US
Lines: 798
Approved: [e-mail]
Distribution: world
Expires: 11/05/97
Message-ID: <6168dp$[e-mail]>
Reply-To: [e-mail] (Robert Fourer)
NNTP-Posting-Host: scherzo.iems.nwu.edu
Summary: A List of Frequently Asked Questions about Nonlinear Programming
Keywords: FAQ, NLP, Nonlinear Programming
Originator: [e-mail]
Xref: senator-bedfellow.mit.edu sci.op-research:8391 sci.answers:7179 news.answers:113858

Posted-By: auto-faq 2.4
Archive-name: nonlinear-programming-faq
Last-modified: October 4, 1997

[ ]

        Nonlinear Programming
        Frequently Asked Questions

Optimization Technology Center of
Northwestern University and Argonne National Laboratory
Posted monthly to Usenet newsgroup sci.op-research

World Wide Web version:
http://www.mcs.anl.gov/home/otc/Guide/faq/nonlinear-programming-faq.html
Plain-text version:
ftp://rtfm.mit.edu/pub/usenet/sci.answers/nonlinear-programming-faq

THIS PLAIN-TEXT VERSION DOES NOT SHOW THE MANY HYPERTEXT LINKS THAT
ARE INCLUDED IN THE WORLD WIDEWEB VERSION.

Date of this version: October 4, 1997

   * Q1. "What is Nonlinear Programming?"
   * Q2. "What software is there for nonlinear optimization?"
   * Q3. "I wrote an optimization code. Where are some test models?"
   * Q4. "What references and Web links are there in this field?"
   * Q5. "How do I access the Netlib server?"
   * Q6. "Who maintains this FAQ list?"

See also the following pages
pertaining to mathematical programming and optimization modeling:

   * The related Linear Programming FAQ.
   * The NEOS Guide to optimization models and software.
   * The Decision Tree for Optimization Software by H.D. Mittelmann and P.
     Spellucci.
   * Jiefeng Xu's List of Interesting Optimization Codes in the Public
     Domain.
   * Software for Optimization: A Buyer's Guide by Robert Fourer.
   * Harvey Greenberg's Mathematical Programming Glossary.

[ ]

Q1. "What is Nonlinear Programming?"

A: A Nonlinear Program (NLP) is a problem that can be put into the form

    minimize   F(x)
    subject to g (x)  = 0     for i=1,...,m1       where m1 >= 0
                i
               h (x) >= 0    for j=m1+1,...,m      where m >= m1
                j

That is, there is one scalar-valued function F, of several variables (x here
is a vector), that we seek to minimize subject (perhaps) to one or more
other such functions that serve to limit or define the values of these
variables. F is called the "objective function", while the various other
functions are called the "constraints". (If maximization is sought, it is
trivial to do so, by multiplying F by -1.)

Because NLP is a difficult field, researchers have identified special cases
for study. A particularly well studied case is the one where all the
constraints g and h are linear. The name for such a problem, unsurprisingly,
is "linearly constrained optimization". If, as well, the objective function
is quadratic at most, this problem is called Quadratic Programming (QP). A
further special case of great importance is where the objective function is
entirely linear; this is called Linear Programming (LP) and is discussed in
a separate FAQ list. Another important special case, called unconstrained
optimization, is where there are no constraints at all.

One of the greatest challenges in NLP is that some problems exhibit "local
optima"; that is, spurious solutions that merely satisfy the requirements on
the derivatives of the functions. Think of a near-sighted mountain climber
in a terrain with multiple peaks, and you'll see the difficulty posed for an
algorithm that tries to move from point to point only by climbing uphill.
Algorithms that propose to overcome this difficulty are termed "Global
Optimization".

The word "Programming" is used here in the sense of "planning"; the
necessary relationship to computer programming was incidental to the choice
of name. Hence the phrase "NLP program" to refer to a piece of software is
not a redundancy, although I tend to use the term "code" instead of
"program" to avoid the possible ambiguity.

[ ]

Q2. "What software is there for nonlinear optimization?"

A: It's unrealistic to expect to find one general NLP code that's going to
work for every kind of nonlinear model. Instead, you should try to select a
code that fits the problem you are solving. If your problem doesn't fit in
any category except "general", or if you insist on a globally optimal
solution (except when there is no chance of encountering multiple local
optima), you should be prepared to have to use a method that boils down to
exhaustive search, i.e., you have an intractable problem.

If you simply want to try solving a particular model, consider the
Optimization Technology Center at http://www.mcs.anl.gov/home/otc/otc.html.
The centerpiece of this ambitious project is NEOS, the Network-Enhanced
Optimization System, consisting of a library of optimization software, a
facility to use this library over the network at
http://www.mcs.anl.gov/home/otc/Server/neos.html, and a guide to more
information about the software packages. Linear and nonlinear models are
covered. Capabilities and access modes are still being enhanced - this is an
ongoing process.

Several of the commercial LP codes referenced in the LP FAQ have specialized
routines, particularly QP. The ones that I know of that have some form of QP
are: LINDO, KORBX, LOQO, MPS-III, OSL, and PC-PROG. Of course, you don't
generally get source code when you license one of these products; but many
of them can be licensed as a callable library of solver routines. Many
general nonlinear problems can be solved (or at least confronted) by
application of a sequence of LP or QP approximations.

There are ACM TOMS routines for QP, #559 and #587, available in
ftp://netlib2.cs.utk.edu/toms/559 and ftp://netlib2.cs.utk.edu/toms/587

There is a directory on Netlib, ftp://netlib2.cs.utk.edu/opt, containing a
collection of optimization routines. The last time I checked, I saw

   * "praxis" (unconstrained optimization, without requiring derivatives)
   * "tn" (Newton method for unconstrained or simple-bound optimization)
   * "ve08" (optimization of unconstrained separable function).
   * "simann" (unconstrained optimization using Simulated Annealing)
   * "subplex"(unconstrained optimization, general multivariate functions)
   * "donlp2" (differentiable nonlinear optimization, dense linear algebra)
   * "hooke" (Hooke and Jeeves method)

A newer version of the "donlp2" code, mentioned above, can be found at
ftp://plato.la.asu.edu/pub/donlp2. This is P. Spellucci's implementation of
a SQP method for general nonlinear optimization problems including nonlinear
equality and inequality constraints (generally referred to as the NLP
problem). It is freely available for non-commercial and research use, and
includes a number of nontrivial examples. There are four versions:

   * donlp2.tar.gz, donlp2_d.tar.gz (f77, exact & numerical gradients
     respectively)
   * donlp2_c.tar.gz, donlp2_d_c.tar.gz (f2c-converted C-versions of the
     above)

A package for large optimization problems (with only simple bounds for
constraints), L-BFGS-B, implements a limited memory BFGS algorithm. The user
must supply the gradient g of f, but knowledge about the Hessian matrix is
not required. This program is an extension of algorithm L-BFGS (Harwell
routine VA15) which can handle only unconstrained problems. Both codes can
be obtained via anonymous ftp at ftp://eecs.nwu.edu/pub/lbfgs and
ftp://eecs.nwu.edu/pub/lbfgs.unc.

A package called conmin (unrelated to the one by Vanderplaats and
Associates), is available at or
ftp://anusf.anu.edu.au/mld900/constr_minimum. Any comments should be sent to
Murray Dow at [e-mail]. The author states that it is reliable
but not state of the art; surpassed, for instance, by FSQP.

Will Naylor ([e-mail]) has a collection of software he calls
WNLIB. Routines of interest include
- unconstrained non-linear optimization routines: implementation of
conjugate-gradient and conjugate-directions algorithms.
- constrained non-linear optimization routines: based on conjugate-gradient
algorithm with penalties.
- simplex method for linear programming: contains anti-cycling and numerical
stability hacks. No optimization for sparse matrix.
- transportation problem/assignment problem routine: optimization for sparse
matrix.
- general simulated annealing routine
These routines can be obtained by anonymous ftp from
ftp://ftp.rahul.net/pub/spiketech/softlib/wnlib/.

NSWC Library of Mathematical Subroutines has a subroutine to minimize a
function of n variables (OPTF) and a subroutine to solve a system of
nonlinear equations (HBRD). Such routines are also available in NMS library
[Kahaner].

SolvOpt, by Alexei Kuntsevich ([e-mail]) and Franz Kappel
([e-mail]), is designed for local optimization of
nonsmooth nonlinear problems. Free source code is available in C and
Fortran, and also as M-functions for use with MATLAB. Further information is
provided by a manual that is also available for downloading.

For nonlinear optimization problems with both continuous and binary
variables (MINLP), there is a code called DICOPT++, available commercially
from GAMS Development Corp. Contact [e-mail] for more information.
(There is a survey article, "Constrained Nonllinear 0-1 Programming" by
Hansen, Jaumard, and Mathon, in the ORSA Journal on Computing, 5, 2, Spring
1993.)

While they are not NLP solvers, per se, attention should be given to
modeling languages like GAMS, AIMMS and AMPL. See the Linear Programming FAQ
for details on contacting the vendors of these and other modeling language
products.

Microsoft Excel 4.0 and above has a function called "Solver", based on GRG2.
This product runs on PC and Macintoshes. The attraction of this approach is
that models can be built using the spreadsheet. I am told that this function
can handle 200 independent variables and 500 constraints. Quattro also has a
solver based on GRG2.

A package that uses Microsoft Excel as its input mechanism is Magestic, a
non-linear least squares minimization program. You can contact the vendor
at: Logix Consulting, Inc., 11408 Audelia, Ste 4944, Dallas, TX 752431,
1-800-900-5541 or 214-918-0700.

O-Matrix for Windows includes several non-linear optimization tools. You can
contact the vendor at: Harmonic Software Inc., 12223 Dayton Avenue North,
Seattle WA 98133, 1-800-895-4546, 206-367-8742.

Information for obtaining ACCPM, which implements an analytic center cutting
plane method for convex optimization problems, is available at
http://ecolu-info.unige.ch/~logilab/software/accpm.html.

Semidefinite Programming is a generalization of linear programming to the
space of block diagonal, symmetric, positive semidefinite matrices. Interest
in this topic, which has numerous engineering applications, has been greatly
stimulated by the extension of interior-point methods from linear
programming to the semidefinite case. Several groups of researchers are
developing interior-point codes, such as:

   * CSDP, a subroutine library available in C or Fortran source.
   * SDPpack, a package of Matlab files currently in version 0.8 beta.
   * SDPSOL, a parser/solver for semidefinite programming and related
     determinant maximization problems with matrix structure.
   * SDPT3, a Matlab package.

See the semidefinite programming home pages maintained by Farid Alizadeh and
Christoph Helmberg for links and further information.

An extensive index of information on Global Optimization is maintained by
Arnold Neumaier of the Computational Mathematics group at the University of
Vienna. The following are a few of the codes available in this area:

   * BARON consists of a "core" module for global nonlinear optimization in
     continuous and/or discrete variables, and a variety of specialized
     modules for such problems as bilinear programming, fixed-charge
     programming, indefinite quadratic programming, linear multiplicative
     programming, and univariate polynomial programming. Information is
     available from Nick Sahinidis, [e-mail].

   * A software package for solving structured global optimization problems,
     cGOP, is available by ftp from the Computer-Aided Systems Laboratory at
     Princeton University. It implements a primal-dual decomposition
     algorithm applicable to general constrained biconvex problems, using a
     set of C subroutines to solve these problems via decomposition and
     branch-and-bound techniques; version 1.1 has been updated to use CPLEX
     4.0 and MINOS 5.4 as the solvers for various linear and convex
     subproblems. For assistance, write to [e-mail].

   * Fortran source code for global minimization using a stochastic
     integration algorithm (TOMS 667), is obtainable at
     http://www.netlib.org/toms/667.

   * LGO integrates several global and local optimization solvers, which can
     be activated by the user in interactive or automatic execution modes.
     The PC version is embedded under a menu-driven interface.

The following products are said to do some nonlinear optimization, but don't
fall into any of the usual categories:

   * UniCalc, for "arbitrary algebraic systems of equations and
     inequalities," has been developed at the Russian Research Institute of
     Artificial Intelligence, [e-mail].

   * Fortran Calculus is a programming front end to a variety of nonlinear
     problem solvers, available from Optimal Designs,
     [e-mail].

For difficult problems like Global Optimization, methods like Genetic
Algorithms and Simulated Annealing have been studied heavily. I'm not
well-versed in any of these topics, and I have been assured of contradictory
things by different experts. A particular point of controversy is whether
there is a proof of optimality for practical variants of such algorithms for
Global Optimization problems, and I take no particular stand on the issue
(since for difficult problems such a proof may be of academic interest
only). Even moreso than usual, I say "let the user beware" when it comes to
code. There's a (compressed) Postscript file available at
ftp://ftp.cs.colostate.edu/pub/TechReports/1993/tr-103.ps.Z, containing a
forty-page introduction to the topic of GA. The Usenet newsgroup on GA,
comp.ai.genetic, has a FAQ on the topic, otherwise known as "The
Hitch-Hiker's Guide to Evolutionary Computation", available at
ftp://rtfm.mit.edu/pub/usenet/news.answers/ai-faq/genetic. Genetic Algorithm
code can be obtained at ftp://cs.ucsd.edu/pub/GAucsd. A commercial
organization, New Light Industries, Ltd. offers a "Genetic Algorithm Solver
for Excel" they call GENERATOR; their email address is [e-mail].
Simulated Annealing code for NLP and other problems is available at
http://www.ingber.com/ (or ftp.ingber.com) -- contact Lester Ingber
([e-mail]) for more info. A code called SDSC EBSA (Ensemble
Based Simulated Annealing) is available at
ftp://ftp.sdsc.edu/pub/sdsc/math/Ebsa, or contact Richard Frost
([e-mail]). And there is the simann code available on Netlib,
mentioned above. For other ideas on Global Optimization, you may want to
consult one of the books given in the section on references , such as
[Nemhauser] or one of the ones with "Global" in its title. There is also the
Journal of Global Optimization, published by Kluwer.

Another technique that should be considered is "Constraint Programming"
(sometimes embedded in Prolog-like languages to form "Constraint Logic
Programming"). There is a Usenet newsgroup, comp.constraints, devoted to the
topic. A WWW page exists at
http://www.cs.city.ac.uk/archive/constraints/constraints.html. Or you can
access the FAQ at //ftp.cs.city.ac.uk/pub/constraints/constraints-faq. The
maintainer of that FAQ, Michael Jampel ([e-mail]), suggests CLP
is best suited for small problems that don't fit typical OR categories (LP,
QP, etc.),

   * "especially if there is indeterminism / incompleteness. Also, if you
     wish to mix numeric with non-numeric domains.... Also, if you need to
     do a lot of encoding of your problem to get it to fit into the OR
     technique; it may be better to use a relatively slow CSP technique on
     10 variables rather than a super-fast OR technique on 2^10 variables."

In the following table is a condensed version of a survey of NLP software
published in the April 1995 issue of " OR/MS Today", a publication of
INFORMS. For further information I would suggest you read the full article.
Several of the software vendors listed in the survey offer multiple
products, in keeping with the conventional wisdom that no one algorithm will
be best for all NLP models. Hence I have grouped the solver products by
vendor, rather than listing them alphabetically by product name. Since the
information won't fit on one line, I've broken the SOLVERS part of the table
into two pieces.

Key to Methods:
  SQP = Successive Quadratic Programming
  SLP = Successive Linear Programming
  GRG = Generalized Reduced Gradient

SOLVERS:

Vendor                   Phone         Email or URL
---------------------    ------------  ----------------------------------
Aptech Systems           206-432-7855  [e-mail]
ARKI Consult & Dvlpmt [phone]  [e-mail]
Boeing Comp Svc          206-865-3298
ILOG                     415-390-9000  [e-mail]
INRIA                  [phone]
LINDO Systems            312-988-7422  [e-mail]
The Mathworks            508-653-1415  [e-mail]
Numerical Alg Group      708-971-2337
Numerical Opt Ctr     [phone]
Optimal Methods          512-471-9433
Rutherford Lab        [phone]  [e-mail]
SAITECH                  908-264-4700
Prof. K. Schittkowski [phone]  [e-mail]
Stanford Bus Soft        415-962-8719
Prof. A.L. Tits          301-405-3669  [e-mail]
VMA Eng                  719-473-4611
Visual Num.              713-784-3131  [e-mail]

Vendor          Product                  Method
--------------  -----------------------  ------------------------
Aptech          Constr. Max. Likelihood  SQP
                Constr. Optimization     SQP
ARKI            CONOPT                   GRG
Boeing          SPRNLP                   SQP
ILOG            Numerica                 Constraint-based global search
INRIA           Direct Opt. Control      SQP
LINDO Systems   LINGO                    GRG
Mathworks       MATLAB NAG Toolbox       various
                MATLAB Opt. Toolbox      various
NAG             NAG Libraries            various
Num Opt Ctr     OPTIMA                   SQP
Opt. Methods    GRG2                     GRG
                INTPT                    Interior point
                SLP                      SLP
                SQP                      SQP
Rutherford Lab  LANCELOT                 Trust region / aug. lagrangian
SAITECH         SOPT                     SQP / Interior point
K. Schittkowski DFNLP                    Newton methods
                NLPQL                    SQP
Stan Bus Soft   LSSOL                    Active set method
                MINOS                    Reduced gradient
                NPSOL                    SQP
A.L. Tits       FFSQP/CFSQP              SQP
VMA Eng         DOC/DOT                  various
Visual Num      IMSL                     various

MODELING PRODUCTS AND OTHERS:
Product Name       H/W       Phone        Email address or URL
------------       --------- ------------ --------------------
AIMMS              PC3     [phone] [e-mail]
                                          http://www.paragon.nl/
AMPL               PC3 ^     702-322-7600 [e-mail]
                                          http://www.ampl.com/ampl/
CUTE               PC ^     [phone] [e-mail]
                                          http://www.rl.ac.uk/departments/ccd/numerical/cute/cute.html
GAMS               PC2 ^     415-583-8840 [e-mail]
                                          http://www.gams.com/
What's Best!       PC/Mac/WS 800-441-2378 [e-mail]
                                          http://www.lindo.com/

Here is a summary of other NLP codes mentioned in newsgroups in the past few
years (or, further information on the ones in the above table), sorted
alphabetically. Perhaps someone will volunteer to organize these references
more usefully.

   * Amoeba - Numerical Recipes
   * Brent's Method - Numerical Recipes
   * CO/CML - Applications written in GAUSS language, general constrained
     optimization and constrained maximum likelihood estimation using SQP.
     CML includes statistical inference (also Bayesian, bootstrap) for
     constrained parameters. Postscript file descriptions via
     ftp://ftp.u.washington.edu/public/rons. Contact [e-mail], or
     call [phone].
   * CONMAX - Fortran program for solving nonlinearly constrained problems
     of the form:
        o Choose x1,...,xn to minimize w subject to
        o abs(fi - gi(x1,...,xn)) .LE. w, 1 .LE. i .LE. m1
        o gi(x1,...,xn) .LE. w, m1 + 1 .LE. i .LE. m2
        o gi(x1,...,xn) .LE. 0, m2 + 1 .LE. i .LE. m3
     where the fi are given real numbers, and the gi are given smooth
     functions. Constraints of the form gi(x1,...,xn) = 0 can also be
     handled. Each iteration of our algorithm involves approximately solving
     a certain nonlinear system of first order ordinary differential
     equations to get a search direction. The program and its extensive
     user's guide can be obtained from the opt folder of netlib.
   * CONMIN - Vanderplaats, Miura & Associates, Colorado Springs, Colorado,
     719-527-2691.
   * CONOPT - Large-scale GRG code, by Arne Drud. Available with GAMS,
     AIMMS, AMPL, LINGO, and What's Best (modeling languages - see LP FAQ)
     and as a standalone subroutine library. Phone [phone], e-mail
     [e-mail]
   * DFPMIN - Numerical Recipes (Davidon-Fletcher-Powell)
   * Eureka - Borland Software (for IBM PC class of machines)
   * FFSQP/CFSQP (Fortran/C) - Contact Andre Tits, [e-mail]. Free
     of charge to academic users. Solves general nonlinear constrained
     problems, including constrained minimax problems. CFSQP (C code)
     includes a scheme to efficently handle problems with many constraints
     (e.g., discretized semi-infinite problems). Interface to AMPL.
   * GENOCOP - Solves linearly constrained problems via a Genetic algorithm,
     available at ftp://unccsun.uncc.edu. Author: Zbigniew Michalewicz,
     [e-mail].
   * Harwell Library routines
        o VF01: based on R. Fletcher algorithm
        o VF02: based on M. Powell alogorithm
        o VF03: using "watchdog techniques" for line search. An improved
          version of VF02.
        o VF04: Automatically calculate 1st order derivatives, VF03 ia
          required to provide the derivatives.
   * Hooke and Jeeves algorithm - see reference below. A version is
     available at ftp://netlib2.cs.utk.edu/opt/hooke.c, and may be useful
     because it handles nondifferentiable and/or discontinuous functions.
   * LANCELOT - large-scale NLP. See the book by Conn et al. in the
     references section. For peaceful purposes only. For information on
     licensing this package, see the email addresses for Conn, Toint, or
     Gould, in the entry for CUTE,
   * LSSOL - Stanford Business Software Inc. (See MINOS) This code does
     convex (positive semi-definite) QP. Is the QP solver used in current
     versions of NPSOL.
   * MATLAB Optimization Toolbox - The Mathworks, Inc. 508-653-1415. Handles
     various nonlinear optimization problems. Data sheet available in
     postscript format at
     ftp://ftp.mathworks.com/pub/product-info/optimization.ps Email address:
     [e-mail] .
   * MINOS - Stanford Business Software Inc., 415-962-8719. Mailing address:
     2672 Bayshore Parkway, Suite 304, Mountain View, CA 94043. Email:
     [e-mail]. This large-scale code is often used by
     researchers as a "benchmark" for others to compare with.
   * MINPACK I and II - Contact Jorge More', [e-mail], or check
     ftp://netlib2.cs.utk.edu/minpack. Solves dense nonlinear least-squares
     problems.
   * Nelder and Mead's method - Numerical Recipes, also Barabino.
   * NOVA - DOT Products, Houston TX
   * QLD - Contact: [e-mail]. Solves Quadratic
     Programming and other nonlinear problems.
   * QPSOL - see LSSOL.
   * SLATEC - Quadratic solvers dbocls, dlsei, and other routines. National
     Energy Software Center, 9700 Cass Ave., Argonne, Illinois 60439. Also
     available at ftp://netlib2.cs.utk.edu/slatec

An extremely useful book is the Optimization Software Guide, by Jorge More'
and Stephen Wright, from SIAM Books. Call 1-800-447-7426 to order ($24.50,
less ten percent if you are a SIAM member). It contains references to 75
available software packages, and goes into more detail than is possible in
this FAQ. A Web version is available, at least the parts that give info on
actual software packages, in URL
http://www.mcs.anl.gov/home/otc/Guide/SoftwareGuide.

I would be interested in hearing of people's experiences with the codes they
learn about from reading this FAQ. (Note, I'm looking for more-or-less
independent confirmation or denial of the practicality of codes.)

[ ]

Q3. "I wrote an optimization code. Where are some test models?"

A: There are various test sets for NLP. Among those I've seen mentioned are:

   * A. Corana et al, "Minimizing Multimodal Functions of Continuous
     Variables with the Simulated Annealing Algorithm," ACM Transactions on
     Mathematical Software, Vol. 13, No. 3, Sept 1987, pp. 262-280.
     (Difficult unconstrained nonlinear models)
   * C.A. Floudas and P.M. Pardalos, A Collection of Test Problems for
     Constrained Global Optimization Algorithms, Springer-Verlag, Lecture
     Notes in Computer Science 455 (1990).
   * W.W. Hager, P.M. Pardalos, I.M. Roussos, and H.D. Sahinoglou, Active
     Constraints, Indefinite Quadratic Programming, and Test Problems,
     Journal of Optimization Theory and Applications Vol. 68, No. 3 (1991),
     pp. 499-511.
   * J. Hasselberg, P.M. Pardalos and G. Vairaktarakis, Test case generators
     and computational results for the maximum clique problem, Journal of
     Global Optimization 3 (1993), pp. 463-482.
   * B. Khoury, P.M. Pardalos and D.-Z. Du, A test problem generator for the
     steiner problem in graphs, ACM Transactions on Mathematical Software,
     Vol. 19, No. 4 (1993), pp. 509-522.
   * Y. Li and P.M. Pardalos, Generating quadratic assignment test problems
     with known optimal permutations, Computational Optimization and
     Applications Vol. 1, No. 2 (1992), pp. 163-184.
   * P. Pardalos, "Generation of Large-Scale Quadratic Programs", ACM
     Transactions on Mathematical Software, Vol. 13, No. 2, p. 133.
   * P.M. Pardalos, Construction of test problems in quadratic bivalent
     programming, ACM Transactions on Mathematical Software, Vol. 17, No. 1
     (1991), pp. 74-87.
   * P.M. Pardalos, Generation of large-scale quadratic programs for use as
     global optimization test problems, ACM Transactions on Mathematical
     Software, Vol. 13, No. 2 (1987), pp. 133-137.
   * F. Schoen, "A Wide Class of Test Functions for Global Optimization", J.
     of Global Optimization, 3, 133-137, 1993, with C source code available
     at ftp://ghost.dsi.unimi.it/pub/schoen.
   * publications (referenced in another section of this list) by
     Schittkowski; Hock & Schittkowski; Torn & Zilinskas.

Some of the other publications listed in the references section also may
contain problems that you could use to test a code.

A package called CUTE (Constrained and Unconstrained Testing Environment) is
a set of Fortran subroutines, system tools and test problems in the area of
nonlinear optimization and nonlinear equations, available at
ftp://joyous-gard.cc.rl.ac.uk/pub/cute. or at
ftp://thales.math.fundp.ac.be/cute. A LaTex formatted manuscript is included
in the distribution file. Download the README file first and follow the
directions contained therein. Questions should be directed toward any of the
package's authors:

   * Ingrid Bongartz [e-mail]
   * Andy Conn [e-mail]
   * Nick Gould [e-mail]
   * Philippe Toint [e-mail]

John Beasley has posted information on his OR-Lib, which contains various
optimization test problems. Send e-mail to [e-mail] to
get started. Or have a look in the Journal of the Operational Research
Society, Volume 41, Number 11, Pages 1069-72. Available at
ftp://mscmga.ms.ic.ac.uk/pub. The only nonlinear models in this collection
at this writing are Quadratic Assignment problems.

A collection of Global Optimization problems resides at
ftp://fourier.ee.ucla.edu/pub. In this directory, reverse.zip
(reverse.tar.Z) and concave.zip (concave.tar.Z) contain a collection of test
problems for linear reverse convex programs, known as LRCP and concave
minimization problems. For further details, see the README file in the
directory, or contact Khosrow Moshirvaziri at [e-mail].

Fortran source code of global optimization test problems (1-10 dimensional)
are at the end of TOMS 667 fortran code, obtainable at
http://www.netlib.org/toms/667.

The paper "An evaluation of the Sniffer Global Optimization Algorithm Using
Standard Test Functions", Roger A.R. Butler and Edward E. Slaminka, J. Comp.
Physics, 99, 28-32, (1992) mentions the following reference containing 7
functions that were intended to thwart global minimization algorithms:
"Towards Global Optimization 2", L.C.W. Dixon and G.P. Szego, North-Holland,
1978. [from Dean Schulze - [e-mail]]

The modeling language GAMS comes with about 150 test models, which you might
be able to test your code with. The models are in the public domain
according to the vendor, although you need access to a GAMS system if you
want to run them without modifying the files. The modeling system AIMMS also
comes with a number of test models.

In the journal Mathematical Programming, Volume 61 (1993) Number 2, there is
an article by Calamai et al. that discusses how to generate QP test models.
It gives what seems a very full bibliography of earlier articles on this
topic. The author offers at the end of the article to send a Fortran code
that generates QP models, if you send email to [e-mail],
or use anonymous ftp at ftp://dial.uwaterloo.ca/pub/phcalamai/math_prog in
file genqp.code.tar.Z.

Hans D. Mittelmann and P. Spellucci have prepared a test environment of over
400 unconstrained and constrained nonlinear optimization problems, plus code
to facilitate interfacing solvers to them. This material is available as a
tar file from ftp://plato.la.asu.edu/pub/donlp2/testenviron.tar.gz.

[ ]

Q4. "What references are there in this field?"

A: What follows here is an idiosyncratic list, a few books that I like, or
have been recommended on the net, or are recent. I have *not* reviewed them
all.

General reference

   * Nemhauser, Rinnooy Kan, & Todd, eds, Optimization, North-Holland, 1989.
     (Very broad-reaching, with large bibliography. Good reference; it's the
     place I tend to look first. Expensive, and tough reading for
     beginners.)
   * Harvey Greenberg has compiled an on-line Mathematical Programming
     Glossary.

Other publications (can someone help classify these more usefully?)

   * Barabino, et al, "A Study on the Performances of Simplex Methods for
     Function Minimization," 1980 Proceedings of the IEEE International
     Conference on Circuits and Computers, (ICCC 1980), pp. 1150-1153.
   * Bazaraa, Shetty, & Sherali, Nonlinear Programming, Theory &
     Applications, Wiley, 1994.
   * Bertsekas, Dimitri P., Dynamic Programming and Optimal Control.
     Belmont, MA: Athena Scientific, 1995.
   * Bertsekas, Dimitri P., Nonlinear Programming. Belmont, MA: Athena
     Scientific, 1995.
   * Borchers & Mitchell, "An Improved Branch and Bound Algorithm for Mixed
     Integer Nonlinear Programs", Computers and Operations Research, Vol 21,
     No. 4, p 359-367, 1994.
   * Coleman & Li, Large Scale Numerical Optimization, SIAM Books.
   * Conn, A.R., et al., "LANCELOT: a Fortran Package for Large-Scale
     Nonlinear Optimization", Springer Series in Computational Mathematics,
     vol. 17, 1992.
   * Dennis & Schnabel, Numerical Methods for Unconstrained Optimization and
     Nonlinear Equations, Prentice Hall, 1983.
   * Du and Pardalos (eds.), Minimax and applications, Kluwer, 1995.
   * Du and Sun (eds.), Advances in Optimization and Approximation, Kluwer,
     1994.
   * Fiacco & McCormick, Sequential Unconstrained Minimization Techniques,
     SIAM Books. (An old standby, given new life by the interior point LP
     methods.)
   * Fletcher, R., Practical Methods of Optimization, Wiley, 1987. (Good
     reference for Quadratic Programming, among other things.)
   * Floudas & Pardalos, Recent Advances in Global Optimization, Princeton
     University Press, 1992.
   * Gill, Murray & Wright, Practical Optimization, Academic Press, 1981.
     (An instant NLP classic when it was published.)
   * Himmelblau, Applied Nonlinear Programming, McGraw-Hill, 1972. (Contains
     some famous test problems.)
   * Hock & Schittkowski, Test Examples for Nonlinear Programming Codes,
     Springer-Verlag, 1981.
   * Hooke & Jeeves, "Direct Search Solution of Numerical and Statistical
     Problems", Journal of the ACM, Vol.8 pp. 212-229, April 1961.
   * Horst and Pardalos (eds.), Handbook of Global Optimization, Kluwer,
     1995.
   * Horst, Pardalos, and Thoai, Introduction to global optimization,
     Kluwer, 1995.
   * Horst and Tuy, Global Optimization, Springer-Verlag, 1993.
   * Kahaner, Moler & Nash, Numerical Methods and Software, Prentice- Hall.
   * Lau, H.T., A Numerical Library in C for Scientists and Engineers ,
     1994, CRC Press. (Contains a section on optimization.)
   * Luenberger, Introduction to Linear and Nonlinear Programming, Addison
     Wesley, 1984. (Updated version of an old standby.)
   * More', "Numerical Solution of Bound Constrained Problems", in
     Computational Techniques & Applications, CTAC-87, Noye & Fletcher, eds,
     North-Holland, 29-37, 1988.
   * More' & Toraldo, Algorithms for Bound Constrained Quadratic Programming
     Problems, Numerische Mathematik 55, 377-400, 1989.
   * More' & Wright, "Optimization Software Guide", SIAM, 1993.
   * Nash, S., and Sofer, A., Linear and Nonlinear Programming, McGraw-Hill,
     1996.
   * Nocedal, J., summary of algorithms for unconstrained optimization in
     "Acta Numerica 1992".
   * Pardalos & Wolkowicz, eds., Quadratic Assignment and Related Problems,
     American Mathematical Society, DIMACS series in discrete mathematics,
     1994.
   * Powell, M.J.D., "A Fast Algorithm for Nonlinearly Constrained
     Optimization Calculations", Springer-Verlag Lecture Notes in
     Mathematics, vol. 630, pp. 144-157. (Implemented in the Harwell
     Library)
   * Press, Flannery, Teukolsky & Vetterling, Numerical Recipes, Cambridge,
     1986.
   * Schittkowski, Nonlinear Programming Codes, Springer-Verlag, 1980.
   * Schittkowski, More Test Examples for Nonlinear Programming Codes,
     Lecture Notes in Economics and Math. Systems 282, Springer 1987.
   * Torn & Zilinskas, Global Optimization, Springer-Verlag, 1989.
   * Wismer & Chattergy, Introduction to Nonlinear Optimization,
     North-Holland, 1978. (Undergrad text)
   * Wright, M., "Interior methods for constrained optimization", Acta
     Mathematica, Cambridge University Press, 1992. (Survey article.)
   * Wright, M., "Direct Search Methods: Once Scorned, Now Respectable"

Simulated Annealing & Genetic Algorithms

   * Davis, L. (ed.), Genetic Algorithms and Simulated Annealing, Morgan
     Kaufmann, 1989.
   * De Jong, "Genetic algorithms are NOT function optimizers" in
     Foundations of Genetic Algorithms: Proceedings 24-29 July 1992, D.
     Whitley (ed.) Morgan Kaufman
   * Goldberg, D., "Genetic Algorithms in Search, Optimization, and Machine
     Learning", Addison-Wesley, 1989.
   * Ingber "Very fast simulated re-annealing" Mathematical and Computer
     Modeling, 12(8) 1989, 967-973
   * Kirkpatrick, Gelatt & Vecchi, Optimization by Simulated Annealing,
     Science, 220 (4598) 671-680, 1983.
   * Michalewicz et al., article in volume 3(4) 1991 of the ORSA Journal on
     Computing.
   * Michalewicz, Z., "Genetic Algorithms + Data Structures = Evolution
     Programs", Springer Verlag, 1992.
   * Reeves, C.R., ed., Modern Heuristic Techniques for Combinatorial
     Problems, Halsted Press (Wiley). (Contains chapters on tabu search,
     simulated annealing, genetic algorithms, neural nets, and Lagrangean
     relaxation.)

On-Line Sources of Papers and Bibliographies

   * Michael Trick's Operations Research Page at http://mat.gsia.cmu.edu/
   * Optimization Technology Center at
     http://www.mcs.anl.gov/home/otc/otc.html. Home of NEOS, Network-Enabled
     Optimization System.
   * WORMS (World-Wide-Web for Operations Research and Management Science)
     at http://www.maths.mu.oz.au/~worms/
   * List of interesting optimization codes in public domain at
     http://ucsu.colorado.edu/~xu/software.html. Includes many of the codes
     listed here, plus others of interest for specific problem classes.
   * Mathematical Optimization page at Oak Ridge.
   * Computational Mathematics Archive (London and South East Centre for
     High Performance Computing)
     http://www.lpac.ac.uk/SEL-HPC/Articles/GeneratedHtml/math.opt.html
   * Hans Mittelmann and P. Spellucci have put together an html-based
     Decision Tree for Optimization Software. There is also a plain-text
     version available by FTP, at ftp://plato.la.asu.edu/pub/guide.txt.
   * A Global Optimization web page is at
     http://solon.cma.univie.ac.at/~neum/glopt.html.
   * A survey of the Quadratic Assignment Problem can be found at
     ftp://orion.uwaterloo.ca/pub/henry/qap.
   * A listing of people or places involved with global optimization is
     maintained by Simon Streltsov and can be found at http://cad.bu.edu/go/
   * The Journal of Nonlinear Science has an electronic adjunct called
     Nonlinear Science Today.
   * INFORMS home page.
   * IMPS Consortium

[ ]

Q5. "How do I access the Netlib server?"

A: If you have FTP access, you can try "ftp netlib2.cs.utk.edu", using
"anonymous" as the Name, and your email address as the Password. Do a "cd
(dir)" where (dir) is whatever directory was mentioned, and look around,
then do a "get (filename)" on anything that seems interesting. There often
will be a "README" file, which you would want to look at first. Another FTP
site is netlib.bell-labs.com although you will first need to do "cd netlib"
before you can cd to the (dir) you are interested in. Alternatively, you can
reach an e-mail server via "[e-mail]", to which you can send a
message saying "send index from (dir)"; follow the instructions you receive.
This is the list of sites mirroring the netlib repository:

   * Norway [e-mail]
   * England [e-mail]
   * Germany [e-mail]
   * Taiwan [e-mail]
   * Australia [e-mail]

For those who have WWW (Mosaic, etc.) access, one can access Netlib via the
URL http://www.netlib.org. Also, there is, for X window users, a utility
called xnetlib that is available at ftp://netlib2.cs.utk.edu/xnetlib (look
at the "readme" file first).

[ ]

Q6. "Who maintains this FAQ list?"

A: This list was established by John W. Gregory ([e-mail]), and
is currently being maintained by Robert Fourer ([e-mail]) and the
Optimization Technology Center.

This article is Copyright 1997 by Robert Fourer and John W. Gregory. It may
be freely redistributed in its entirety provided that this copyright notice
is not removed. It may not be sold for profit or incorporated in commercial
documents without the written permission of the copyright holder. Permission
is expressly granted for this document to be made available for file
transfer from installations offering unrestricted anonymous file transfer on
the Internet.

The material in this document does not reflect any official position taken
by any organization. While all information in this article is believed to be
correct at the time of writing, it is provided "as is" with no warranty
implied.

If you wish to cite this FAQ formally (hey, someone actually asked for
this), you may use:

     Fourer, Robert ([e-mail]) and Gregory, John W.
     ([e-mail]), "Linear Programming FAQ" (1997). World
     Wide Web http://www.mcs.anl.gov/home/otc/
     faq/nonlinear-programming-faq.html, Usenet sci.answers, anonymous
     FTP /pub/usenet/sci.answers/ nonlinear-programming-faq from
     rtfm.mit.edu.

There's a mail server on rtfm.mit.edu, so if you don't have FTP privileges,
you can send an e-mail message to [e-mail] containing:

    send usenet/sci.answers/nonlinear-programming-faq

as the body of the message to receive the latest version (it is posted on
the first working day of each month). This FAQ is cross-posted to
news.answers and sci.op-research.

Suggestions, corrections, topics you'd like to see covered, and additional
material are all solicited. Send email to [e-mail].

[ ]

END nonlinear-programming-faq