User Manual for Octeract Engine

explanation   practical insight   user manual  

1. Introduction
1.1 Solver Highlights
2. Solving your First Problem
2.1 Using the Command Line Interface
2.2 Using Python
2.3 Using C++
3. Solver Flags
3.1 Input Flags
3.2 Exit Flags
4. Solver Options
5. Running in Parallel Mode Using MPI
5.1 Running on a Single Machine
5.2 Running on a Computer Cluster




1. Introduction

Octeract Engine is a Deterministic Global Optimisation (DGO) solver which solves general nonlinear problems to guaranteed global optimality. The general mathematical description is encapsulated in problem \(P\):

\begin{align} P : \min_{\substack{ x\in X \\y\in Y }} &f(x,y)\\ \textrm{s.t. } &g(x,y)\leq \ 0 \nonumber\\ &h(x,y)=\ 0 \nonumber \\ &X=[\ x^L,\ x^U]\subset\mathbb{R}^n \nonumber \\ &Y=\{0,1\}\nonumber \end{align}
The solver can solve any nonlinear function to global optimality, as long as that function has an analytical form that does not include differential expressions or integrals. For instance,
\begin{equation} \underset{x\in[-1,1]}\min\sqrt{x}\nonumber,\;\;\; \underset{x\in[-1,1]}\min\Big|-\log(\frac{1}{\tan(x)^{0.85}})\Big|,\;\;\; \underset{x\in[-1,1]}\min\sqrt{\max(x^{-1/2},1)}\nonumber,\;\;\; \nonumber \end{equation} are valid inputs, whereas:
\begin{equation} \underset{x\in[-1,1]}\min \Gamma{(x)}\nonumber \nonumber \end{equation} is not valid input because the expression for the Gamma function is an integral.

Note

Two important exceptions to the analytical expression rule are \(min(f(x),g(x)\) and \(max(f(x),g(x)\), which are fully supported.

1.1 Solver Highlights

No starting points
Users do not need to define starting points when using Octeract Engine. The solver will locate feasible solutions automatically as part of its branch-and-bound search.

Guaranteed calculations
Octeract Engine uses a combination of Interval Arithmetic and Arbitrary Precision Arithmetic to guarantee the correctness of all internal calculations. The combination of these two paradigms enables the solver to handle extremely challenging numerics. This is very important in Deterministic Global Optimisation, as our algorithms are always at risk of incorrectly eliminating the global solution due to bad floating-point calculations. However, Octeract Engine relies on third-party solvers in order to solve NLP and LP subproblems, meaning that it is possible for the solver to return an incorrect result due to numerical error from third-party software. In the majority of cases, the solver compensates for such errors using conservative tolerances for external calculations, but it is important for users to be aware that the end result is still subject to third-party floating-point errors.

Symbolic engine
Octeract Engine comes equipped with a full-fledged symbolic engine designed for optimisation mathematics, which allows it to perform symbolic manipulation of user input to an unprecedented degree.

Octeract Reformulator

The Octeract symbolic engine for optimisation math is a standalone product, a.k.a. the Octeract Reformulator. The Reformulator is an extremely flexible tool which allows users to script complicated reformulations, create reformulation libraries and apply the same reformulations to other problems, or to share them with collaborators. Octeract Engine is equipped with a special version of the Reformulator, tuned for global optimisation problems.
Because of the Reformulator, users should never need to reformulate their problems manually to make them solvable by Octeract Engine – the solver handles bad math automatically.

Accessible parallelism
Octeract Engine can be run in parallel using MPI out of the box, for single machines and computing clusters alike.

2. Solving your First Problem

2.1 Using the Command Line Interface

The solver can be invoked from Windows PowerShell or Linux terminal using the following syntax:
                
octeract-engine [problem_file]
                
            
The solver supports direct input in ASL (.nl), MPS (.mps), and LP (.lp) formats. It also has built-in support for the Pyomo and AMPL modeling environments. Example input files are included in the installation folder under examples. Let’s begin by solving test problem ex2_1_1.nl.
Invoke the solver using the following command:
                
octeract-engine ex2_1_1.nl
                
            
You should see the following output:
                
-----------------------------------------------------------------------------------------------
Iteration            GAP               LLB          BUB        Pool      Time     Mem
-----------------------------------------------------------------------------------------------
11           5.000e-11 (  0.00%)   -1.700e+01     -1.700e+01    3      0.0s    91.0MB

Objective value at global solution: -1.700e+01
                
            
By default, the solver outputs the following information:
  • Number of iterations (in this case 11).
  • Absolute and relative optimality gap (here \(5x10^{−11}\) and 0.00% respectively).
  • Least Lower Bound (LLB). This is the smallest lower bound throughout the branch-and-bound tree.
  • Best Upper Bound (BUB). This is the best local optimum that has been located so far.
  • Pool. This is the number of nodes in the branching pool.
  • Time. This is the real time (not CPU time) spent in branch-and-bound (in seconds).
  • Memory. The amount of RAM that the solver is currently taking up.

By default, the solver will automatically write an .octsol solution file to the system’s LOCAL_TEMP. This directory can be set explicitly (overridden) using the -s flag:
                
octeract-engine ex2_1_1.nl -s MY_SOLUTION_PATH
                
            
Detailed solution information can be accessed by inspecting the solution file which produces the following output:
                
=========================================
***************  Solution  ***************
========================================
- Local Engine      : ipopt
- Local Eng. Status : 0
- Feasible          : Yes
- Problem type      : UB
- Found in node     : 20
- Objective value   : -16.9999999999499778
- Model name        : ex2_1_1
- Problem structure : QP
- DGO exit status   : Solved_To_Global_Optimality
- Solving time (s)  : 0.078000
- Nu cores          : 1
- nu vars             : 5
* nu nlvars         : 5
* nu linear vars    : 0
* nu binary vars    : 0
- nu cons              : 1
* nu linear cons     : 1
* nu fixed cons      : 0
* nu quadratic cons  : 0
* nu general nl cons : 0
- Solution vector :
x1	: 0.9999999999998276
x2	: 0.9999999999998215
x3	: 0.0000000000002222
x4	: 0.9999999999998114
x5	: 0.0000000000002105
- Lagrange multipliers :
con1	: 0.0000000000099999
x1	: -57.9999999999529479
x2	: -56.0000000000025153
x3	: 45.0000000009757386
x4	: -53.0000000000258993
x5	: 47.5000000009467271
========================================
                
            

That’s it! Congratulations, you just solved your first problem using Octeract Engine!


2.2 Using Python

Check the Python API documentation for simple examples to get started.

2.3 Using C++

Check the C++ API documentation for simple examples to get started.



3. Solver Flags

3.1 Input Flags

The only mandatory argument for the octeract-engine executable is the model file. The executable also accepts the following optional arguments:

  • –help: Show help.
  • -o, –option: Location of a custom options file.
  • -s, –solution: Directory where solution files should be saved.
  • -t, –timeout: Solver timeout in seconds.
  • -n, –core: Number of MPI processes to be created (equivalent to number of CPU cores to use if n<=total_cores).
  • –hostfile: Location of the MPI hostfile (if running on a computer cluster).

3.2 Exit Flags

The solver can print the following exit status messages to the solution (.octsol) file upon termination:

  • Global_Solution_Status_Undefined
  • Solved_To_Global_Optimality
  • Proved_Global_Infeasibility
  • Found_Solution_For_CS_Problem (CS stands for constraint satisfaction)
  • Timeout_With_Feasible_Solution
  • Timeout_Without_Feasible_Solution
  • Interrupt_With_Feasible_Solution
  • Interrupt_Without_Feasible_Solution
  • Catastrophic_Error
  • Parsing_Error


4. Solver Options

The solver accepts custom options through a text file. By default, the solver will attempt to locate and read an options file octeract.opt in the current directory, but this can be overridden using the -o flag. All options are case-sensitive and are set using the following syntax:
                
OPTION_NAME = option_value
                
            
Click here to go to How to Set Options page.



5. Running in Parallel Mode Using MPI

The Message Passing Interface (MPI) is a framework for distributed computing, originally designed for use in supercomputers. Octeract Engine is distributed with MPI, and can be used in parallel mode out of the box.

5.1 Running on a Single Machine

The syntax to invoke MPI on a single machine is the following:
                
octeract-engine -n [number_of_processes] [problem_file]
                
            
The solver will now generate and run n processes in parallel. It is highly recommended to use at most as many processes as there are physical cores in your system.

5.2 Running on a Computer Cluster

Octeract Engine should run on any Linux cluster out of the box. The syntax to invoke MPI on a distributed architecture is very similar to single machine MPI mode:
                
octeract-engine -n [nu_processes] --hostfile [hostfile]
                
            
The hostfile is required by MPI, as it contains the IP addresses of all the machines that the solver can connect to. A sample hostfile could look like this:
                
10.200.300.01 : 32
10.200.300.02 : 8
10.200.300.45 : 2
10.200.300.32 : 12
                
            
This file contains two columns delimited by a colon. The IP addresses of the available machines are listed in the first column. In the second column, the user can optionally declare the maximum number of cores that can be used in each machine. If the column is ommited, then MPI will use all cores by default. In this example, the first machine is allowed to utilise up to 32 cores.

Note

Octeract Engine will spawn as many processes as the user requests on startup. If that number is smaller than all the processors specified in the hostfile, some machines will not be used at all.

man/man1002