**Octeract Engine v3.1.0**

Copyright (c) Octeract Ltd, 2017-2021

June 21, 2021

Copyright (c) Octeract Ltd, 2017-2021

June 21, 2021

**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. Check out \cref{sec:mpimode} for a detailed overview.

**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 ouput:

```
-----------------------------------------------------------------------------------------------
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 \(5\text{x}10^{-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`

For instance, USE_OBBT = true will set that option to true. An example custom options file would look like the following:

```
# MY OPTIONS FILE
CONVERGENCE_TOLERANCE = 1.e-1
INFINITY = 1.e6
MAX_SOLVER_TIME = 60
USE_OBBT = false
```

### 4.1 Convergence Settings

`MAX_SOLVER_ITERATIONS`

This sets the maximum number of solver iterations **in serial mode** (this option is ignored in parallel mode).

Type: integer

Default value: 2.e9

Range: [1 – 2.e9]

`MAX_SOLVER_TIME`

This sets a timeout for the solver in seconds (elapsed real time).

Type: integer

Default value: 2.e9

Range: [1 – 2.e9]

`CONVERGENCE_TOLERANCE`

This sets a tolerance \(epsilon\) to determine whether the algorithm has converged to global optimality. The solver will terminate if either of the following conditions is satisfied:

- \(BUB – LLB \leq \epsilon \) (an absolute optimality gap)
- \( (BUB – LLB) \leq \epsilon |LLB| \)
**and**\( (BUB – LLB) <= \epsilon |BUB| \) (a relative optimality gap)

Type: double

Default value: 1.e-3

Range: [1 – 1.e308]

### 4.2 Domain Reduction

`USE_OBBT`

Enables or disables optimality-based bounds tightening (OBBT). OBBT is one of the most effective methods for reducing variable domains but can be computationally expensive. Recommended for small to mid-size problems. If running in parallel mode with significant computing power, OBBT becomes viable for large problems as well.

Type : bool

Default Value: true

Available options: true, false

`CP_VOLUME_IMPROVEMENT_FACTOR`

This sets the required volume improvement factor for iterations of constraint propagation. Constraint propagation will stop if it can’t achieve this improvement at a given iteration.

Type : double

Default Value: 0.999

Range: [0 – 1]

`MAX_OBBT_DEPTH`

Sets the maximum depth in the branch-and-bound tree to apply OBBT.

Type : int

Default Value: 2.e9

Range: 0 – 2.e9

### 4.3 General Solver Settings

`APPLY_CB`

This enables or disables constraint probing for domain reduction.

Type: bool

Default Value: false

Available options: true, false

`BINARY_REFORMULATION_PROCEDURE`

If REFORMULATE_BINARIES is enabled, this option determines which method to use in the reformulation of binary variables.

Type: string

Default Value: Quadratic_Concave_Constraint

Available options: Quadratic_Concave_Constraint, Quadratic_Equality_Constraint, Exponential_Reformulation.

`CUT_POOL_MAX_SIZE`

This sets the maximum number of cuts to be kept in the cut pool.

Type: integer

Default Value: 100000

Range: [0 – 1.e308]

`FORCE_EXPANSION`

If this option is enabled and USE_AUTOMATIC_EXPANSION is disabled, the Engine will solve the expanded version of your original problem.

Type: bool

Default Value: false

Range: true, false

`INTEGER_REFORMULATION_VAR_RANGE_LIMIT`

This sets the maximum bound difference for integer variables in IQP and IQCQP for which integer reformulation is to be applied. This is to avoid creating huge problems with poor accuracy and numerical issues.

Type: double

Default Value: 5000

Range: [0 – 100000]

`IS_PURGE_CUTS_ENABLED`

The option allows flagging for purging cuts. This is for cut management purposes.

Type: bool

Default Value: true

Available options: true, false

`MAX_CB_DEPTH`

This sets the maximum depth in the branching tree at which constraint probing should be adding additional constraints. If this is set to 0, depth is unlimited.

Type: integer

Default Value: 1

Range: [0 – 1.e308]

`MAX_SOLVER_MEMORY`

This option sets the memory limit allowed during the solving process, i.e., if the memory used exceeds this limit the solving process is terminated.

Type: double

Default Value: 2.e9

Range: [0 – 2.e9]

`MINLP_DIVING`

This enables or disables the diving heuristic for finding better upper bounds (UBs) for mixed-integer nonlinear programming (MINLP) problems.

Type: bool

Default Value: true

Available options: true, false

`OUTPUT_FREQUENCY`

The solver will print output every OUTPUT_FREQUENCY iterations.

Type: integer

Default value: 2.e9

Range: [1 – 2.e9]

`OUTPUT_TIME_FREQUENCY`

The solver will print output every OUTPUT_TIME_FREQUENCY seconds.

Type : integer

Default Value: 1

Range: [1 – 2.e9]

`PARALLEL_NODE_PROCESSING`

This option enables or disables parallel node processing for the branch and bound algorithm.

Type : bool

Default Value: true

Available options: true, false

`PARALLEL_PREPROCESSOR`

This option enables or disables certain preprocessing steps that are performed in parallel.

Type : bool

Default Value: false

Available options: true, false

`REFORMULATE_BINARIES`

This enables or disables the reformulation of binary variables. In particular, it replaces the binary requirement for a variable by adding a set of equivalent constraints according to the option BINARY_REFORMULATOR_PROCEDURE.

Type : bool

Default Value: false

Available options: true, false

`REFORMULATE_INTEGERS_IN_MIQCQCP`

This enables or disables the reformulation of integer variables as binary in Integer Quadratic Problems (IQP) and Integer Quadratically Constrained Quadratic Problems (IQCQP).

Type : string

Default Value: Logarithmic_Sum

Available options: Logarithmic_Sum, Linear_Sum

`REFORMULATE_INTEGERS`

This enables or disables the reformulation of integer variables as binary.

Type : bool

Default Value: false

Available options: true, false

`USE_AUTOMATIC_EXPANSION`

This enables or disables the use of expansion for mathematical expressions in your problem. If enabled, an alternative expanded version of your problem would be created where functions like \((x-2)^2\) will be replaced by \(x^2-4x+4\). The Engine will then select the most promising model to solve between the original (unexpanded) and alternative (expanded) version.

Type : bool

Default Value: true

Available options: true, false

`USE_CONVEXITY_CUTS`

This enables or disables the use of convexity cuts.

Type : bool

Default Value: true

Available options: true, false

`USE_FACTORABLE_REFORMULATION`

This enables or disables factorisation of the problem, i.e. recursively substituting nested expressions with auxiliary variables.

Type : bool

Default Value: true

Available options: true, false

`USE_FEASIBILITY_GENERATOR`

This option enables or disables the feasibility generator heuristic.

Type : bool

Default Value: false

Available options: true, false

`USE_GUIDED_DIVING`

This enables or disables the guided diving heuristic.

Type : bool

Default Value: false

Available options: true, false

`USE_MINLP_CUTS`

This option enables or disables the use of cuts in the branch and cut algorithm for mixed-integer nonlinear programming (MINLP) problems.

Type : bool

Default Value: false

Available options: true, false

`USE_MIP_CUTS`

This enables or disables the use of cuts in a branch and cut fashion when USE_OCTERACT_MILP is enabled for mixed-integer programming (MIP) problems.

Type : bool

Default Value: false

Available options: true, false

`USE_MIP_RELAXATION_CUTS`

This enables or disables the use of mixed-integer programming (MIP) cuts for relaxations of mixed-integer nonlinear programming (MINLP) problems.

Type : bool

Default Value: false

Available options: true, false

`USE_PROBING`

This enables or disables probing techniques for domain reduction.

Type : bool

Default Value: true

Available options: true, false

`USE_QPDIVING`

This option enables or disables the quadratic programming (QP) diving heuristic.

Type : bool

Default Value: true

Available options: true, false

`USE_REDUCED_COST`

This enables or disables the use of reduced costs to tighten variable domains.

Type : bool

Default Value: true

Available options: true, false

`USE_REFORMULATION_LINEARIZATION`

This option enables or disables the use of reformulation linearisation techniques to create new, valid constraints.

Type : bool

Default Value: true

Available options: true, false

`USE_SIMPLIFICATION`

Enables or disables standard reformulation rules that are applied to canonicalise the problem. This often results in a better relaxation.

Type : bool

Default Value: true

Available options: true, false

`USE_STRUCTURE_DETECTOR`

If enabled, problems with a linear objective of the form \(\min kx_i\) (\(k\) a constant), where \(x_i\) appears only in one constraint, and this constraint is linear, are reformulated. This reformulation happens by replacing the variable \(x_i\) in the objective function using the linear constraint if certain conditions are satisfied.

Type : bool

Default Value: true

Available options: true, false

`WARM_START_PATH`

This is the path to a solution file to be used for warm starting the solver (i.e., using the solution as the initial point when starting the solving algorithm)

Type : STRING

Default Value: (empty)

Available options: any valid path to a solution file

`PRESOLVE`

This simply enables or disables the presolver.

Type : bool

Default Value: true

Available options: true, false

`UB_FREQUENCY`

Sets how often the solver should solve local optimization problems to find upper bounds. Small values for this option can be helpful in problems where finding feasible upper bounds is challenging. For instance, UB_FREQUENCY = 1 will instruct the solver to calculate an upper bound on every node it processes, thus increasing the probability that a feasible solution is going to be located.

Type : int

Default Value: 4

Range: 1 – 2.e9

`PARALLEL_HEURISTICS`

This enables or disables the implementation of parallel heuristics to find the upper bound (UB) of a node.

Type : bool

Default Value: false

Available options: true, false

`PRINT_SOLUTION`

This sets whether to print the solution object on the screen or not, upon termination of the solver.

Type : bool

Default Value: false

Available options: true, false

`INFINITY`

