University of Vienna Logo    Institut für Mathematik
Fakultät für Naturwissenschaften und Mathematik
Universität Wien

Download
Documentation
Installation
Links
Patent Issues

COCONUT Environment
An open source solver platform for
global optimization problems



The COCONUT Environment is a modular solver environment for nonlinear continuous global optimization problems with an open-source kernel, which can be expanded by commercial and open-source solver components (inference engines). The first test version of the environment was provided back in 2004 by the COCONUT consortium. Since then it has been under continuous improvement and stabilization, in particular, during the project P18704-N13 sponsored by FWF, the Austrian Science Foundation. The full source of the current development version including the solvers, the strategy engine and the converters is available via a subversion repository. In addition, we provide a binary compiled version of the converters and the two available global optimization solvers. For more information on obtaining the COCONUT sources and binaries please visit the download section.

The application programmer's interface (API) is designed to make the development of the various module types independent of each other and independent of the internal model representation. It is a collection of open-source C++ classes protected by the LGPL and GPL license models, so that most of it could be used as part of commercial software (special license regulations are contained in the distribution, and they can be read here). It uses the FILIB++ library for interval computations and the matrix template library (MTL) for the internal representation of various matrix classes. The graphs are implemented using the VGTL (Vienna Graph Template Library), and the search database is based on the VDBL (Vienna DataBaseLibrary). Support for dynamic linking relieves the user from recompilation when modules are added or removed. In addition, it is designed for distributed computing, and will probably be developed further (in the years after the end of the COCONUT project) to support parallel computing as well.

The solution algorithm is an advanced branch-and-bound scheme which proceeds by working on the search graph, a directed acyclic graph (DAG) of search nodes, each representing an optimization problem, a model. The search nodes come in two flavors: full nodes which record the complete description of a model, and delta nodes which only contain the difference between the model represented by the node and its (then only) parent.

Search Graph
Search graph

The optimization problems stored in the work nodes, which are passed to the various inference engines, are kept as directed acyclic graphs (DAG), as well. This representation has big advantages. Hereby, a complete optimization problem is always represented by a single DAG. The vertices of the graph represent operators similar to computational trees. Constants and variables are sources, objective and constraints are sinks of the DAG.

Every vertex represents a real valued function of n variables. Predefined functions include sum, product, max, min, elementary real functions (exp, log, pow, sqrt, ...), and also some discrete operators like all_diff and count.

For expression graphs (DAG or tree), special forward and backward evaluators are provided. Currently implemented are real function values, function ranges, gradients (real, interval), Hessians (real, interval), and slopes. In the near future evaluators for second order slopes will be provided, as well.

The strategy engine consists of the logic core (``search'') which is essentially the main solution loop. It calls the management modules, the report modules, and the inference engines in a sequence defined by programmable search strategies.

Component framework
Component Framework

The engine can be programmed using a simple strategy language, an interpreted language based on Python. Since it is interpreted, (semi-)interactive and automatic solution processes are possible, and even debugging and single-stepping of strategies is supported. The language is object oriented, garbage collecting, and provides dynamically typed objects. These features make the system easily extendable.

For the solution strategy, the most important class of modules are the inference engines. They provide the computational base for the algorithm, namely methods for problem structure analysis, local optimization, constraint propagation, interval analysis, linear relaxation, convex optimization, bisection, ....

Corresponding to every type of problem change, a class of inference engines is designed: model analysis (e.g. find convex part), model reduction (e.g. pruning, fathoming), model relaxation (e.g. linear relaxation), model splitting (e.g. bisection), model glueing (e.g. undo excessive splitting), computing of local information (e.g. probing, local optimization).

Inference engines calculate changes to a model that do not change the solution set. But they never change the model; the decision to apply the changes if they are considered useful is left to the strategy engine. The inference engines are implemented as subclass of a single C++ base class. In addition, there is a fixed documentation structure defined.

Several state of the art techniques are provided: A wrapper for DONLP3, a general purpose nonlinear local optimizer for continuous variables, STOP, a heuristic starting point generator, Karush-John-Condition generator using symbolic differentiation, Point Verifier for verifying solution points, Exclusion Box generator, calculating an exclusion region around local optima, Interval constraint propagation, Linear Relaxation generator using slopes, CPLEX engine, a wrapper for the state of the art commercial linear programming solver by ILOG, LP_solve engine, a wrapper for the public domain LP solver, XPRESS engine, a wrapper for another state of the art commercial linear programming solver by Dash Optimization,Basic Splitter computing difficult variables and split variants, BCS, a box covering solver, Convexity detection, for simple convexity analysis, and more.

Management modules are the interface between the strategy engine and the internal representation of data and modules, taking care of the management of models, resources, initialization, the search graph, the search database, ....

They are provided to make it possible to change the implementation of the search graph and the internal representation of problems without having to change all of the modules. Management modiles just perform some of the changes which have been advertised by inference engines; they never calculate anything.

