 |
Institut für Mathematik Fakultät für Naturwissenschaften und Mathematik Universität Wien |
|
|||
| Download |
Documentation |
Installation |
Links |
Patent
Issues |
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.
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.
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.