Jump to content

Octeract Engine

From Wikipedia, the free encyclopedia
Octeract Engine
Developer(s)Octeract
Stable release
4.7.1
TypeTechnical computing
LicenseSubscription
Websiteocteract.gg

Octeract Engine is a proprietary massively parallel deterministic global optimization solver for general Mixed-Integer Nonlinear Programs (MINLP).

The solver is designed to work in parallel on a distributed environment. It is optimized for succeeding in synthetic benchmark sets.[1] The latest world records were set in April 2023, when it became the first optimization solver to ever solve all problems in the benchmark, with a world record setting unscaled shifted geometric mean of 36.8.[2]

History

[edit]

Octeract Engine was developed by Nikos Kazazakis and Gabriel Lau.[3] The first public beta version of Octeract Engine was released in August 2019, and it came out of beta in August 2020.

Performance

[edit]

On 23 July 2022 it ranked first on the single thread Mittelmann MINLPLIB benchmark.[4] This lead has been maintained for all releases of Octeract Engine hence.

As of August 2022 it is the first and only solver to solve the largest open transmission switching problems in the industry standard MINLPLIB[1] library, namely transswitch2736spp[5] and transswitch2736spr.[6]

World records

[edit]

Octeract Engine currently holds two world records in MINLP benchmarks.[2] The first world record, set on 20 April 2023, is in number of problems solved (100%). The second world record, also set on 20 April 2023, is the smallest unscaled shifted geometric mean[7] ever achieved for this test set, which was 36.8. The runner-ups achieved means of 138.2 (BARON) and 380.5 (SCIP), with Couenne ranking last with a mean of 3304.4.

World record history

[edit]

On 27 October 2022 Octeract Engine set its first world record by solving more 91% of problems in the benchmark, which was more than any solver had ever been able to solve by that time. This record has yet to be broken by any other solver as of 21 April 2023.

In January 2023, it became the first solver to solve 99% of problems in this benchmark.

In April 2023, it became the first solver to solve 100% of problems in this benchmark.

Features

[edit]

Octeract Engine is a suite of numerous solvers and techniques which are invoked automatically, or at the user's discretion. It features parallel branch-and-bound solvers, numerous local heuristics which can be invoked independently of global optimization, as well as numerous specialized techniques to exploit special structure, such as the Sherali-Smith reformulation.[8][9][10]

Other notable features include: [10]

  • Distributed computing through MPI
  • High degree of configurability with more than 100 options
  • Supports discontinuous elementary functions (e.g. min and max)
  • Supports trigonometric functions
  • Can guarantee global optimality
  • Reformulation of user input
  • Detection of special structure
  • Automatic problem classification
  • Guaranteed calculations through interval arithmetic and arbitrary-precision arithmetic
  • Powerful local solver capabilities through its LOCAL_SEARCH [11] mode

File formats

[edit]

Octeract Engine can read and write .nl, .lp and .mps files.

Interfaces

[edit]

Octeract Engine can be run directly or invoked as a C++ library. It supports the following modelling languages:[10]

The engine also interfaces to the following solvers:

See also

[edit]

References

[edit]
  1. ^ a b "A Library of Mixed-Integer and Continuous Nonlinear Programming Instances". Minlplib. 2022-10-14. Retrieved 2023-01-27.
  2. ^ a b "Visualisation of Mittelmann Benchmark". mattmilten.github.io. Matthias Miltenberger. Retrieved 20 April 2023.
  3. ^ "Octeract Credits". octeract.gg. Octeract. Retrieved 27 January 2023.
  4. ^ "Visualisation of Mittelmann Benchmark". mattmilten.github.io. Matthias Miltenberger. Retrieved 20 April 2023.
  5. ^ "Transswitch2736spp solution". minlplib.org. MINLPLIB. Retrieved 27 January 2023.
  6. ^ "Transswitch2736spr solution". minlplib.org. MINLPLIB. Retrieved 27 January 2023.
  7. ^ "Shifted Geometric Mean". plato.asu.edu. Hans Mittelmann. Retrieved 21 April 2023.
  8. ^ "BQP Reformulation Procedure". octeract.gg. Octeract. Retrieved 27 January 2023.
  9. ^ Sherali, Hanif D.; Smith, J. Cole (2006). "An improved linearization strategy for zero-one quadratic programming problems". Optimization Letters. 1 (1): 33–47. doi:10.1007/s11590-006-0019-0.
  10. ^ a b c "Octeract Engine documentation". octeract.gg. Octeract. Retrieved 27 January 2023.
  11. ^ "Local Search". octeract.gg. Octeract. Retrieved 21 April 2023.