Simple Solving: The Reformulator API

Python API
10 min read
#Label

The Octeract Reformulator is the ORL compiler that creates Octeract Engine. We’re exposing some of its powerful functionality to our users. Now anyone can code reusable reformulations in a few lines of Python.

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 reformulationsWhat’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:

The trigger command initiates the reformulation and sets out to find all terms with a square root
The action tracks this term throughout the model, adds the variable bounds and sets a linear constraint
Mod shows the modification to the model: the action and the substitution with the auxiliary variable
The rule simply states that if the trigger is true then take action with the modification

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

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:

only needs the pattern of a term; not the exact term – it identifies structure in a model
allows for the reusability of reformulations 
will run the code once and perform the action on every matched term in the model
allows for versatility and modeling flexibility – the user has the power of customisation 
provides a user-friendly environment with Python API
ensures that the user only need know a few lines of code to perform a reformulation
gives users free rein to apply any type of reformulation throughout a model, hassle-free

Leave a Reply

%d bloggers like this: