Global Extrema Locator Parallelization for Interval Arithmetic
Gelpia is a cooperative, interval-arithmetic branch-and-bound based algorithm (IBBA). It rigorously finds an upper bound on the global maximum of a multivariate function on a given interval. This means that its answer is guaranteed to be above the global maximum on the interval when evaluated using real arithmetic.
Gelpia is a cooperative solver in the sense that we concurrently run fast, approximate algorithms which find local maxima to inform the IBBA of new lower bounds. This causes the IBBA to refocus its attention on more promising regions of the search space. Meanwhile, the IBBA informs the cooperative algorithms of the search space currently being explored to keep them focused on trying to find the global maximum. We have found that this bi-directional communication significantly reduces runtime, allowing us to handle functions with many variables.
Building and usage
Known to build on Ubuntu 14.04 through 16.04
Currently only Linux is explicitly supported.
- Not included:
- c++ compiler
- c compiler
- rust nightly
- Not included:
For automatic building of the requirements run
For building by hand see documents/BuildingRequirements
Once requirements are met, gelpia may be compiled by running
This runs Rust's cargo build system as well as adding the correct files to bin for execution.
Gelpia may then be ran, it is an executable
gelpia in the
It has a built in help system for argument clarification.
A file may be specified which has arguments in it, one per line, this filename must be preceded by the @ symbol. The benchmarks/fptaylor_generated directory has many of these files.
Additional arguments, or overwiting arguments, may be specified after the file.
'x2' : [4.993896484375, 5],
'x1' : [4.990234375, 5],
Solver time: 0.21112608909606934
Overriding input tolerance
>./bin/gelpia @benchmarks/fptaylor_generated/gelpia_jet.txt -ie 1e-15
'x2' : [4.999999976716935, 5],
'x1' : [4.999999981373548, 5],
Solver time: 0.34747815132141113
Dreal dOp format support
We currently support a subset of Dreal's
dOp optimizer input format. An example can be found at benchmarks/dop_benchmarks/pows.dop. Full examples can be found in benchmarks/dreal_dop_benchmarks
An example run:
'x' : [4.9990234375, 5],
Parsing time: 0.07706475257873535
Solver time: 0.3199582099914551
Gelpia's dOp mode cannot currently handle constraints as constraint propogation is not currently implemented.
Gelpia may outlive the supplied time limit. This is because it goes through the remaining branches in the priority queue – this can sometimes be a lengthy process. This is why we have a grace option which is an additional grace period after the supplied timeout before gelpia is killed hard.
When used for minimization, Gelpia will report a guaranteed lower bound on the global minimum.
Gelpia is authored by Mark S. Baranowski and Ian Briggs