The Octeract Reformulator is the ORL compiler that creates Octeract Engine. As part of our initiative to make optimisation usable by a wider audience, we are gradually exposing more of its powerful functionality to our users. Now anyone can code reusable reformulations in a few lines of Python.

**Accelerate Solving: Reformulate**

**Accelerate Solving: Reformulate**

**The Reformulator has the power to save time.** How? It reformulates problems. A reformulation substitutes any mathematical structure with one that’s equivalent and simpler for an optimisation solver to handle. It’s even customisable so users can perform any transformation imaginable! This speeds up problem-solving, without compromising on accuracy. It also spares users the headache.**Performing a reformulation is as simple as typing a few lines of code.** Let’s take a look at an abstract example to get an idea of the basic formulation:

```
rule = SubTerm("sqrt(E(fun))", "aux_var",
AddVariableSpan("aux_var", \
"sqrt((fun))")+AddConstraint("con1",\
"aux_var**2-fun=0"))
m.apply_mod(rule)
```

**Method 1**

```
trigger = Match("C(n)*sqrt(E(fun))")
action = Track("sqrt(E(fun))", \
AddVariableSpan("aux_var", \
"sqrt((fun))")+AddConstraint("con1", \
"aux_var**2-fun=0"))
mod = action + SubWith("n*aux_var")
rule = trigger.then(mod)
m.apply_mod(rule)
```

**Method 2**

This example illustrates a reformulation of the problem in Problem** (1)** where backslashes show line breaks. Both methods shown above can achieve the change we see from Problem **(1)** to **(2)**. In other words, either method will reformulate all square roots in the original problem. This involves simply replacing the square root of the function with an auxiliary variable, defining its bounds, and adding a constraint.

Problem **(1)**

#### \begin{equation}

\begin{aligned}

& {\text{minimise}}

& & f(x) \\

& \text{subject to}

& & g_i(x) \leq a_i, \forall i \\

&&& h_j(x) = b_j, \forall j \\

&&& n_k\sqrt{s_k(x)} \leq c_k, \forall k \\

&&& x \in [\underline{x},\overline{x}]

\end{aligned}

\label{eq:original}

\end{equation}

Problem **(2)**

#### \begin{equation}

\begin{aligned}

& {\text{minimise}}

& & f(x) \\

& \text{subject to}

& & g_i(x) \leq a_i, \forall i \\

&&& h_j(x) = b_j, \forall j \\

&&& n_kz_k \leq c_k, \forall k \\

&&& z_k^2 – s_k(x) = 0, \forall k \\

&&& x \in [\underline{x},\bar{x}] \\

&&& z_k \in [\underline{z_k},\overline{z_k}]

\end{aligned}

\label{eq:reformulated}

\end{equation}

The terms \(\underline{z_k}\) and \(\overline{z_k}\) are interval bounds of the function \(\sqrt{s_k(x)}\), \(a_i\), \(b_j\), \(c_k\), \(n_k\) are constants.

**The user has the choice. **This new way of formulating optimisation problems allows users to sit in the driver’s seat. The format of terms in the reformulation is completely up to the user. One of the Reformulator’s signature moves is identifying structure so concern over specific names can go straight out the window. This also means that commands can be reused in different reformulations**. **What’s more, reformulations can be reused on different models thanks to the ORL.

**To perform this reformulation, there are a few commands we’ve used in Method 2.** Namely

trigger

action

mod

rule

These are not cast in stone – users can create custom commands to perform the tasks.** **This method gives the user a much higher degree of control over the reformulation. Each command completes a task:

**Method 1, on the other hand, keeps the reformulation basic.** This method uses the rule as a single command and applies the modification to the model. It assumes that the user wants to ignore any multipliers of the square root so the ORL will deal with them in default. Moral of the story: the Reformulator offers versatility should the user wish to exploit it.

**The Reformulator in Action**

**The Reformulator in Action**

**Let’s now unpack a more complex example.** Assume that we have an optimisation problem, m, loaded in the Octeract Shell. The problem is shown in below (Problem **(3)**):

#### \begin{equation}

\begin{aligned}

& {\text{minimize}}

& & x_1^3 – x_2^2 + 3x_1x_2 + 5x_3x_4 \\

& \text{subject to}

& & 2\log(x_1^2+3x_1x_2-x_2^2) \leq 10 \\&&&-3\log(-x_1^2+3x_1x_2+x_2^2) \geq -15 \\

&&& 5x_1x_3 <= 45 \\

&&& 5x_2x_4 <= 45 \\

&&& x_1x_2 <= 40 \\

&&& x_1,x_2 \in [-10,10] \\

&&& x_3,x_4 \in \{0,1\}\

\end{aligned}

\label{eq:example_original}

\end{equation}

**There are a few complex terms that make solving this form of the problem an uphill battle.** Specifically, the bilinear binary term in the objective function as well as the bilinear continuous binary and the logarithmic terms found in the constraints. In its current state, this model is solved by Octeract Engine in 97 iterations with an optimality gap of 0.02%. To make the problem simpler to solve, there are three types of exact reformulations that we can perform.

### Bilinear Binary Term Reformulation

**The first reformulation we will perform is that of the bilinear binary term.** This will substitute every bilinear binary term in the model with a single auxiliary variable, w_yy. In this reformulation, we use a filters command. This ensures that we keep the original bilinear variable definition i.e the variables are binary. The action tracks this term and adds the auxiliary variable as well as three linear constraints. These constraints replace the bilinearity functionality in the model. This reformulation rule states that if both the trigger and filters are true then the modification is actioned.

