fbpx

How to NOT Reformulate a Problem that includes the min() Function

problem
7 min read

If you have a model with a min() function, you might be thinking that it can’t be directly solved. Think again.

This type of problem-solving can be achieved with Octeract Engine. In fact, the Engine prides itself on being able to solve such problems out of the box. Let’s take a look at an example.

The Math

The Original Problem

The type of problem in question looks like the one below:


minimise \(log(x_1)x_2^2+x_2x_1^2\)
subject to \(2x_1+3x_2=\) min\((x_1,x_2)+9\),
\(2.9 \le x_1 \le10,1 \le x_2 \le10\)

Unfortunately, this type of problem cannot be automatically handled by most global MINLP solvers.

So, in order to find the global optimum, optimisation experts have been reformulating the min() function using either the absolute (abs) value function which can be handled by these solvers or by using binary variables.

The Reformulated Problem

In the reformulated problem where the abs() function is used, one would have to replace min\((x_1, x_2)\) with an equivalent expression that does not include the min() function. This is one of the most widely used:

min\((x_1, x_2) = \frac{x_1 + x_2 – |x_1 – x_2|}{2}\)

With this in mind, the reformulated problem would look like this:

minimise \(log(x_1)x_2^2+x_2x_1^2\)
subject to \(2x_1+3x_2= \frac{x_1 + x_2 – |x_1 – x_2|}{2} +9\),
\(2.9 \le x_1 \le10,1 \le x_2 \le10\)

Reformulating this type of problem is a necessity. Until now.

Enter Octeract Engine: the MINLP solver that solves this problem as is, out of the box. Want to know how? Read more here.

Let’s take the original problem and solve it with the Engine, step by step:

The Model

Step 1: Write the model in Python

If you’re unfamiliar with using Python for your optimisation models, don’t fret! Just follow our easy guide and you’ll be up to speed. You can write your model in a text editor or in a Python application such as Jupyter. In any case, the Python model for the problem will look like this:

from octeract import *

#initiate a model object
m = Model()

#Add variables x1 and x2 and determine their bounds
m.add_variable("x1", 2.9, 10)
m.add_variable("x2", 1, 10)

#Set the objective function that we want to minimise
m.set_objective("log(x1)*x2**2 + x2*x1**2", MINIMIZE)

#Add the constraint
m.add_constraint("2*x1 + 3*x2 - min(x1, x2) + (-9) = 0")

#Print the model
print(m)

#Solve the model using Octeract Engine and 4 cores
m.global_solve(4);

Step 2: Save the file

If you’ve written the model in text editor, save it as a .py file. Alternatively, if you’ve used Jupyter, or something similar, you can just run the problem as we do in Step 3 below.

Step 3: Run the model

Now we need to run the file. To do this, open a PowerShell or a Shell session and type: 

python file_name.py

In our case, we would type the following:

python Users\Octeract\Desktop\min_example.py

As we mentioned before, if you’ve used another means such as Jupyter, you can run the script directly.  In both cases, the problem will be solved in less than a second.

Once you’ve written, saved, and run the model, the output you’ll get will look something like this:

========================================
 Octeract Engine v1.07.29    
 Copyright (c) Octeract Ltd, 2020
========================================

-----------------------------------------------------------------------------------------
 Iteration            GAP               LLB          BUB            Pool      Time     Mem  
-----------------------------------------------------------------------------------------
         0    2.210e-08 (  0.00%)    1.350e+01    1.350e+01            0      0.1s    26.0MB

Objective value at global solution:  1.350e+01
Solved_To_Global_Optimality

Total time : 0.12s

As you can see, the Engine doesn’t waste time. It automatically solves the model in the blink of an eye. Impressed with what you’ve just achieved with the Engine? There’s more where that came from. Octeract Engine’s ability to solve the min() function, without requiring ANY reformulation from the user, does not stop here. There’s a lot more magic you can do.

Scroll down to see more examples and give yourself a bit of a challenge.

1. Min(ax, by)

Let’s increase the complexity of the function, just a notch. This is no problem for the Engine! For the case of min(ax, by), we add the constants 3 and 2 as multipliers of \(x_1\) and \(x_2\) respectively in the min() function. The Python model will now look like what you see below:

from octeract import *

#initiate a model object
m = Model()

#Add variables x1 and x2 and determine their bounds
m.add_variable("x1", 2.9, 10)
m.add_variable("x2", 1, 10)

#Set the objective function that we want to minimise
m.set_objective("log(x1)*x2**2 + x2*x1**2", MINIMIZE)

#Add the constraint
m.add_constraint("2*x1 + 3*x2 - min(3*x1, 2*x2) + (-9) = 0")

#Print the model
print(m)

#Solve the model using Octeract Engine and 4 cores
m.global_solve(4);

Once again, the Engine makes light work of the problem. After the problem is solved, the solution that’s printed is shown in the snippet below:


========================================
 Octeract Engine v1.07.29    
 Copyright (c) Octeract Ltd, 2020
========================================

-----------------------------------------------------------------------------------------
 Iteration            GAP               LLB          BUB            Pool      Time     Mem  
-----------------------------------------------------------------------------------------
         0    2.579e-01 (  1.51%)    1.713e+01    1.739e+01            0      0.1s    26.0MB
        55    5.572e-09 (  0.00%)    1.739e+01    1.739e+01            0      0.1s    26.0MB

Objective value at global solution:  1.739e+01
Solved_To_Global_Optimality

Total time : 0.12s

2. Max(x,y)

Apart from handling the minimum function out of the box, Octeract Engine does the same for the maximum function. Yes, the Engine is an all-rounder. For a simple case of max(x, y), the Python model will look like what you see below:


from octeract import *

#initiate a model object
m = Model()

#Add variables x1 and x2 and determine their bounds
m.add_variable("x1", 2.9, 10)
m.add_variable("x2", 1, 10)

#Set the objective function that we want to minimise
m.set_objective("log(x1)*x2**2 + x2*x1**2", MINIMIZE)

#Add the constraint
m.add_constraint("2*x1 + 3*x2 - max(x1, x2) + (-9) = 0")

#Print the model
print(m)

#Solve the model using Octeract Engine and 4 cores
m.global_solve(4);

The Engine takes this problem and solves it as is. No reformulations or manipulations needed. After the problem is solved, the solution is printed. You can see what this will look like in the code block below:

========================================
 Octeract Engine v1.07.29    
 Copyright (c) Octeract Ltd, 2020
========================================

-----------------------------------------------------------------------------------------
 Iteration            GAP               LLB          BUB            Pool      Time     Mem  
-----------------------------------------------------------------------------------------
         0    3.495e-05 (  0.00%)    2.150e+01    2.150e+01            0      0.1s    26.0MB

Objective value at global solution:  2.150e+01
Solved_To_Global_Optimality

Total time : 0.10s

3. Max(ax, by)

In a similar way to dealing with the min(ax, by), the Engine goes about its business of solving the case of max(ax, by). As can be seen, the constants 10 and 2 have been added as multipliers to \(x_1\) and \(x_2\) in the min() function. The Python model will now look like what you see below:

from octeract import *

#initiate a model object
m = Model()

#Add variables x1 and x2 and determine their bounds
m.add_variable("x1", 2.9, 10)
m.add_variable("x2", 1, 10)

#Set the objective function that we want to minimise
m.set_objective("log(x1)*x2**2 + x2*x1**2", MINIMIZE)

#Add the constraint
m.add_constraint("2*x1 + 3*x2 - max(10*x1, 2*x2) + (-9) = 0")

#Print the model
print(m)

#Solve the model using Octeract Engine and 4 cores
m.global_solve(4);

The snippet below shows the output printed by the Engine:

========================================
 Octeract Engine v1.07.29    
 Copyright (c) Octeract Ltd, 2020
========================================

Loading problem...
Preprocessing problem... 100% complete

Input problem is infeasible.

Presolve time : 0.00s

Proved_Global_Infeasibility

Total time : 0.01s

As is evident from the snippet above, the problem is infeasible. Proving infeasibility is just another one of Octeract Engine’s superpowers!

4. Max(f(x), g(y))

It’s time for some real complexity. Now, this is a challenge worthy of the Engine! This modification of the original problem sees the inclusion of functions within the max() function. For the case of max(f(x), g(y)), where f(x) and g(y) are functions of x and y respectively, the Python model now looks like what you see below:

from octeract import *

#initiate a model object
m = Model()

#Add variables x1 and x2 and determine their bounds
m.add_variable("x1", 2.9, 10)
m.add_variable("x2", 1, 10)

#Set the objective function that we want to minimise
m.set_objective("log(x1)*x2**2 + x2*x1**2", MINIMIZE)

#Add the constraint
m.add_constraint("2*x1 + 3*x2 - max(log(x1), sqrt(x2)) + (-9) = 0")

#Print the model
print(m)

#Solve the model using Octeract Engine and 4 cores
m.global_solve(4);

The solution printed after the problem is solved is the following:

========================================
 Octeract Engine v1.07.29    
 Copyright (c) Octeract Ltd, 2020
========================================

-----------------------------------------------------------------------------------------
 Iteration            GAP               LLB          BUB            Pool      Time     Mem  
-----------------------------------------------------------------------------------------
         0    5.863e-01 (  4.16%)    1.409e+01    1.467e+01            0      0.5s    26.0MB
      8733    5.863e-01 (  4.16%)    1.409e+01    1.467e+01            2      1.1s    26.0MB
     15192    5.863e-01 (  4.16%)    1.409e+01    1.467e+01            2      2.1s    26.0MB
     20761    5.863e-01 (  4.16%)    1.409e+01    1.467e+01            2      3.1s    26.0MB


     24360    1.392e-02 (  0.10%)    1.457e+01    1.459e+01            0      3.6s    26.0MB

Objective value at global solution:  1.459e+01
Solved_To_Global_Optimality

Total time: 5.56s

The Engine seamlessly solves this problem without any simplification from the user. In less than 6 seconds! That is some serious power.

There you have it! The Engine has been put to the test and doesn’t disappoint. It has the ability to automatically solve the min() function, as well as variations of it, out of the box. The dream of no longer toiling over manual manipulations is now a reality!

Leave a Reply