This sets the default bound for unbounded variables. Global optimisation requires all variables to be bounded before the solving process begins. If you do not provide bounds for a variable, its bounds will be automatically set to ±INFINITY. The default value is quite conservative – reducing this number can greatly improve performance.

Type : double

Default Value: 1.e7

Range: [0 – 1.e308]

### 4.4 Third-party Solvers

`LP_SOLVER`

Sets the solver which will be used to solve linear problems.

Type : string

Default: OSICLP

Available options: IPOPT, OSICLP, OSICBC, CPLEX, GUROBI, XPRESS

`MILP_SOLVER`

This sets the solver which will be used to solve mixed-integer linear problems (MILP).

Type : string

Default Value: OSICBC

Available options: OSICBC, CPLEX, GUROBI, XPRESS

### 4.5 Tolerances

`BIG_GAP_TOLERANCE`

This option states that if the difference between a node’s upper bound and the parent’s lower bound is smaller than BIG_GAP_TOLERANCE, then solve the relaxation.

Type : double

Default Value: 1.e60

Range: [0 – 1.e308]

`BQP_SPARSITY_TOLERANCE`

The maximal sparsity for a binary quadratic problem (BQP) to be reformulated as a linear problem.

Type : double

Default Value: 0.8

Range: [0 – 1]

`BOUND_DIFF_FOR_INTEGER_REFORMULATION_IN_MIQCQP`

This option sets the maximum bound difference for integer variables in IQP and IQCQP, for which integer reformulation is to be applied. This is necessary to avoid creating huge problems with poor accuracy and numerical issues.

Type : double

Default Value: 5000

Range: [0 – 100000]

`BOUND_VIOLATION_TOLERANCE`

Bound violation tolerance is used to confirm whether solutions returned by third-party solvers are indeed feasible, within that tolerance. Relaxing this tolerance can help in problems where finding a feasible solution is difficult, or where the global solution is eliminated due to slight constraint violations.

Type : double

Default Value: 1.e-8

Range: [0 – 1.e308]

`INTEGRALITY_VIOLATION_TOLERANCE`

Integrality violation tolerance is the acceptable violation before the solver determines that a variable is no longer an integer. Relaxing this tolerance can prevent integer solutions from being fathomed due to small constraint violations.

Type : double

Default Value: 1.e-3

Range: [0 – 1.e308]

`CONSTRAINT_VIOLATION_TOLERANCE`

This tolerance determines the acceptable constraint violation when applying domain reduction techniques. Relaxing this tolerance can help in problems where finding a feasible solution is difficult, or where the global solution is eliminated due to slight constraint violations.

Type : double

Default Value: 1.e-6

Range: [0 – 1.e308]

`NUMBER_COMPARISON_TOLERANCE`

This tolerance is used to determine whether two floating point numbers are the same. Its use in the solver is context sensitive, as outward rounding is always used to ensure that solutions are not incorrectly eliminated. Making this tolerance smaller can accelerate convergence, as the solver becomes more aggressive in domain reduction. This, however, increases the risk of eliminating otherwise acceptable solutions. Relaxing this tolerance slows down convergence, as the solver adopts a more conservative approach.

Type : double

Default Value: 1.e-6

Range: [0 – 1.e308]

`LLB_TOLERANCE`

This tolerance is used to compare solutions of upper bounding problems and lower bounding problems. These two numbers are typically results of two separate local optimisation problems, potentially using two different third-party solvers. Therefore, they are prone to high numerical error. Tightening this tolerance can accelerate convergence, but it can increase the risk of eliminating the global solution due to error accumulation.

Type : double

Default Value: 1.e-3

Range: 0 – 1.e308

`BIG_COEFF_TOLERANCE`

Sets the maximum acceptable absolute value of a coefficient in the lower bounding problem. If a coefficient is greater than this number, the solver will use other, less effective methods instead of solving the lower bounding linear problem (LP). This option rarely needs to be changed because coefficients are naturally improved through branching. However, in rare cases where the problem is numerically well-behaved but has a large gap that is not closing, increasing this tolerance will force the solver to solve these ill-posed lower bounding problems.

Type : double

Default Value: 1.e9

Range: [0 – 1.e308]

### 4.6 Variable Branching

`BRANCHING_POLICY`

This option sets the technique to be used when branching over a variable (i.e., how to split the domain of the variable to generate children for a given parent node).

Type : string

Default Value: Multisection

Available options: Multisection, Bisection, Future, NoSplit, NoSplitMultisection, LBSolution

`STRONG_BRANCHING_VARIABLE_COUNT`

This option sets the (maximum) number of variables to consider for strong branching.

Type : integer

Default Value: 100

Available options: [0 – 2.e9]

`VARIABLE_SELECTION_HEURISTIC`

Sets which heuristic should be used to select branching variables in serial mode. The default is OS1, which is a lightweight strategy with good performance across the board. OS2-4 are increasingly more expensive strategies (with OS4 being the most expensive one), which can yield great results in small to mid-size problems.

Type : string

Default Value: OS1

Available options: OS1, OS2, OS3, OS4

**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.