# The Math Optimization Library (mathopt)

Collection of math optimization tools.

## Module: mathopt:Solver

Various implementations of a DSL for specifying mathematical optimization problems.

### Module: Debug

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

### Module: Evaluate

Evaluate objective functions and constraints against variable assignments.

### Module: Solve

Solve models using a mathematical optimization solver.

## Module: mathopt:SolverConfigDefaults

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

.

### objective

A symbol with the name of the sub-relation in `MODEL`

that contains the
objective function definition.

##### Definition

`def objective = :objective`

### sense

Indicates whether the solver should :maximize or :minimize the objective function.

##### Definition

`def sense = :maximize`

### solver

Which solver backend to use. Currently only :CBC is accepted.

##### Definition

`def solver = :CBC`

### 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 a number. Example:

`// provide a solution timeout limit to `CBC`.`

def solver_attributes = {("seconds", 60)}

##### Definition

`def solver_attributes = {}`

## 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.

**Express 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 domain = 5 ; 7

end

@inline

module MyVariables[Data]

with Data use domain

// x is an integer variable

def x:type = "integer"

// create a variable for each value in the Data domain

def x:keys = (domain)

end

@inline

module MyModel[Data, Variables, DSL]

with Data use 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 domain]

// subject to an artificial constraint limiting their values

def subject_to:artificial = foreach[domain, {d : d * x[d] ≼ 20 }]

end

With these definitions we 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.

**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: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]

### 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]`

##### Definition

`@inline`

def debug[MODEL, DATA, VARS] =

MODEL[DATA, _mathopt_debug_variables[VARS[DATA]], mathopt:Solver:Debug]

### 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]

##### Definition

`@inline`

def evaluate[MODEL, DATA, SOLUTION] =

MODEL[DATA, SOLUTION, mathopt:Solver:Evaluate]

### 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]

##### Definition

`@inline`

def extract[RESULT, DATA, VARS](:solution, name, x..., value) =

rel_primitive_mathopt_extract[RESULT](:solution, id, value) and

_mathopt_debug_variables[VARS[DATA]](name, x..., id) from id

@inline

def extract[RESULT, DATA, VARS](key, value) =

rel_primitive_mathopt_extract[RESULT](key, value) and key != :solution

### extract_info

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

Similar to `rel:mathopt:extract`

, but only extract meta-information, such as termination
status, solver time, etc.

##### Definition

`@inline`

def extract_info[RESULT](key, value) =

rel_primitive_mathopt_extract[RESULT](key, value)

### extract_solution

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

Similar to `rel:mathopt:extract`

, but only extract the solution, which contains variable
assignments.

##### Definition

`@inline`

def extract_solution[RESULT, DATA, VARS](name, x..., value) =

rel_primitive_mathopt_extract[RESULT](:solution, id, value) and

_mathopt_debug_variables[VARS[DATA]](name, x..., id) from id

### 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.

##### Definition

`@inline`

def solve[CONFIG, MODEL, DATA, VARS] =

rel_primitive_mathopt_solve[

(string[_mathopt_solve_config[CONFIG][:sense]]),

(string[_mathopt_solve_config[CONFIG][:solver]]),

_mathopt_solve_attributes_folded[CONFIG],

_mathopt_solve_variable_declarations_folded[VARS[DATA]],

(_mathopt_solve_model[MODEL, DATA, VARS][_mathopt_solve_config[CONFIG][:objective]] <++ ""),

_mathopt_solve_constraints_folded[_mathopt_solve_model[MODEL, DATA, VARS]]

]