home *** CD-ROM | disk | FTP | other *** search
- Path: senator-bedfellow.mit.edu!bloom-beacon.mit.edu!hecate.umd.edu!haven.umd.edu!news5.digex.net!digex!news2.digex.net!digex!lynx.unm.edu!jobone!newsxfer3.itd.umich.edu!news2.chicago.iagnet.net!iagnet.net!129.188.136.101!ftpbox.mot.com!newsfeed.acns.nwu.edu!news.acns.nwu.edu!4er
- From: 4er@iems.nwu.edu (Robert Fourer)
- Newsgroups: sci.op-research,sci.answers,news.answers
- Subject: Nonlinear Programming FAQ
- Followup-To: sci.op-research
- Date: 1 Dec 1997 19:18:16 GMT
- Organization: Northwestern University, Evanston, IL, US
- Lines: 788
- Approved: news-answers-request@MIT.Edu
- Distribution: world
- Expires: 01/02/98
- Message-ID: <65v2ho$5oj@news.acns.nwu.edu>
- Reply-To: 4er@iems.nwu.edu (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: 4er@scherzo.iems.nwu.edu
- Xref: senator-bedfellow.mit.edu sci.op-research:8635 sci.answers:7452 news.answers:117966
-
- Posted-By: auto-faq 2.4
- Archive-name: nonlinear-programming-faq
- Last-modified: December 1, 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
-
- Date of this version: December 1, 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 gi(x) = 0 for i = 1, ..., m1 where m1 >= 0
- hj(x) >= 0 for j = m1+1, ..., m where m >= m1
-
- 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 m.dow@anusf.anu.edu.au. The author states that it is reliable
- but not state of the art; surpassed, for instance, by FSQP.
-
- Will Naylor (naylor@synopsys.com) 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 (alex@bedvgm.kfunigraz.ac.at) and Franz Kappel
- (franz.kappel@kfunigraz.ac.at), 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 gams@gams.com 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, nikos@uiuc.edu.
-
- * 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 cgop@titan.princeton.edu.
-
- * 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, narin@artint.msk.su.
-
- * Fortran Calculus is a programming front end to a variety of nonlinear
- problem solvers, available from Optimal Designs,
- OptimalDesigns@awaiter.com.
-
- 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 nli@comtch.iea.com.
- Simulated Annealing code for NLP and other problems is available at
- http://www.ingber.com/ (or ftp.ingber.com) -- contact Lester Ingber
- (ingber@alumni.caltech.edu) 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
- (frost@sdsc.edu). 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 (jampel@cs.city.ac.uk), 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 (Sequential) Quadratic Programming
- SLP = Successive (Sequential) Linear Programming
- GRG = Generalized Reduced Gradient
-
- Solver Vendor Phone E-mail address
- Aptech Systems 206-432-7855 info@aptech.com
- ARKI Consulting &
- Development +45 44-49-03-23 info@arki.dk
- Frontline Systems 702-831-0300 info@frontsys.com
- ILOG 415-390-9000 info@ilog.com
- INRIA +33 13963-5557 scilab@inria.fr
- Prof. L. Lasdon 512-471-9433 lasdon@mail.utexas.edu
- LINDO Systems 312-988-7422 info@lindo.com
- Mathworks 508-653-1415 info@mathworks.com
- NAG (Numerical
- Algorithms Group) 630-971-2337 naginfo@nag.com
- Rutherford Appleton
- Laboratory +44 1235-821900 N.I.M.Gould@rl.ac.uk
- SAITECH 732-264-4700 saitech@monmouth.com
- Prof. K. Schittkowski +49 921-55-3278 Klaus.Schittkowski@uni-bayreuth.de
- Stanford Business
- Software 415-962-8719 sales@sbsi-sol-optimize.com
- Prof. A.L. Tits 301-405-3669 andre@isr.umd.edu
- Vanderplaats Research &
- Development 415-962-8719 vanderplaats@vma.com
- Visual Numerics 713-784-3131 info@boulder.vni.com
-
- Vendor Product Method
- Aptech GAUSS CO module SQP
- ARKI CONOPT GRG
- Frontline Systems GRG2, LSGRG GRG
- ILOG Numerica Constraint-based global search
- INRIA Scilab SQP
- L. Lasdon GRG2 GRG
- INTPT Interior point
- SLP SLP
- SQP SQP
- LINDO Systems LINGO GRG
- Mathworks NAG Foundation various
- Toolbox various
- Optimization Toolbox
- NAG NAG Numerical Libraries various
- Rutherford Lab LANCELOT Trust region, augmented
- lagrangian
- SAITECH SOPT SQP, Interior point
- K. Schittkowski NLPQL SQP
- others various
- Stanford Bus Soft LSSOL Active set method
- MINOS Reduced gradient
- NPSOL SQP
- A.L. Tits FSQP SQP
- Vanderplaats DOC/DOT various
- Visual Numerics IMSL various
-
- Modeling
- Product Phone E-mail address
- AIMMS +31 23-5350935 info@paragon.nl
- AMPL 702-322-7600 info@ampl.com, info@modeling.com
- ASCEND 412-268-2344 a.westerberg@cmu.edu
- CUTE +32 81-724917 pht@math.fundp.ac.be
- GAMS 415-583-8840 gams@gams.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 info@aptech.com, or
- call +1-206-432-7855.
- * 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 +45 44 49 03 23, e-mail
- adrud@arki.dk
- * DFPMIN - Numerical Recipes (Davidon-Fletcher-Powell)
- * Eureka - Borland Software (for IBM PC class of machines)
- * FFSQP/CFSQP (Fortran/C) - Contact Andre Tits, andre@src.umd.edu. 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,
- zbyszek@mosaic.uncc.edu.
- * 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:
- info@mathworks.com .
- * MINOS - Stanford Business Software Inc., 415-962-8719. Mailing address:
- 2672 Bayshore Parkway, Suite 304, Mountain View, CA 94043. Email:
- mike@sol-michael.stanford.edu. This large-scale code is often used by
- researchers as a "benchmark" for others to compare with.
- * MINPACK I and II - Contact Jorge More', more@mcs.anl.gov, 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: Klaus.Schittkowski@uni-bayreuth.de. 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 bongart@watson.ibm.com
- * Andy Conn arconn@watson.ibm.com
- * Nick Gould gould@cerfacs.fr
- * Philippe Toint pht@math.fundp.ac.be
-
- John Beasley has posted information on his OR-Lib, which contains various
- optimization test problems. Send e-mail to umtsk99@vaxa.cc.imperial.ac.uk 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 moshir@ee.ucla.edu.
-
- 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 - schulze@asgard.lpl.arizona.edu]
-
- 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 phcalamai@dial.waterloo.edu,
- 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 "netlib@ornl.gov", 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 netlib@nac.no
- * England netlib@ukc.ac.uk
- * Germany anonymous@elib.zib-berlin.de
- * Taiwan netlib@nchc.edu.tw
- * Australia netlib@draci.cs.uow.edu.au
-
- 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 (ashbury@skypoint.com), and
- is currently being maintained by Robert Fourer (4er@iems.nwu.edu) 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 (4er@iems.nwu.edu) and Gregory, John W.
- (ashbury@skypoint.com), "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 mail-server@rtfm.mit.edu 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 4er@iems.nwu.edu.
-
- [ ]
-
- END nonlinear-programming-faq
-