Representing Optimisation Problems in the Model

[niklasdewally]

Motivation

As well as satisfaction problems (find me the x that satisfies these constraints), Minion and other solvers support optimisation problems (find me the x that fulfills the most/least of these criteria).

The Problem

We need to store optimisation information in the model. This should be used to determine what rules to apply (for example, if we have optimisation specific rules). This information also needs to be accessible to the solver adaptor.

Related Issues

• [Discussion] Support conditional rule selection and priority #165. This problem is a subset of the larger issue of conditional rule application.
• minion_rs / minion C++: Allow the use of minion to solve optimisation problems #215. This tracks the implementation of this at the Minion bindings level.

[niklasdewally]

RFC: @ozgurakgun @lixitrixi @Kieranoski702 @gskorokhod @PedroGGBM

Unanswered questions:

• Are there any overarching problems adding this would cause (e.g. with conditional rule selection).
• Are there any cases I am missing?
• Are there any further requirements for this feature?

[gskorokhod]

Would the optimisation also be expressed using Expressions?
What specifically do we need to do? (i.e. - is it just "find a solution that satisfies the constraints such that variable a is as high as possible" or something more complex?)

[gskorokhod]

Also, how do solvers (mostly Minion) handle optimisation and how is it handled in Conjure currently? This could be a starting point

[niklasdewally]

Also, how do solvers (mostly Minion) handle optimisation and how is it handled in Conjure currently? This could be a starting point

From a minion_rs pov, it would be passed in the SearchMethod.

In minion language, it is expressed something like so: https://github.com/minion/minion/blob/main/test_instances/new_optimisetest.minion

Would the optimisation also be expressed using Expressions? What specifically do we need to do? (i.e. - is it just "find a solution that satisfies the constraints such that variable a is as high as possible" or something more complex?)

That's right - optimisation is just specifying "MAXIMISING x / MINIMISING y" It does not change the model, just how the model is solved. Of course, as with SAT encodings, etc rules may want this information so that we can tailor optimisation problems.

The Minion manual (in the GH repo) would give more details on what exactly we can support here.

[niklasdewally]

As with SAT Encodings, solver, etc this is information needed alongside the model itself for knowing which rules to apply, but is not something that is directly represented in the model, at least for Minion.

I.e. it might be something we store in the Model struct, or the Context discussed in #221.

[gskorokhod]

As with SAT Encodings, solver, etc this is information needed alongside the model for knowing which rules to apply, but is not something that is directly represented in a model, at least in Minion.

I.e. it might be something we store in the Model struct, or the Context discussed in #221.

Thanks! I'd lean towards having it as a separate field in the Model. I think the optimisation information is something that's different from general settings / metadata (which would be in the context), and potentially different solver adaptors could also handle it differently?

(In the worst case scenario, if the solver doesn't support it entirely, we might have to get all solutions and pick the best ones manually)

[ozgurakgun]

getting all solutions and picking is never an option I think. it'll just be extremely expensive.

I agree though it should be another field in model. call it objective. it contains a single expression that is of an orderable type (so not necessarily a boolean and for now all types we have are orderable).