fbpx

User Manual

Manual

Octeract Engine v3.1.0
Copyright (c) Octeract Ltd, 2017-2021
June 21, 2021

Table Of Contents

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.