PREVIEW
OPTIMIZATION
Library: mathopt
⚠️

EXPERIMENTAL: These features are experimental and should not be used in production systems.

# The Math Optimization Library (mathopt)

A collection of math optimization tools.

## Module: rel:mathopt

``rel:mathopt``

Integration of external mathematical optimization solvers within Rel.

This module implements a DSL that defines operators which allow for the specification of mathematical optimization problems within Rel. Additionally, it defines APIs to execute the specified models using different interpreters, which are different implementations of the DSL operators.

Expressing an Optimization Model

A mathematical optimization problem should be specified in 3 modules:

• a `Data` module defines the underlying data feeding into the problem.
• a `Variables` module declares variables to be solved for, usually based on the `Data`.
• a `Model` module uses the DSL operators to specify an objective function and a set of constraints that should be satisfied by a solution.

Note that you can use any name for those modules. A very simple (and very artificial) example could be the following:

``````module MyData
// my data set has only a couple of integers
def my_domain = 5 ; 7
end

@inline
module MyVariables[Data]
with Data use my_domain
// x is an integer variable
def x:type = "integer"
// create a variable for each value in the Data my_domain
def x:keys = (my_domain)
end

@inline
module MyModel[Data, Variables, DSL]
with Data use my_domain
with Variables use x
with DSL use sum, foreach, +, -, *, ≼, ≽, /, ∧, ∨, =

// we will try to maximize the sum of the variables
def objective = sum[x[d] for d in my_domain]
// subject to an artificial constraint limiting their values
def subject_to:artificial = foreach[my_domain, {d : d * x[d] ≼ 20 }]
end``````

With these definitions you can now use one of the interpreters. There are currently 3 implementations: `solve`, `evaluate` and `debug`.

Solve

`rel:mathopt:solve` uses an implementation that builds a representation of the model and sends it to an external, configurable solver. The results can be inspected with a call to `rel:mathopt:extract`. For example:

``````def result = rel:mathopt:solve[{}, MyModel, MyData, MyVariables]
def extracted = rel:mathopt:extract[result, MyData, MyVariables]``````

Note that currently it is necessary to materialize `result`, it cannot be `@inlined`. The `extracted` relation contains the objective function value and solution data, as well as various meta-data about the execution:

``````// the outcome of the execution (see below for possible values)
ic { extracted:outcome = 1 }
// the termination status of the execution (see below for possible values)
ic { extracted:termination_status = 1 }
// the time in seconds taken by the external solver to execute
ic { exists extracted:solver_time_seconds }
// the external solver version
ic { exists extracted:solver_version }``````

The returned `outcome` relation contains one of the following values:

• Model Error (0): some error occurred in the translation from Rel to solver, which usually means the model was incorrectly specified.
• Success (1): the Rel model was correctly translated into a solver model, the solver was invoked and it returned a termination status that indicated it reached a conclusion, which could be an OK or relaxed result. The termination_status field contains a more detailed value for the outcome.
• Solver Limit (2): translation was OK but the solver stopped without reaching a conclusion due to some limit imposed on it, such as a time or model size limit.
• Solver Error (3): translation was OK but the solver stopped due to some unexpected error.

If the `outcome` is not Model Error(0), then the `termination_status` contains additional information. Its value comes from MathOptInterface’s TerminationStatusCode (opens in a new tab).

Evaluate

`rel:mathopt:evaluate` uses a DSL implementation that evaluates the model against a proposed solution. This allows us to compute the objective function value for a specific solution, and check whether the constraints would be satisfied.

``````module ProposedSolution
def x = MyData:my_domain, 2
end
def evaluated = rel:mathopt:evaluate[MyModel, MyData, ProposedSolution]

// the objective function value using ProposedSolution variable assignments
ic { evaluated:objective = 4 }
// the artificial constraint exists because it was satisfied by the assignments
ic { exists evaluated:subject_to:artificial }``````

Debug

Finally, `rel:mathopt:debug` can be used to compute debug information in the form of strings that contain S-expressions that represent the model’s objective function and constraints. This may be useful to understand issues with the specification.

``````// will output debug strings for objective function and constraints
def output = rel:mathopt:debug[MyModel, MyData, MyVariables]``````

Alternative Specification Pattern

The pattern suggested above, with `Data`, `Variables` and `Model` modules, is very flexible, allowing for multiple datasets to coexist in a database, reusing the same models. However, we pay a price in code complexity and, often, runtime performance.

The expression DSL can be reused with an alternative, simpler pattern. The simplified pattern has the advantage of minimizing the need for higher order modules, which makes specifications a bit simpler and faster. The drawback is that it is not possible to define group-bys based on different data sets.

The example above, using the simplified pattern, would look as follows:

``````// the dataset can be any Rel definition, not necessarily within a module
def my_domain = 5 ; 7

// variables are declared with rel:mathopt:variables and stored in a definition
def variables = rel:mathopt:variables[{
:x, "integer", my_domain
}]

// we can then bring variables and the expression DSL definitions into scope
with variables use x
with mathopt:Solver:Solve use sum, foreach, +, -, *, ≼, ≽, /, =

// there is no need for higher order modules for objective function and constraints
def objective = sum[x[d] for d in my_domain]

// we use a first-order module to group the constraints
module constraints
def artificial = foreach[my_domain, {d : d * x[d] ≼ 20 }]
end

// finally we can maximize and extract the results:
def result = rel:mathopt:maximize[objective, constraints, variables, {}]

// note that this is extract_result, not extract as before
def output = rel:mathopt:extract_result[result, variables]``````

Note that names are irrelevant for the library, you can use other names for `objective`, `constraints`, `variables` and `result`.

### solve

``rel:mathopt:solve[CONFIG, MODEL, DATA, VARS]``

Call a mathematical optimization solver to search for a solution to the specified problem.

Inputs:

• `CONFIG`: the relation that contains configuration for the solver. `mathopt:SolverConfigDefaults` describes the accepted configuration parameters. The empty relation can be used when the defaults are appropriate, e.g. `rel:mathopt:solve[{}, ...]`
• `MODEL`: the relation that specifies the model to solve. It should contain the objective function, the constraints (under a `subject_to` sub-relation) and must be parameterizable with DATA, VARS and SOLVER higher order relations.
• `DATA`: the relation that contains data to populate the model. It must be first order.
• `VARS`: the relation that declares the model variables. It must be parametrizable with DATA.

Output:

• an opaque binary string containing the result of the solver. Use the `rel:mathopt:extract` function to extract detailed information from the result.

### solve_instance

``rel:mathopt:solve_instance[MODEL, DATA, VARS]``

Compute the full instance of this model, when instantiated with this data and variables. This can be used to investigate and debug the model that is being instantiated by `rel:mathopt:solve` without attempting to call the solver.

Inputs are the same `MODEL`, `DATA` and `VARS` as `rel:mathopt:solve`.

Output:

• an instantiated model, which is the `MODEL` module instantiated with `DATA` and `VARS`, which should contain the concrete objective function and constraints that would be sent to the solver.

### extract

``rel:mathopt:extract[result, DATA, VARS]``

Extract detailed information from the result of a call to a mathematical optimization solver. The result must be a materialized relation. This is equivalent to the union of `rel:mathopt:extract_info` and `rel:mathopt:extract_solution`; if you are only interested in the solution, using `rel:mathopt:extract_solution` is potentially more efficient.

Inputs:

• `result`: a relation that contains the result of a `rel:mathopt:solve` call. It must be materialized.
• `DATA`: the relation that contains data to populate the model. It must be grounded.
• `VARS`: the relation that declares the model variables. It must be parametrizable with DATA.

Output:

• a function from variable keys to the float value assigned by the solver, if any. The keys depend on the variable specification in VARS.

Example:

``````def result = rel:mathopt:solve[{}, Model, Data, Variables]
def extracted = rel:mathopt:extract[result, Data, Variables]``````

### extract_info

``rel:mathopt:extract_info[result]``

Similar to `rel:mathopt:extract`, but only extract meta-information, such as termination status, solver time, etc.

### extract_solution

``rel:mathopt:extract_solution[result, DATA, VARS]``

Similar to `rel:mathopt:extract`, but only extract the solution, which contains variable assignments.

### evaluate

``rel:mathopt:evaluate[MODEL, DATA, SOLUTION]``

Evaluate a model against a specific solution.

This function uses the same `MODEL` and `DATA` modules that `rel:mathopt:solve` expects, but instead of searching for a solution, it evaluates the provided solution. This is useful to validate whether a solution satisfied the model constraints and to obtain the corresponding value for the objective function.

Example:

``````module CorrectSolution
def xMake = ("bands", 10) ; ("coils", 20)
end
def evaluated_model = rel:mathopt:evaluate[Model, Data, CorrectSolution]``````

### debug

``rel:mathopt:debug[MODEL, DATA, VARS]``

Get debug information for a mathematical optimization model.

This function has the same interface as `rel:mathopt:solve`, but returns debug information in the form of strings that contain S-expressions that represent the model’s objective function and constraints.

Example:

``def output = rel:mathopt:debug[Model, Data, Variables]``

## Module: mathopt:SolverConfigDefaults

Default values for the configuration parameters accepted by `rel:mathopt:solve`.

### sense

Indicates whether the solver should “maximize” or “minimize” the objective function:

### objective

A symbol with the name of the subrelation in `MODEL` that contains the objective function definition:

### solver

