------------------------------------------------------------------------ ---------------------------- update request --------------------------- ------------------------------------------------------------------------ Global Optimization Software Survey - Information Update Please send new or updated information to Janos Pinter regarding your lgobal optimization software. For the minimal amount of information requested, please consult the December 1996 issue of Optima (the Newsletter of the Mathematical Programmming Society); an ASCII version is available below. Additional details related to type / size of solvable problems, as well as to various applications will also be useful. Thank you for your contribution. I intend to make the collected information available in the near future. Janos Pinter ------------------------------------------------------------------------ ------------------------------------------------------------------------ ------------------------------------------------------------------------ ************************************************************************ J. Pint\'{e}r, Continuous global optimization software: a brief review, Optima 52 (December 1996), 1-8. ************************************************************************ This information is based on the above article of Janos Pinter in Optima, the newsletter of the Mathematical Programming Society. (Reproduced and distributed with permission.) Please refer to the Optima article when referring to this material. Janos Pinter welcomes comments, corrections, modifications, information updates, etc. ************************************************************************ CONTINUOUS GLOBAL OPTIMIZATION SOFTWARE: A BRIEF REVIEW J\'{a}nos D. Pint\'{e}r Pint\'{e}r Consulting Services (PCS), and Dalhousie University PCS address: 129 Glenforest Drive, Halifax, NS, Canada B3M 1J2 e-mail: pinter@tuns.ca http://www.tuns.ca/~pinter/ Abstract ------- Following a concise introduction to multiextremal mathematical programming problems and global optimization (GO) strategies, a commented list of software products for analyzing and solving continuous GO problems is presented. Keywords: --------- Multiextremal optimization models; continuous global optimization; solution approaches; software review. AMS Subject Classification: 65K30, 90C05. --------------------------- 1. Global Optimization Models and Solution Approaches ----------------------------------------------------- A large variety of quantitative decision issues, arising in the sciences, engineering and economics, can be perceived and modelled as a constrained optimization problem. According to this generic description, the best decision - often expressed by a real vector - is sought which satisfies all stated feasibility constraints, and minimizes (or maximizes) the value of an objective function. Applying standard mathematical programming notation, we shall consider problems in the general form (1) min f(x) subject to x \epsilon D \in R^n. The function f symbolizes the objective(s) in the decision problem, and D denotes the (non-empty) set of feasible decisions. D is usually defined by a finite number of functions; for the purposes of the present discussion, we shall assume that (2) D={x \epsilonD \in R^n: l \le x \le u; g_j(x) \le 0 j=1,...,J}. In (2) l and u are explicit (finite) bounds, and g_j j=1,...,J are given constraint functions. Postulating now that all functions defined above are continuous, the optimal solution set to problem (1)-(2) is non-empty. Most typically, it is assumed that the decision problem modelled by (1)-(2) has a unique - locally and, at the same time, also globally - optimal solution. Uniextremality is often implied by the mathematical model structure (for example, by the strict convexity of f, and the convexity of D). This paradigm corresponds to the situation in which one, supposedly, has a sufficiently close initial 'guess' of the feasible region where the optimal solution x^* is located. Hence, the global optimality of the solution directly follows, having found the single local optimum of f on D. For example, linear and convex nonlinear programming models - both, in essence, satisfying the mentioned uniextremality assumption in most practical cases - have been extensively applied in the past decades to formulate and solve an impressive range of decision problems. Although very important classes of models naturally belong to the above category, there is also a broad variety of problems, in which the property of uniextremality cannot be simply postulated or verified. Consider, for instance, the following general problem types: \bullet nonlinear approximation, including the solution of systems of nonlinear equations and inequalities \bullet model fitting to empirical data (calibration, parameterization) \bullet optimized design and operation of complex 'black box' ('oracle') systems, e.g., in diverse engineering contexts \bullet configuration/arrangement design (e.g., in various data classification, facility location, resource allocation, or scientific modelling contexts) Such problems - together with numerous other prospective application areas - are discussed by Pint\'{e}r (1996), and the extensive list of related references therein. For further applications consult, e.g., Pardalos and Rosen (1987), T\"{o}rn and \v{Z}ilinskas (1989), Floudas and Pardalos (1990, 1992), Grossmann (1996), Bomze, Csendes, Horst and Pardalos (1996), or special application-related issues of the Journal of Global Optimization. The emerging field of Global Optimization (GO) deals with mathematical programming problems, in the (possible) presence of multiple local optima. Observe that, typically, the number of local (pseudo)solutions is unknown and it can be quite large. Furthermore, the quality of the various local and global solutions may differ significantly. In presence of such structure - often visualized by 'hilly landscapes' corresponding to projections of the objective function into selected subspaces (given by coordinate-pairs of the decision variable x) - GO problems can be extremely difficult. Hence, most classical numerical approaches are, generally speaking, not directly applicable to solve them. For illustration, see Figure 1 which displays a - relatively simple - composition of trigonometric functions with imbedded polynomial arguments, in just two variables (denoted by x and y). Figure 1 follows here Caption: Figure 1. A multiextremal function in two variables Naturally, under such circumstances, it is essential to use a proper global search strategy. Furthermore, instead of 'exact' solutions, most typically one has to accept diverse numerical approximations to the globally optimal solution (set) and optimum value. Following early sporadic work related to GO (since the late fifties), the present state-of-art is characterized by several tens of monographs, a professional journal and - at least - a few thousand research articles devoted primarily to the subject. A few illustrative references are provided at the end of this brief review. The most important GO model-classes which have been extensively studied include the following examples. (Please recall the general model form (1)-(2), and note that the problem-classes listed below are not necessarily distinct: in fact, several of them are hierarchically contained by more general problem-types listed.) \bullet Bilinear and biconvex programming (f is bilinear or biconvex, D is convex) \bullet Combinatorial optimization (problems which have discrete decision variables in f and/or in g_j j=1,...,J can be equivalently reformulated as GO problems in continuous variables) \bullet Concave minimization (f is concave, D is convex) \bullet Continuous global optimization (f is continuous, D is compact) \bullet Differential convex (D.C.) optimization (f and g_j j=1,...,J can all be represented, as the difference of two corresponding convex functions) \bullet Fractional programming (f is the ratio of two real functions, and g_j j=1,...,J are convex) \bullet Linear and nonlinear complementarity problems (f is the scalar product of two vector functions, D is typically convex) \bullet Lipschitz optimization (f and g_j j=1,...,J are arbitrary Lipschitz-continuous functions) \bullet Minimax problems (f is some minimax objective, the maximum is considered over a discrete set or a convex set, D is convex) \bullet Multilevel optimization (models non-cooperative games, involving hierarchies of decision-makers, their conflicting criteria are aggregated by f; D is typically assumed to be convex) \bullet Multiobjective programming (e.g., when several conflicting linear objectives are to be optimized over a polyhedron) \bullet Multiplicative programming (f is the product of several convex functions, and g_j j=1,...,J are convex, or - more generally - multiplicative functions) \bullet Network problems (f can be taken from several function-classes including nonconvex ones, and g_j j=1,...,J are typically linear or convex) \bullet Parametric nonconvex programming (the feasible region D and/or the objective f may also depend on a parameter vector) \bullet Quadratic optimization (f is an arbitrary - indefinite - quadratic function; g_j j=1,...,J are linear or, in the more general case, can be arbitrary quadratic functions) \bullet Reverse convex programming (at least one of the functions g_j expresses a reverse convex constraint) \bullet Separable global optimization (f is an arbitrary nonlinear - in general, nonconvex - separable function, D is typically convex) \bullet Various other nonlinear programming problems, including, e.g., nonconvex stochastic models (in which the defining functions f, g_j j=1,...,J depend on random factors, possibly in an implicit, 'black box' manner) For detailed descriptions of most of these model-types and their connections consult, e.g., Horst and Pardalos (1995), with numerous further references. There are several main classes of algorithmic GO approaches which possess strong theoretical convergence properties, and - at least in principle - are straightforward to implement and apply. All such rigorous GO approaches have an inherent computational demand which increases non-polynomially, as a function of problem-size, even in the simplest GO instances. It should be emphasized at this point that GO approaches are (should be) typically completed by a 'traditional' local optimization phase - at least when considering also numerical efficiency issues. Global convergence, however, needs to be guaranteed by the global scope algorithm-component which - theoretically - should be used in a complete, 'exhaustive' fashion. These remarks indicate the significant difficulty of developing robust and efficient GO software. Without aiming at completeness, several of the most important GO strategies are listed below; for details, consult, for instance, the corresponding works from the list of references. (Note that the listing below is not complete, and its items are not necessarily mutally exclusive: some software implementations combine ideas from several approaches.) \bullet Adaptive partition and search strategies (including, i.a., branch- and-bound algorithms, Bayesian approaches and interval arithmetic based methods) (Forg\'{o}, 1988; Ratschek and Rokne, 1988; Mockus, 1989; Neumaier, 1990; Zhigljavsky, 1991; Hansen, 1992; Horst and Pardalos, 1995; Horst and Tuy, 1996; Pint\'{e}r, 1996; Kearfott, 1996) \bullet Adaptive stochastic search algorithms (including random search, simulated annealing, evolution and genetic algorithms) (van Laarhoven and Aarts, 1987; Zhigljavsky, 1991; Horst and Pardalos, 1995; Michalewicz, 1996; Pint\'{e}r, 1996) \bullet Enumerative strategies (for solving combinatorial problems, or certain 'structured' - e.g., concave - optimization problems) (Forg\'{o}, 1988; Horst and Pardalos, 1995; Horst and Tuy, 1996) \bullet 'Globalized' local search methods (applying a grid search or random search type global phase, and a local search algorithm) (Horst and Pardalos, 1995; Pint\'{e}r, 1996) \bullet Heuristic strategies (deflation, tunneling, filled function methods, approximate convex global underestimation, tabu search, etc.) (Horst and Pardalos, 1995; Pint\'{e}r, 1996) \bullet Homotopy (parameter continuation) methods and related approaches (including fixed point methods, pivoting algorithms, etc.) (Horst and Pardalos, 1995) \bullet Passive (simultaneous) strategies (uniform grid search, pure random search) (Zhigljavsky, 1991; Horst and Pardalos, 1995; Pint\'{e}r, 1996) \bullet Successive approximation (relaxation) methods (cutting plane, more general cuts, minorant construction approaches, certain nested optimization and decomposition strategies) (Forg\'{o}, 1988; Horst and Pardalos, 1995; Pint\'{e}r, 1996) \bullet Trajectory methods (differential equation model based, path-following search strategies) (Horst and Pardalos, 1995) In spite of a considerable progress related to the rigorous theoretical foundations of GO, software development and 'standardized' use lag behind. The main reason for this is, of course, the inherent numerical difficulty of GO, even in case of 'simpler' specific instances (such as, e.g., the indefinite quadratic programming problem). In general, the difficulty of a global optimization problem (GOP) can be expected to increase as some exponential function of the problem dimension n. Consequently, dimensions 100, 50 or even 10 can already be considered as 'large', depending on the GOP type investigated (please recall Figure 1). In the remainder of this paper, an illustrative list of software products to solve GOPs is reviewed. 2. GO Software: Information Sources and Some General Remarks ------------------------------------------------------------ For the purposes of collecting information to this survey, GO software authors have been asked (mainly by sending e-mail messages, and by placing 'electronic ads' at several prominent mathematical programming sites on the WWW) to submit documentation related to their work. The information - or lack thereof - summarized below is largely based on the responses received. Additional information has been collected from the Internet, from several GO books, and from the Journal of Global Optimization. Note that though in many research publications reference is made to numerical examples, or even to sophisticated specific applications, only such work is reported below which is understood to be a general purpose, 'off-the-shelf' - i.e., at least in principle readily available, and legally distributable - program system for handling a particular GOP class. For obvious reasons, the present survey is far from being 'complete' in any possible sense; rather, it is an attempt to provide a realistic picture of the state-of-art, supported by instances of existing software. This short review is not intended to be either comparative or 'judgemental': one simple reason being that the information received from GO software developers is used 'as is', mostly without the possibility of actual software testing. By the same token, the accuracy of all information cannot be guaranteed, either. Further research into this direction - including the preparation of a more comprehensive and detailed survey - is thought to be important; some of that work is currently in progress. The software list provided in the next section is simply alphabetical, without categorization (which - in absence of detailed information - would possibly be imprecise anyway). For a more uniform presentation style, abbreviations are associated with all software products listed, even when such names were not given in the documentation available for this survey (existing names were not changed, of course). The descriptions are almost formula-free and extremely concise - due to space restrictions. For the latter reason, we decided not to include important classes of more specific GO approaches and related methodology. In particular - as reflected by the title - pure or mixed integer programming, and more general combinatorial optimization algorithms are not discussed here. Furthermore, although most of the available top-of-the-line continuous nonlinear (convex) optimization software can be applied - with good taste and some luck - to analyze GOPs, even the most prominent such systems are excluded from this review. Again, it is planned to prepare a more detailed survey, appropriately discussing also the program system types mentioned. The hardware and software platform of the systems reviewed is also shown, when such information is available. In order to assist the Reader in obtaining additional information, contact person(s), their e-mail addresses, ftp and/or WWW sites are listed, whenever known to me. (For brevity, only a few such pointers are provided in each case.) The Reader is assumed to have at least some basic familiarity with the GO approaches mentioned: for related discussions, please consult the references. 3. Short Software Descriptions ------------------------------ \alphaBB -- A GO Algorithm for General Nonconvex Problems --------------------------------------------------------- An implementation of a Branch-and-Bound (B&B) algorithm which is based on the difference of convex functions (D.C.) transformation. Nonconvexities are identified and categorized as of either special or generic structure. Special nonconvex (such as bilinear or univariate concave) terms are convex lower bounded using customized bounding functions. For generic nonconvex terms, convex lower bounding functions are derived by utilizing the parameter \alpha (specified by the user, or derived based on theory). \alphaBB solves general unconstrained and constrained problems; it requires MINOS and/or NPSOL for the solution of linear or convex optimization subproblems. (Languages: C and Fortran.) Contact: I.P. Androulakis , C.A. Floudas , C.D. Maranas , http://titan.princeton.edu/. ANNEAL - Simulated Annealing ---------------------------- ANNEAL is based on the core SA approach, including several possibilities of parameter adjustment, and a deterministic solution refinement phase. It has been applied to predict complex crystal structures. Workstation implementation. Contact: W. Bollweg , H. Maurer , H. Kroll . ASA - CalTech Adaptive Simulated Annealing ------------------------------------------ ASA is developed to find the global optimum of a continuous non-convex function over a multidimensional interval (box). This algorithm permits an annealing schedule for 'temperature' decreasing exponentially in annealing time. The introduction of re-annealing also permits adaptation to changing sensitivities in the parameter-space. Some other adaptive options in ASA include self-optimize (to find optimal starting conditions) and quenching (to methodically find faster performance that might be useful for large parameter-spaces). (Language: C.) Contact: L. Ingber , http://www.ingber.com/#ASA-CODE. B&B - A Family of B&B Algorithms -------------------------------- This obvious acronym (by the present author) attempts to summarize several B&B type algorithms developed to solve certain structured GOP classes. These include (among others) indefinite quadratic, quasiconvex-concave, and general Lipschitz problems. Workstation implementations. (Language: C.) Contact: R. Horst , M. Nast , N. Thoai . BARON - Branch-And-Reduce Optimization Navigator ------------------------------------------------ Combines interval analysis and duality with enhanced B&B concepts. The BARON modules can handle structured nonconvex problems up to thousands of constraints and variables. The library of specialized modules includes solvers for numerous specific GOP-classes. (For other, more general problems, underestimation routines need to be provided by the user.) All modules can solve also such problems in which some or all of the variables are restricted to integer values. The specialized modules use OSL or MINOS, to solve interim subproblems. Workstations, UNIX type operating systems. (Languages: Fortran and GAMS.) Contact: N.V. Sahinidis, http://archimedes.me.uiuc.edu/sigma/baron.html, ftp://aristotle.uiuc.edu. BGO - Bayesian Global Optimization ---------------------------------- This program system includes four versions of Bayesian search, clustering, uniform deterministic grid, and pure Monte Carlo search. Bound constraints and more general constraints can be handled. Interactive DOS and UNIX versions are available. (Languages: Fortran and C.) Contact: J. Mockus , L. Mockus . cGOP - Global Optimization Program ---------------------------------- Solves structured GOPs which have an objective function of the form a^Tx+b^Ty+x^TAy+f_1(x)+f_2(y) with convex f_1, f_2, and linear constraints. Requires the presence of the commercial codes MINOS and/or CPLEX to solve linear, mixed-integer linear and convex subproblems. cGOP has been used to solve problems involving several hundred variables and constraints. Versions are available for workstations. (Language: C.) Contact: V. Visweswaran , C.A. Floudas , http://titan.princeton.edu/. CGU - Convex Global Underestimator ---------------------------------- This approach is designed to generate efficient approximations to the global minimum of a multiextremal function, by fitting a convex function to the set of all known (calculated) local minima. This heuristically attractive strategy requires only the sequential solution of auxiliary LPs, and some rather elementary calculations. CGU has been applied to calculate molecular structure predictions, up to several tens of variables. Implemented on parallel workstations and supercomputers. Contact: K.A. Dill, A.T. Phillips , J.B. Rosen . CRS - Controlled Random Search ------------------------------ This is a recently developed variant of a popular class of random search based methods which can be applied under very mild analytical conditions imposed on the GOP. Several other related stochastic search methods have also been developed by this group. Workstation implementations. Contact: M.M. Ali, A. T\"{o}rn , S. Viitanen . CURVI - Bound-Constrained Global Optimization --------------------------------------------- Windward Technologies (WTI) develops advanced numerical and visualization software, for solving constrained and unconstrained nonlinear optimization problems. One of their solvers, CURVI is aimed at solving bound-constrained nonlinear programs which have a complicated - possibly multiextremal - objective function. (Language: Fortran.) Contact: T. Aird , http://users.aol.com/WTI/. DE - Differential Evolution Genetic Algorithm for Bound Constrained GO ----------------------------------------------------------------------- DE won the third place at the 1st International Contest on Evolutionary Computation on a real-valued function test-suite. It was the best genetic algorithm approach (the first two places of the contest were won by non-GA algorithms). (Languages: Matlab and C.) Contact: R. Storn , http://http.icsi.berkeley.edu/~storn/code.html. ESA - Edge Searching Algorithm ------------------------------ An implementation of an edge search algorithm for finding the global solution of linear reverse convex programs. ESA is based on an efficient search technique and the use of fathoming criteria on the edges of the polytope representing the linear constraints. In addition, the method incorporates several heuristics, including a cutting plane technique which improves the overall performance. Implemented for several UNIX platforms; the TPG Test Problem Generator is also available. (Language: Fortran.) Contact: K. Moshirvaziri , . GA - Genetic Algorithms ----------------------- Genetic algorithms - as a rule - can be applied to GOPs under mild structural requirements. Both general and specific information related to this popular solver class is available from the following sources: - A Commented List of Genetic Algorithm Codes, ftp://ftp.germany.eu.net/pub/research/softcomp/ec/faq/www/q20_1.htm - GA Archive, http://www.aic.nrl.navy.mil/galist/src/. Only a few illustrative examples are listed in the present review. GAS - Genetic Algorithm ----------------------- Unconstrained and bound-constrained versions are available. For DOS and UNIX operating systems. (Language: C++.) Contact: M. Jelasity , ftp://ftp.jate.u-szeged.hu/pub/math/optimization/GAS/. GAucsd - Genetic Algorithm -------------------------- Developed and maintained at the University of California, San Diego. GAucsd was written in C under Unix, but should be easy to port to other platforms. The package is accompanied by brief information and a User's Guide. (Language: C.) Contact: nici@ucsd.edu, GAucsd-request@cs.ucsd.edu, ftp://cs.ucsd.edu/pub/GAucsd/. GENERATOR - Genetic Algorithm Solver ------------------------------------ This method is aimed at solving a variety of (combinatorial and continuous multiextremal) scientific and engineering optimization problems. It is designed to interact with Excel which serves as a user interface. (Platform: Excel.) Contact: New Light Industries , http://www.iea.com/~nli/. GC - Global Continuation ------------------------ GC is a continuation approach to GO applying global smoothing, in order to derive a simpler approximation to the original objective function. GC is applied by the authors to distance geometry problems, in the context of molecular chemistry modelling. IBM SP parallel system implementation. Contact: J.J.Mor\'{e} , Z. Wu. GENOCOP III - Genetic Algorithm for Constrained Problems -------------------------------------------------------- Solves general GOPs, in presence of additional constraints and bounds (using quadratic penalty terms). System parameters, domains, and linear inequalities are input via a data file. The objective function and any nonlinear constraints are to be given in appropriate C files. (Language: C.) Contact: Z. Michalewicz, http://www.coe.uncc.edu/~zbyszek/gcreadme.html, ftp://ftp.uncc.edu/coe/evol/genocopIII.tar.Z. GEODES - Minimum-Length Geodesic Computing ------------------------------------------ Approximating a minimum-length geodesic on a multidimensional manifold, GEODES is differential geometry software. However, it has potential also in the GO context. GEODES includes example manifolds and metrics; it is implemented in Elements (a matrix and function oriented scientific modelling environment) to compute and visualize geodesics on 2D surfaces plotted in 3-space. Portable to various hardware platforms. (Languages: C, C++.) Contact: W.L. Anderson , http://www.netcom.com/~elements/, http://www.netlib.org/ode/geodesic/. GLO - Global and Local Optimizer -------------------------------- GLO is a modular optimization system developed for 'black box' problems in which objective function calculations may take a long time. Its methodology is based on the coupling of global (genetic) and local (variable metric) nonlinear optimization software with scientific applications software. It has been applied to automated engineering design. Besides the modular optimization control system, GLO also has a graphical user interface, and includes a pre-processor. Contact: M.J. Murphy, http://www.llnl.gov/glo/09glo.html, M. Brosius . GLOBAL - Multistart with Stochastic Clustering ---------------------------------------------- GLOBAL can be used for the solution of the general bound-constrained GOP which has a (measurable) real objective function. The algorithm is a derivative-free implementation of the clustering stochastic multistart method of Boender et al., supplemented with a quasi-Newton local search routine and with a robust random local search method. Available for UNIX machines, IBM-compatible mainframes and PCs. (Languages: Fortran and C.) Contact: T. Csendes , http://www.inf.u-szeged.hu/~csendes/, ftp://ftp.jate.u-szeged.hu/pub/math/optimization/index.html. GLOBALIZER - An Educational Program System for Global Optimization ------------------------------------------------------------------ Serves for solving univariate GOPs. After stating the problem, the user can choose among various (random search, B&B based, or Bayesian partition based) solver techniques. The software has interactive tutoring capabilities, provides textual and graphical information. Works on PCs, under MS-DOS. Contact: R.G. Strongin , V.P. Gergel, A.V. Tropichev. GLOPT - Constrained Global Optimization --------------------------------------- Solves GOPs with a block-separable objective function subject to bound constraints and block-separable constraints: it finds a nearly globally optimal point that is near to a true local minimizer. GLOPT uses a B&B technique to split the problem recursively into subproblems that are either eliminated or reduced in their size. It includes a new reduction technique for boxes and new ways for generating feasible points of constrained nonlinear programs. The current implementation of GLOPT uses neither derivatives nor simultaneous information about several constraints. (Language: Fortran.) Contact: A. Neumaier , S. Dallwig and H. Schichl. GOPP - Global Optimization of Polynomial Problems using Gr\"{o}bner Bases ------------------------------------------------------------------------- The (local) optimality conditions to polynomial optimization problems lead to polynomial equations, under inequality constraints. Applying recent Gr\"{o}bner basis techniques, this approach is aimed at finding all solutions to such systems, hence also finding global optima. (Language: Maple.) Contact: K. Hagglof , P.O. Lindberg , L. Svensson , http://www.optsyst.math.kth.se. GOT - Global Optimization Toolbox --------------------------------- GOT combines random search and local (convex) optimization. DOS and HP UX versions are available. (Language: Fortran.) Contact: A.V. Kuntsevich . GSA - Generalized Simulated Annealing ------------------------------------- GSA is based on the generalized entropy by Tsallis. The algorithm obeys detailed balance conditions and, at low 'temperatures', it reduces to steepest descent. (Note that the members of the same research group have been involved in the development of several SA type algorithms.) Contact: J.E. Straub , P.Amara , J. Ma . IHR - Improving Hit-and-Run --------------------------- IHR is a random search based GO algorithm that can be used to solve both continuous and discrete optimization problems. IHR generates random points in the search domain by choosing a random direction and selecting a point in that direction. Versions have been implemented, using different distributions for the random direction, as well as several ways to randomly select points along the search line. The algorithm can also handle inequality constraints, and a hierarchy of objective functions. IHR has been used to solve GOPs in various disciplines such as in engineering design. Contact: Z. Zabinsky , ftp://ftp.bart.ieng.washington.edu. IMINBIS - Interval Arithmetic Based GO -------------------------------------- This method applies interval arithmetic techniques to isolate the stationary points of the objective function. Next, a topological characterization is used to separate minima from maxima and saddle points, followed by local minimization (sub)searches to select the global solution. The method has been applied also to 'noisy' problems. Workstation and PC implementations, extensive related research. (Language: Fortran.) Contact: M.N. Vrahatis , D.G. Sotiropoulos , E.C. Triantaphyllou. INTBIS - Global Solver for Polynomial Systems of Equations ---------------------------------------------------------- Finds all solutions of polynomial systems of equations, with rigorously guaranteed results. The software package INTBIS is ACM-TOMS Algorithm 681; it is available through NETLIB. Distributed with the package are four source code files, sample input and output files, and a brief documentation file. The source files consist of the following: interval arithmetic, stack management, core INTBIS routines, and machine constantse. (Language: Fortran.) Contact: R.B. Kearfott , http://interval.usl.edu/kearfott.html, ftp://interval.usl.edu/pub/interval_math/intbis/. INTOPT_90 - Verified (Interval) Global Optimization --------------------------------------------------- Serves to the verified solution of nonlinear systems of equations, and unconstrained and bound-and-equality-constrained global optimization. Based on exhaustive search, driven by a local optimizer, epsilon-inflation, interval Newton methods, and interval exclusion principles; uses automatic differentiation. Test results with hundreds of test examples. The underlying interval arithmetic package (ACM TOMS Algorithm 737) is also distributed. Workstation and PC implementations. (Language: Fortran.) Contact: R.B. Kearfott , http://interval.usl.edu/kearfott.html, ftp://interval.usl.edu/pub/interval_math/intbis/. INTGLO, INTGLOB - Integral Global Optimization ---------------------------------------------- These methods solve unconstrained and constrained, as well as discrete GOPs by the integral method. They also include a discontinuous penalty function approach for constrained problems. Problems up to one hundred variables have been solved. A set of test problems is also available, including box or unconstrained, constrained, concave minimization, discrete variable programs and multicriteria programs. For IBM PCs. (Language: Fortran.) Contact: Q. Zheng , D. Zhuang . ISA - Inductive Search Algorithm -------------------------------- ISA won first place at the 1st International Contest in Evolutionary Computation, on a real-valued function test-suite. (Language: C++.) Contact: G. Bilchev, information available at http://solon.cma.univie.ac.at/~neum/glopt/test_results.html#bilchev. LGO - Continuous and Lipschitz Optimization ------------------------------------------- Solves bound-constrained and more general GOPs under mild structural requirements; it can be applied also to 'black box' problems. LGO integrates several global (adaptive partition and random search based) and local (derivative-free conjugate directions type) strategies: these can be activated in interactive or automatic execution modes. The PC version has a menu interface to assist the application development process, includes a concise information / tutoring session, and has visualization capabilities. Available also for workstations. LGO has been applied to problems with up to 100 variables (can be configured to encompass larger sizes). Accompanied by a User's Guide and sample problems. (Language: Fortran.) Contact: J.D. Pint\'{e}r , http://www.tuns.ca/~pinter/. LOPS - Lipschitz Optimization Program System -------------------------------------------- In all approaches listed below, the objective function is defined over n-intervals. The Lipschitz-continuity of f or f' is also assumed. Problem-classes and corresponding available versions include: - one-dimensional GOPs (sequential methods with local tuning, PC version (Language: C++) - one-dimensional GOPs, parallel solver implementations (Language: Alliant FX/80, parallel Fortran) - multi-dimensional GOPs: sequential and parallel algorithms using Peano curves (Language: Alliant FX/80, parallel Fortran) Contact: Y.D. Sergeyev . MAGESTIC - Data Fitting by Global Optimization ---------------------------------------------- Automatic global optimization based on a fast modified Gauss-Newton approach combined with Monte Carlo search. MAGESTIC handles calibration model variants (e.g., parameter and error masks for restricted sub-fitting, implicit equation fitting without solving, etc.). Suitable for use also with Lagrange multipliers for constrained optimization. Uses Excel as an interface (under Windows) and for generating graphics. (Platform: Excel.) Contact: Logix Consulting , http://www.lgx.com/magestic.html. MULTISTART - Clustering Algorithm --------------------------------- This widely used approach is based on random search - or some other initial sampling in the feasible set - combined with clustering, and local optimization launched from the most 'promising' point(s). Implemented on SUN workstations. Several interesting applications - in combination with simulation models - are related to the analysis of oil resources. (Language: Fortran.) Contact: S. Buitrago . NETSPEAK - General Network Optimization --------------------------------------- This is an algebraic modelling language used to specify, solve, and analyze general - linear, but also possibly nonconvex - minimum cost network flow problems. A wide variety of network and network-related topologies (pure networks, networks with side-constraints and/or side variables, generalized networks) can be modelled using NETSPEAK. The language is being developed as a Windows application; it features flexible I/O, robust program control, and intuitive commands. Contact: B.W. Lamar . PA - Packet Annealing --------------------- In PA, the Gibbs distribution of the objective function is deterministically 'annealed' by tracing the evolution of a multiple Gaussian packet approximation. The approach has been applied to analyze complex molecular conformation models. IBM PC implementation. Contact: D. Shalloway , B.W. Church , M. Oresic . PROFIL - Interval Branch and Bound Method ----------------------------------------- Bound constrained interval global optimization, with rigorously guaranteed results. PROFIL is based on BIAS (Basic Interval Arithmetic Subroutines) which provides an interface for interval operations. For PC and a number of UNIX systems. (Language: C.) Contact: C. Jansson, O. Knueppel , http://www.ti3.tu-harburg.de/Software/PROFILEnglisch.html, ftp://ti3sun.ti3.tu-harburg.de/pub/profil/unix/profopt.tar.Z, ftp://ti3sun.ti3.tu-harburg.de/pub/profil/pc/profopt.tgz. PVGO - Parallel Verified Global Optimization -------------------------------------------- PVGO is a new parallel method for interval global optimization. Implemented on a Connection Machine CM5. (Language: Pascal-XSC.) Contact: S. Berner . RSBB - Reduced Space Branch-and-Bound Method -------------------------------------------- RSBB applies variable domain reductions and an underestimating module. Two versions run under Unix; one of these algorithms is described in Chapters 1 and 2 of Grossmann (1996). (Language: both versions in C++, they use external Fortran procedures.) Contact: T. Epperly, t.epperly@ic.ac.uk, http://www.ps.ic.ac.uk/~epperly/index.html. SA - Simulated Annealing ------------------------ In addition to the algorithm itself, this includes on-line interactive demonstration, and additional information on C++ classes , random number generation, Monte Carlo methods and Forth. A Nelder-Mead simplex method implementation is also available. (Languages: C, C++, Ada and Forth.) Contact: E. Carter, Taygeta Scientific Inc. , http://www.taygeta.com/annealing/simanneal.html. SAT - Global Optimization for Satisfiability Problems ----------------------------------------------------- Boolean satisfiability (SAT) problems can be directly transformed into unconstrained GOPs. These, in turn, can be solved by specifically tailored solvers. Workstation implementations. Contact: J. Gu . SIGMA - Stochastic Integration Global Minimization Algorithm ------------------------------------------------------------ The software package SIGMA is Algorithm 667; appeared in ACM-TOMS 14 (1988) 366-380. Includes also the code of several test GOPs. (Language: Fortran.) Contact: F. Aluffi-Pentini, V. Parisi and F. Zirilli , http://www.netlib.no/netlib/toms/667. SIMANN - Simulated Annealing ---------------------------- This program implements the continuous simulated annealing global optimization algorithm described in Corana et al., ACM TOMS 13 (1987) No. 3, 262-280. Algorithm modifications and many details on its use can be found in Goffe et al., J. of Econometrics 60 (1994) No. 1-2, 65-100. (Language: Fortran.) Contact: B. Goffe, , http://www.netlib.no/netlib/opt/simann.f. SOLVEX - Solver for Nonlinear Optimization Problems --------------------------------------------------- For solving constrained and unconstrained nonlinear, multiobjective and GOPs. SOLVEX algorithm libraries include the methods listed below: - unconstrained minimization: Hooke-Jeeves direct search, conjugate gradient method, Shor R-algorithm, Powell-Brent method - general nonlinear programming problem: penalty functions, Lagrange function method, parameterization method - global optimization: sequential set covering technique, simulated annealing, clustering algorithm - multicriteria optimization: convolution methods, including goal programming, direct Pareto approximation. Interactive use enhanced by a built-in problem editor and graphics capabilities. Contact: M.A. Potapov . TORUS - Stochastic Algorithm for Global Minimization with Constraints --------------------------------------------------------------------- It is a Monte Carlo algorithm, combined with annealing search principles. The software package TORUS is Algorithm 774; appeared in ACM-TOMS 21 (1995) 194-213. Includes also the code of several test GOPs. Contact: F. M. Rabinowitz, http://www.netlib.no/netlib/toms/744. TRUST - Terminal Repeller Unconstrained Subenergy Tunneling ----------------------------------------------------------- This method formulates the GOP as the solution of a deterministic dynamical system incorporating terminal repellers and a subenergy tunneling function. Benchmark tests comparing this method to other global optimization procedures are presented, with favourable results. The TRUST formulation leads to a simple stopping criterion. In addition, the structure of the equations enables an implementation of the algorithm in analog VLSI hardware (in the spirit of artificial neural networks) for further speed enhancements. Contact: B.C. Cetin, J. Barhen and W. Burdick; TRUST is described in JOTA 77 (1993) No. 1. TVC - Toolbox for Verified Computing ------------------------------------ Can be applied to the rigorous solution of nonlinear systems of equations, and to general unconstrained and bound-constrained GOPs. TVC is based on interval B&B and interval Newton methods, it also has automatic differentiation capabilities. The toolbox can be used on PCs, workstations and parallel computers. (Languages: PASCAL-XSC, C++.) Test problems have been solved up to one hundred variables. A driver program and hundreds of test examples are available from the author. Contact: D. Ratz , http://www.uni-karlsruhe.de/~iam, http://ourworld.compuserve.com/homepages/numerik_software. UFO - Universal Functional Optimization --------------------------------------- Interactive modular system for solving problems, and for algorithm development. Several types of GO methods - random search, continuation, clustering, and random plus local search - can be applied. For PCs. (Language: Fortran.) Contact: L. Luksan , M. Tuma, M. Siska, J. Vlcek and N. Ramesova, ftp: uivt.cas.cz/pub/msdos/ufo. UNICALC - Interval Branch and Bound Algorithm --------------------------------------------- UNICALC serves for bound-constrained GO; accepts also inequality and/or equality constraints and decision variables. Contact: A. Semenov, information available at ftp://ftp.iis.nsk.su/pub/ai/unicalc. VerGO - Verified Global Optimization ------------------------------------ VerGO is designed for rigorous bound (and approximate general constrained) GO of a twice continuously differentiable objective function. VerGO features include interval arithmetic, automatic differentiation, non-convexity test, monotonicity test, and local optimization. Tested on problems up to over 30 variables. DOS, OS/2, Linux and workstation versions. (Language: C++.) Contact: R. van Iwaarden , http://www.cs.hope.edu/~rvaniwaa/VerGO/VerGO.html. VTT - Interval Arithmetic Research ---------------------------------- The goals of the Interval Arithmetic, Constraint Satisfaction and Probability Project are summarized as follows: - development of portable C++ libraries for interval programming tasks - integration of the libraries to Microsoft Excel - application in financial planning software products (Platforms: C++, Excel.) Contact: S. De Pascale , http://www.vtt.fi/tte/. 4. Acknowledgements ------------------- The software review presented here is based to a significant extent on information kindly provided by colleagues working on GO and/or closely related areas. I would like to especially thank Arnold Neumaier and Simon Streltsov for the information collected on their WWW Global Optimization Pages (respectively, http://solon.cma.univie.ac.at/~neum/glopt/, and http://cad.bu.edu/go/). I also wish to thank Faiz Al-Khayyal for his valuable comments on the manuscript. The space (and time) limitations of this review certainly have made it illusory to include 'all' existing software on this rapidly changing area: omissions are entirely possible, but absolutely unintentional... It is planned to continue this work, and to provide a more comprehensive and informative picture of the state-of-art, for the mathematical programming community. Comments and suggestions are most welcome: they will contribute to an 'unabridged' GO software review in the near future. References ---------- To avoid a superfluously long listing, the reference list is reduced to the most topical journal, and to several GO monographs and handbooks published in the past ten years. Bomze, I.M., Csendes, T., Horst, R., and Pardalos, P.M., eds. (1996) Developments in Global Optimization. Kluwer Academic Publishers, Dordrecht / Boston / London. Floudas, C.A. and Pardalos, P.M. (1990) A Collection of Test Problems for Constrained Global Optimization Algorithms. Lecture Notes in Computer Science 455, Springer, Berlin / Heidelberg / New York. Floudas, C.A. and Pardalos, P.M., eds. (1992) Recent Advances in Global Optimization. Princeton University Press, Princeton. Forg\'{o}, F. (1988) Nonconvex Programming. Akad/'{e}miai Kiad\'{o}, Budapest. Grossmann, I.E., ed. (1996) Global Optimization in Engineering Design. Kluwer Academic Publishers, Dordrecht / Boston / London. Hansen, E.R. (1992) Global Optimization Using Interval Analysis. Marcel Dekker, New York. Horst, R. and Tuy, H. (1996) Global Optimization - Deterministic Approaches. Springer, Berlin / Heidelberg / New York. (3rd Edn.) Horst, R. and Pardalos, P.M., eds. (1995) Handbook of Global Optimization. Kluwer Academic Publishers, Dordrecht / Boston / London. Journal of Global Optimization (published since 1991, by Kluwer Academic Publishers). Kearfott, R.B. (1996) Rigorous Global Search: Continuous Problems. Kluwer Academic Publishers, Dordrecht / Boston / London. Michalewicz, Z. (1996) Genetic Algorithms + Data Structures = Evolution Programs. Springer, Berlin / Heidelberg / New York. (3rd Edn.) Mockus, J. (1989) Bayesian Approach to Global Optimization. Kluwer Academic Publishers, Dordrecht / Boston / London. Neumaier, A. (1990) Interval Methods for Systems of Equations. Cambridge University Press, Cambridge. Pardalos, P.M. and Rosen, J.B. (1987) Constrained Global Optimization: Algorithms and Applications. Lecture Notes in Computer Science 268, Springer, Berlin / Heidelberg / New York. Pint\'{e}r, J.D. (1996) Global Optimization in Action. Kluwer Academic Publishers, Dordrecht / Boston / London. Ratschek, H. and Rokne, J.G. (1988) New Computer Methods for Global Optimization. Ellis Horwood, Chichester. T\"{o}rn, A.A. and \v{Z}ilinskas, A. (1989) Global Optimization. Lecture Notes in Computer Science 350, Springer, Berlin / Heidelberg / New York. van Laarhoven, P.J.M. and Aarts, E.H.L. (1987) Simulated Annealing: Theory and Applications. Kluwer Academic Publishers, Dordrecht / Boston / London. Zhigljavsky, A.A. (1991) Theory of Global Random Search. Kluwer Academic Publishers, Dordrecht / Boston / London.