The final class of modules, called report modules, produce output. Human or machine readable progress indicators, solution reports, the interface to modeling languages (currently only AMPL and GAMS are supported). Among the report modules is also a AMPL to GAMS translator, which supports many but not all AMPL constructs.

Documentation

There are several technical reports describing the internal structure of the environment.
A good amount of the scientific background for the techniques in the COCONUT environment is described in the survey paper General information on global optimization can be found on at Global (and Local) Optimization.

Patent Issues

William G. Walster of SUN Microsystems has issued 22 patent applications to the US Patent and Trademark Office, three of them alone, one together with Ramon E. Moore, and 18 together with Eldon R. Hansen. We believe that some, if not most, of these patent applications are invalid because they are based on prior art, many of the algorithms are, e.g., described in the State-of-the-Art report published by the project in November 2001, which is more that one year prior to all of the patent applications. Should these patents be granted, the COCONUT environment might infringe on them. We are currently investigating. If you want to help us by pointing out prior art with respect to these patent applications, your information will be greatly welcome. Below is a list of the above mentioned patent applications:
PUB. APP. NO. Title
20040015531 Computing interval parameter bounds from fallible measurements using systems of nonlinear equations
20030172099 Method and apparatus for solving systems of linear inequalities
20030172095 Method and apparatus solving problems having interval parameters
20030145027 Method and apparatus for bounding the solution set of a system of linear equations
20030131034 Method and apparatus for solving systems of nonlinear equations using interval arithmetic
20030131033 Method and apparatus for solving an inequality constrained global optimization problem
20030130971 Method and apparatus for solving an unconstrained global optimization problem
20030130970 Method and apparatus for solving an equality constrained global optimization problem
20030115230 Applying term consistency to an inequality constrained interval global optimization problem
20030115229 Applying term consistency to an equality constrained interval global optimization problem
20030110195 Method and apparatus for solving systems of equations in fixed-point form
20030105789 Solving systems of nonlinear equations using interval arithmetic and term consistency
20030097390 Solving systems of nonlinear equations using interval arithmetic and term consistency
20030097191 Applying term consistency to the solution of unconstrained interval global optimization problems
20030055857 Method and apparatus for computing roots of a polynomial equation with interval coefficients
20030050947 Solving a nonlinear equation through interval arithmetic and term consistency
20030050946 Termination criteria for the interval version of newton's method for solving systems of non-linear equations
20030037086 Method and apparatus for facilitating exception-free arithmetic in a computer system
20030033339 Termination criteria for the one-dimensional interval version of newton's method
20030033335 Min and max operations for multiplication and/or division under the simple interval system
20030023645 Method and apparatus for automatically producing efficient code for computing derivatives
20020194232 Minimum and maximum operations to facilitate interval multiplication and/or interval division

Download

The COCONUT environment is distributed under the GNU GPL and the GNU LGPL licenses, but note that there is one additional license regulation concerning hardware and software by Sun Microsystems, which is explicitly spelled out in the file LICENSES contained in the distribution. Note that only those parts are included, which are essentially free. The current development version is available via a subversion repository. To gain access to it, please send a mail to the main developer and maintainer (Hermann dot Schichl atsign univie dot ac dot at). Please include an ssh public key (generate with ssh-keygen). The repository is located at svn+ssh://cocosrv@login.mat.univie.ac.at/coconut-environment/trunk. To get the package for donlp3, contact the author Peter Spellucci and afterwards me, and to get the CPLEX interface, contact ILOG to get a CPLEX license and afterwards download an ALPHA test version of the CPLEX interface and an additional library provided (but NOT MAINTAINED) by ILOG here. The heuristic global optimization package PGSL by Benny Raphael and its interface can be downloaded from here.

In addition to the full source distribution, we also provide two of its subsets as separate binary packages, created from a recent version of the development source above. The packages below were compiled for 32-bit i386 architectures under Linux Fedora Core 10 with gcc 4.3.2. (For those interested in the historical evolution of the COCONUT Environment, we provide here the first publicly available version 1.00 (RPMs, Sources) as well.)

Installation

When compiling the source distribution, copy the doprepare.definitions.sample file into a new file called doprepare.definitions, and edit the latter file according to your needs. Then call the 'doprepare' script. The RPM packages can be installed simply by using the rpm command. The prefix is adaptable, so you can use rpm --prefix=/yourdir to change the installation prefix from /usr to /yourdir.

Links

The COCONUT environment uses a number of external libraries. The following links point to the respective sources.
A number of inference modules are based on commercial software or on software, which is not public domain. Below are the contact addresses for the corresponding software packages.
A complete interface to the modeling systems AMPL and GAMS are available.

Acknowledgments


This site contains material provided by other partners in the COCONUT project, notably by Arnold Neumaier, Oleg Shcherbina, Eric Monfroy, and Brice Pajot. I also want to express special thanks to Tuan-Viet Nguyen, Xuan-Ha Vu, Boglarka Toth, Tamas Vinko, Knut Petras, Christian Keil, and Mihaly Markot.
Vienna, 2004-2010
Hermann Schichl
( Hermann DOT Schichl AT-SIGN esi DOT ac DOT at )