Which solver backend to use. Currently “HiGHS” (MIP and QP formulations), “DAQP” (MIP and QP formulations), and “Pavito” (MIQP formulations) are accepted:

### solver_attributes

Key value pairs of solver-specific attributes. These are sent directly to the solver backend. The key must be a string and the value must be either a number or a string. Example:

``````// provide a solution timeout limit and turn off presolve while using `HIGHS`.
def solver_attributes = {("time_limit", 60); ("presolve", "off")}``````

### model_format

A string specifying the format of the optimization model to be returned as a single string. The available formats are “LP”, “MPS”, “MOF”, and “NL”.

## Module: mathopt:Solver

Various implementations of a DSL for specifying mathematical optimization problems.

### Module: Solve

Solve models using a mathematical optimization solver.

### Module: Evaluate

Evaluate objective functions and constraints against variable assignments.

### Module: Debug

Debug models by generating S-expressions for objective functions and constraints.

## Module: rel:mathopt

### variables

``rel:mathopt:variables[R]``

Declare variables without needing a module. The relation `R` must contain triples `(Symbol, String, D)` that represent the variable name, the variable type, and the domain, respectively.

Example:

``````    def vars = rel:mathopt:variables[{
:x, "continuous", domain ;
:y, "binary", ()
}]``````

### named_variables

``rel:mathopt:named_variables[R]``

Declare variables with name and key value pairs to be used in debugging, and also without needing a module. The relation `R` must contain triples `(Symbol, String, D)` that represent the variable name, the variable type, and the domain, respectively.

Example:

``````    def vars = rel:mathopt:named_variables[{
:x, "continuous", domain ;
:y, "binary", ()
}]``````

### maximize

``rel:mathopt:maximize[OBJECTIVE, CONSTRAINTS, VARIABLES, CONFIG]``

Execute a solver trying to maximize the `OBJECTIVE` function under these `CONSTRAINTS`, using these `VARIABLES`. Configure the solver using `CONFIG`.

Inputs:

• `OBJECTIVE` must be an expression created using the mathopt:Solver DSL.
• `CONSTRAINTS` must be a module that contains definitions for the constraints; those constraints also should be built with the mathopt:Solver DSL.
• `VARIABLES` must be a definition that contains the value returned from a call to `rel:mathopt:variables`, which defines variables.
• `CONFIG` is a relation to override values from `mathopt:DefaultSolverConfig`. Note that `sense` and `objective` are ignored by this function.

Output:

• an opaque binary string containing the result of the solver. Use the `rel:mathopt:extract_result` function to extract detailed information from the result.

### minimize

``rel:mathopt:minimize[OBJECTIVE, CONSTRAINTS, VARIABLES, CONFIG]``

Execute a solver trying to minimize the `OBJECTIVE` function under these `CONSTRAINTS`, using these `VARIABLES`. Configure the solver using `CONFIG`.

See rel:mathopt:maximize for details.

### export_model

``rel:mathopt:export_model[OBJECTIVE, CONSTRAINTS, VARIABLES, CONFIG]``

Export the model as a string representation of the file as specified in `CONFIG`, without optimizing the model. The default model returned is a LP format, the default sense is maximize, and the default solver is HiGHS. Any errors encountered while building the model are reported to the user instead of the model file string.

Inputs:

• `OBJECTIVE`: an expression created using the mathopt:Solver DSL.
• `CONSTRAINTS`: a module that contains definitions for the constraints, which should also be built with the mathopt:Solver DSL.
• `VARIABLES`: a definition that contains the value returned from a call to `rel:mathopt:variables`, or a call to `rel:mathopt:named_variables`, which defines variables.
• `CONFIG`: a relation to override values from `mathopt:DefaultSolverConfig`.

Output:

• An opaque binary string containing the result of the solver. Use the `rel:mathopt:extract_result` function to extract detailed information from the result.

Example:

``````def result = rel:mathopt:export_model[objective, constraints, variables, {}]
def extracted = rel:mathopt:extract_result[result, variables]``````

### extract_result

``rel:mathopt:extract_result[result, VARIABLES]``

Extract detailed information from the result of a call to a mathematical optimization solver (`maximize`, `minimize`, or `export_model`). The result must be a materialized relation.

Inputs:

• `result`: a relation that contains the result of a `rel:mathopt:maximize`, `rel:mathopt:minimize`, or`rel:mathopt:export_model` call. It must be materialized.
• `VARIABLES`: the relation that declares the model variables, created with `rel:mathopt:variables`.

Output:

• a function from variable keys to the float value assigned by the solver, if any. The keys depend on the variable specification in VARS.

Example:

``````def result = rel:mathopt:maximize[objective, constraints, variables, {}]
def extracted = rel:mathopt:extract_result[result, variables]``````