```
trigger = Match('C(n)*V(y1)*V(y2)')
filters = (IsBinary('y1') & IsBinary('y2'))
action = Track('V(y1)*V(y2)',AddBinaryVariable('w_yy') \
+AddConstraint('con1','y1+y2-w_yy-1<=0') \
+AddConstraint('con2','w_yy-y1<=0') \
+AddConstraint('con3','w_yy-y2<=0'))
mod = action + SubWith('n*w_yy')
rule = (trigger & filters).then(mod)
m.apply_mod(rule)
```

### Bilinear Continuous Binary Term Reformulation

**This reformulation will replace every bilinear continuous binary term with the defined auxiliary variable.** Once again, we use the filters command to maintain the original variable definitions i.e. x is continuous and y is binary. The action tracks this term in the model, defines parameters for the continuous variable and adds a minimum for the auxiliary variable. This command also adds new constraints to the model which include the newly defined parameters of the continuous variable in the term. These constraints will substitute the bilinear functionality. The rule here is similar to the previous reformulation in that both the trigger and filters need to hold true before the modification gets the go-ahead.

```
trigger = Match('C(n)*V(x)*V(y)')
filters = (∼IsBinary('x') & IsBinary('y'))
action = Track('V(x)*V(y)', AddParameter('x_LB','x','lb') \
+AddParameter('x_UB','x','ub') +AddVariableMin('w_xy',0) \
+AddConstraint('con1','w_xy-x_UB+x_LB<=0') \
+AddConstraint('con2','w_xy-(x_UB-x_LB)*y<=0') \
+AddConstraint('con3','w_xy-x+x_LB<=0') \
+AddConstraint('con4','x-w_xy-(1-y)*x_UB-y*x_LB<=0'))
mod = action + SubWith('n*(w_xy+y*x_LB)')
rule2 = (trigger & filters).then(mod)
m.apply_mod(rule2)
```

### Logarithmic Term Reformulation

**The third and final reformulation is of the logarithmic term.** This reformulation simply finds all the logarithmic terms in the model and substitutes them with an auxiliary variable, w_log. The action tracks the term and adds variable bounds. It also adds a linear constraint that will substitute the logarithmic functionality. This action replaces finding the bounds manually, which we know is a real pain in the neck. The rule for this reformulation simply gives the instruction that if the trigger is true then the modification should be actioned on the model.

```
trigger = Match('C(n)*log(E(f))')
action = Track('log(E(f))', AddVariableSpan('w_log', 'log(E(f))') \
+AddConstraint('con1','f-exp(w_log)==0'))
mod = action + SubWith('n*w_log')
rule3 = trigger.then(mod)
m.apply_mod(rule3)
```

### The Final Model

**After performing the reformulations, the model is now easier to solve than the ****original problem****. ** Let’s take a look at the summary of the reformulated problem compared to that of the original problem:

```
==========================================
**************** Problem ***************
Problem structure : MINLP
Is convex? : no
Total # variables : 4
-- continuous : 2
-- binary : 2
-- integer : 0
Total # constraints : 5
-- linear : 0
-- nonlinear : 5
==========================================
```

**The Original Problem**

```
==========================================
**************** Problem ***************
Problem structure : MINLP
Is convex? : no
Total # variables : 9
-- continuous : 6
-- binary : 3
-- integer : 0
Total # constraints : 18
-- linear : 15
-- nonlinear : 3
==========================================
```

**The Reformulated Problem**

In the final instance of the model, there are 5 extra auxiliary variables, 15 linear constraints, and 3 non-linear constraints. Each reformulation has contributed to the simplification of the problem. It might be tricky to see how each mathematical manipulation had a hand in this (it’s not unlike magic). So, here are the specific modifications to the model with each reformulation:

The Reformulator has given the problem a new lease on life. Now, this form of the problem can easily be tackled by an optimisation solver.

### Time to Solve

**Solving the reformulated problem is a breeze for Octeract Engine. **Let’s take a look at the solution to the original problem compared to that of the final reformulation.

```
==================================================
******************** Solution ********************
==================================================
- Local Engine : fixing heuristic
- Local Eng. Status : 0
- Feasible : Yes
- Problem type : UB
- Found in node : 191
- Objective value : -671.63645780051331257710
- Model name : post model
- Problem structure : MINLP
- DGO exit status : Solved To Global Optimality
- Solving time (s) : 1.319000
```

**Solution of the original problem**

```
===================================================
******************** Solution ********************
===================================================
- Local Engine : fixing heuristic
- Local Eng. Status : 0
- Feasible : Yes
- Problem type : UB
- Found in node : 8
- Objective value : -671.69745824716619608807
- Model name : test
- Problem structure : MINLP
- DGO exit status : Solved To Global Optimality
- Solving time (s) : 0.100000
```

**Solution of the final reformulation**

The model is now solved by Octeract Engine in 7 iterations with an optimality gap of 0.09%. In comparison, the solution of the original problem is found in node 191 while the solution of the reformulated problem is located in node 8. Hence, the significant reduction in the number of iterations. There’s also a notable difference in the time to solve. The solution of the final reformulation is found approximately thirteen times faster than that of the original problem.

**Before we close the chapter on this example, it’s important to note that all problem formulations are mathematically equivalent.** This is due to the fact that the reformulations we’ve applied are exact. Therefore, the initial information of the problem is maintained so the final solution is the same here. We just get to it faster and more seamlessly with the Reformulator. Once again, the user has the control and can structure a reformulation as they see fit.

**The Value**

**The power of the Octeract Reformulator speaks for itself.** This technology transforms optimisation problems so they can be solved more easily. As shown above, this involves replacing some element/s in the model to make it/them linear. Manually, we know this process is time-consuming, complex, and prone to human error. When it comes to the value of this technology, there’s a lot to digest.

So, to summarise, the Reformulator: