External functions¶

External functions are a special feature of LocalSolver that allows you to create your own operators for your model. They have two main interests:

To create expressions that cannot be represented easily with the available catalog of operators of LocalSolver. For example, LocalSolver does not have a special operator for inverse trigonometric functions (such as arctan, arcsin or arccos). With external functions, you can create them provided that your coding language allows it. In fact, you can create almost any operator or function you want as long as it returns a valid integer or floating-point number, or an array of integer or floating numbers.
To reduce the size of your model. If you have many equivalent expressions, or a recurring pattern, you can replace it with an external function and reduce the number of expressions in the model and thus, reduce the memory footprint of LocalSolver and improve the global search performance.

Caution

Even if external functions are a really powerful and simple to use feature, you have to take care of the few pitfalls listed at the end of the document, especially the thread-safety issue.

Principles¶

External functions must be pure mathematical functions, which means:

The returned value must only depend on the input values: calling an external function with the same parameters must always returns the same value.
They should not have any side effects (some technical aspects such as reusing arrays or intermediate objects useful for internal calculations are nevertheless allowed).

Moreover, no assumption can be made as to when and on which parameters the solver will call the external function. This is because LocalSolver can explore the domain of the function independently of any solution. For example, the solver may call the function on some tentative assignment of values or precompute it for a certain number of input values.

To use external functions with your model, you have to proceed in 3 steps:

Create and code your function. The exact way depends on the targeting language (implementing an interface, using a delegate, etc.), but the main principle is the same: a list of arguments is provided to your code as input and it must return an integer or floating point number or an array of integer or floating numbers as output.
Instantiate your function and transform it to an LSExpression than can be made available to other expressions. At the end of this step, you will get an LSExpression of type O_ExternalFunction, that does not have a value by itself, but than can be used in O_Call expressions. You can optionally provide additional data about your function, such as a lower bound, an upper bound, and wether or not the function can return a NaN value. This is done by accessing and modifying the LSExternalContext of the function.
Pass arguments to your function and call it. For that, you have to create expressions of type O_Call. The first operand will be your external function created in step 2, and the other operands will be other LSExpressions. The values of these operands will be passed to your code/function during the search.

You can use external functions with the modeling language and all the languages supported by the API of LocalSolver (Python, C++, Java, .NET).

Example¶

In this example, we expose the inverse cosine function (also called arccosine) to our model, and we try to minimize a simple expression based on this new operator.

LSP
Python
C++
C#
Java

In LSP, the virtual machine does most of the job for you. Indeed, any function can be turned into a new operator with the special methods intExternalFunction, doubleExternalFunction, intArrayExternalFunction or doubleArrayExternalFunction (depending on the return type of the function).

Furthermore, the arguments provided in the O_Call expressions are simply exposed as arguments of the LSP function. Thus, in the example below, the value of the argument x + y is simply passed to the lsAcos function.

You can access the context of the function by addressing the field context of the function expression:

use math;

function model() {
    x <- float(-0.5, 0.5);
    y <- float(-0.5, 0.5);
    func <- doubleExternalFunction(lsAcos);
    func.context.lowerBound = 0.0;
    func.context.upperBound = math.pi;
    func.context.nanable = true;
    minimize call(func, x + y);
    constraint x + 3*y >= 0.75;
}

function lsAcos(val) {
    // math.acos is a function provided in the math module.
    return math.acos(val);
}

In Python, any function can be turned into a new operator provided that it takes a list of numbers and it returns an integer or double. To create a new external function, you can use create_int_external_function(), create_double_external_function(), create_int_array_external_function() or create_double_array_external_function() (depending on the return type of your function).

Then, you can use your function in CALL expressions. To create CALL expressions, you can use the generic method create_expression(), use the shortcut call() or use the specific overloaded __call__() operator on LSExpressions. Values of the arguments of your external function will be exposed through a LSExternalArgumentValues that can be seen as a read-only list.

You can access the LSExternalContext of the function with get_external_context() or the shortcut external_context:

import localsolver
import math

def lsAcos(arg_values):
    if arg_values[0] < -1 or arg_values[0] > 1: return float('nan')
    return math.acos(arg_values[0])

...
ls = localsolver.LocalSolver()
m = ls.model
func = m.create_double_external_function(lsAcos)
func.external_context.lower_bound = 0.0
func.external_context.upper_bound = math.pi
x = m.float(-0.5, 0.5)
y = m.float(-0.5, 0.5)
m.minimize(func(x + y))
m.constraint(x + 3*y >= 0.75)
...

In CPP, according to the type of your function, you have to extend the LSExternalFunction or LSArrayExternalFunction class and specifically the call method to implement your external function (step 1).

Then (step 2), you instantiate your function and turn it into an LSExpression with the createExternalFunction() method.

Finally (step 3), you can use your function in O_Call expressions. To create O_Call expressions, you can use the generic method createExpression(), the shortcut call() or use the specific overloaded operator()() on LSExpressions. Values of the arguments of your external function will be exposed through a LSExternalArgumentValues.

You can access the LSExternalContext of the function with getExternalContext():

#include <cmath>
#include <localsolver.h>
...

// Step 1: implement the external function
class LSArcCos : public LSExternalFunction<lsdouble> {
public:
    lsdouble call(const LSExternalArgumentValues& argumentValues) {
        return std::acos(argumentValues.getDoubleValue(0));
    }
}

LocalSolver ls;
LSModel m = ls.getModel();
LSArcCos acosCode;
// Step 2: Turn the external code into an LSExpression
LSExpression func = m.createExternalFunction(&acosCode);
func.getExternalContext().setLowerBound(0.0);
func.getExternalContext().setUpperBound(3.15);
LSExpression x = m.floatVar(-0.5, 0.5);
LSExpression y = m.floatVar(-0.5, 0.5);
// Step 3: Call the function
m.minimize(func(x + y));
m.constraint(x + 3*y >= 0.75);
...

In C#, the signature of external functions must conform to the delegates LSIntExternalFunction, LSDoubleExternalFunction, LSIntArrayExternalFunction or LSDoubleArrayExternalFunction that take a LSExternalArgumentValues instance and return an integer or a double value, or an array of integer or double numbers.

Then, you can use your function in Call expressions. To create Call expressions, you can use the generic method LSModel.CreateExpression or use the shortcut LSModel.Call. Values of the arguments of your external function will be exposed through a LSExternalArgumentValues.

You can access the LSExternalContext of the function with LSExpression.GetExternalContext:

using System.Math;
using localsolver;

...

double Acos(LSExternalArgumentValues argumentValues)
{
    return Math.Acos(argumentValues.GetDoubleValue(0));
}


void TestExternalFunction()
{
    LocalSolver ls = new LocalSolver();
    LSModel m = ls.GetModel();
    LSExpression func = m.CreateDoubleExternalFunction(Acos);
    func.GetExternalContext().SetLowerBound(0.0);
    func.GetExternalContext().SetUpperBound(Math.PI);
    LSExpression x = m.Float(-0.5, 0.5);
    LSExpression y = m.Float(-0.5, 0.5);
    m.Minimize(m.Call(func, x + y));
    m.Constraint(x + 3*y >= 0.75);
    ...
}

In Java, you have to implement the LSIntExternalFunction, LSDoubleExternalFunction, LSIntArrayExternalFunction or LSDoubleArrayExternalFunction interface and specifically the call() method to implement your external function (step 1).

Then (step 2), you instantiate your function and turn it into an LSExpression with the methods LSModel.createIntExternalFunction, LSModel.createDoubleExternalFunction, LSModel.createIntArrayExternalFunction or LSModel.createDoubleArrayExternalFunction.

Finally (step 3), you can use your function in LSOperator.Call expressions. To create LSOperator.Call expressions, you can use the generic method LSModel.createExpression or the shortcut LSModel.call. Values of the arguments of your external function will be exposed through a LSExternalArgumentValues.

You can access the LSExternalContext of the function with LSExpression.getExternalContext:

import java.lang.Math;
import localsolver.*;

...

void TestExternalFunction()
{
    LocalSolver ls = new LocalSolver();
    LSModel m = ls.getModel();
    LSExpression func = m.createDoubleExternalFunction(new LSDoubleExternalFunction() {
        double call(LSExternalArgumentValues argumentValues) {
            return Math.acos(argumentValues.getDoubleValue(0));
        }
    });

    // Users of Java 8 can simplify the code above by using a lambda:
    // LSExpression func = m.createDoubleExternalFunction(
    //    args -> Math.acos(args.getDoubleValue(0))
    // );

    func.getExternalContext().setLowerBound(0.0);
    func.getExternalContext().setUpperBound(Math.PI);

    LSExpression x = m.floatVar(-0.5, 0.5);
    LSExpression y = m.floatVar(-0.5, 0.5);
    m.minimize(m.call(func, m.sum(x, y)));
    m.constraint(m.geq(m.sum(x, m.prod(3, y)), 0.75));
    ...
}

Pitfalls¶

Solver status & cinematic¶

Most of the time your external function will be called when the solver is in state Running. Do not attempt to call any method of the solver (to retrieve statistics, values of LSExpressions or whatever) in that state or an exception will be thrown. The only accessible function is LocalSolver::stop().

Thread-safety¶

The search strategy of LocalSolver is multi-threaded by default. Thus, multiple threads can call your external functions and your code at the same time. This is not a problem as long as your external function does not have any side effect. In other cases, it is your responsability to ensure the thread-safety of your code by using mutexes, critical sections or any other locking mechanism you want. You can also limit the number of threads to 1 with the nbThreads parameter if you don’t want to deal with multi-threading issues.

Note

This recommendation applies only for C#, C++ and Java. Python (CPython) and LSP interpreters use a Global Interpreter Lock (also called GIL) that synchronizes the access of their underlying virtual machine, so that only one thread can execute at a time. If this special property of CPython and LSP simplifies the use of external functions, it can also have a significant performance impact since it prevents search parallelization (see Performance issues).

Performance issues¶

Even if we designed external functions to be as fast as possible, sometimes you will be faced with performance issues. There are two kinds of performance issues that can occur with external functions:

The final result of the search is not as good as it can be expected.
The speed of the search is degraded compared to a model without external functions.

The first issue is due to the nature of the feature itself. Indeed, LocalSolver doesn’t know anything about the new operator you add. It doesn’t even know if your operator is deterministic or not. Thus it will not be able to target the search or explore the solution space as it does with operators defined in its catalog. So if you observe feasibility troubles or if you can easily improve the solution returned by LocalSolver, try to reformulate most of your external function with the operators of LocalSolver.

The speed issue is a totally different problem. Calling an external function is a bit more costly for LocalSolver than calling one of its internal operator, but it is negligible. However, the case of LSP and Python are special. As explained a bit earlier, Python and LSP virtual machines use a Global Interpreter Lock that prevents 2 threads to access the managed code at the same time. Because of this locking mechanism, using more than one thread for the LocalSolver search would severely decrease performance compared to a single-threaded search. Therefore, in presence of LSP or Python external functions, LocalSolver will automatically limit the number of threads actually used by the search if the nbThreads parameter is not overloaded.

Memory management¶

In C++, you have to free the memory of the external functions you created. LocalSolver does not manage memory of objects created outside of its environment. This recommendation does not apply for managed languages (LSP, C#, Java, Python).

Surrogate modeling¶

If your function is computationally expensive to evaluate and can only be evaluated a small number of times during the solving process, you can enable the surrogate modeling feature on your external function to get better results.

Note

This feature changes the internal behavior of the solver. Therefore, the following restrictions must be taken into account:

Collection variables and intervals are currently not supported.
Surrogate modeling can be enabled on one external function in your model at most, and only one call is allowed on the associated function.
The values returned by the function can only be used in objectives or in constraints (another LSExpression cannot include one of the returned value).

Principles¶

To use the surrogate modeling feature, you must enable the LSSurrogateParameters of the external function using the method available on the LSExternalContext. Additional parameters specific to this functionality can be set on the LSSurrogateParameters class:

The evaluation limit of the function, i.e. the maximum number of calls of the function

The evaluation points. A LSEvaluationPoint is used to specify a known point of the function to the solver. It can be useful to warm-start the solver, especially when the function is particularly expensive to evaluate or if you already have a good estimate of the optimal point.

Example¶

To illustrate this functionality we use the same example as before, in which we show how to enable the surrogate modeling on the external function.

LSP
Python
C++
C#
Java

The surrogate modeling feature is enabled by the method enableSurrogateModeling available on the external function’s context. This method returns the LSSurrogateParameters which are used to limit the evaluation budget of the function to 20 calls:

function model() {
    func <- doubleExternalFunction(...);
    surrogateParams = func.context.enableSurrogateModeling();
    ...
}

function param() {
    surrogateParams.evaluationLimit = 20;
}

The surrogate modeling feature is enabled by the method LSExternalContext.enable_surrogate_modeling() available on the external function’s context. This method returns the LSSurrogateParameters which are used to limit the evaluation budget of the function to 20 calls:

with localsolver.LocalSolver() as ls:
    model = ls.model
    func = model.double_external_function(...)
    surrogate_params = func.external_context.enable_surrogate_modeling()
    ...
    model.close()
    surrogate_params.set_evaluation_limit(20)
    ls.solve()
    ...

The surrogate modeling feature is enabled by the method LSExternalContext::enableSurrogateModeling() available on the external function’s context. This method returns the LSSurrogateParameters which are used to limit the evaluation budget of the function to 20 calls:

LocalSolver ls;
LSModel model = ls.getModel();
LSExpression func = model.externalFunction(...);
LSSurrogateParameters surrogateParams = func.getExternalContext().enableSurrogateModeling();
...
model.close();
surrogateParams.setEvaluationLimit(20);
ls.solve();
...

The surrogate modeling feature is enabled by the method EnableSurrogateModeling() available on the LSExternalContext of the function. This method returns the LSSurrogateParameters which are used to limit the evaluation budget of the function to 20 calls:

LocalSolver ls = new LocalSolver();
LSModel model = ls.GetModel();
LSExpression func = model.DoubleExternalFunction(...);
LSSurrogateParameters surrogateParams = func.GetExternalContext().EnableSurrogateModeling();
...
model.Close();
surrogateParams.SetEvaluationLimit(20);
ls.Solve();
...

The surrogate modeling feature is enabled by the method enableSurrogateModeling available on the LSExternalContext of the function. This method returns the LSSurrogateParameters which are used to limit the evaluation budget of the function to 20 calls:

LocalSolver ls = new LocalSolver();
LSModel model = ls.getModel();
LSExpression func = model.doubleExternalFunction(...);
LSSurrogateParameters surrogateParams = func.getExternalContext().enableSurrogateModeling();
...
model.close();
surrogateParams.setEvaluationLimit(20);
ls.solve();
...