[RFC] Dominance Relations

[gskorokhod]

Background

Terms

Satisfaction Problems

A classic Constraints Satisfaction Problem (CSP) consists of:

• a set of decision variables and corresponding domains
• a set of constraints, which are boolean expressions in terms of some set of decision variables
  A solution is any assignment of values to decision variables that satisfies all constraints

Optimisation Problems

A Constraints Optimisation Problem (COP) consists of:

• a CSP, and
• an objective function of some decision variables that needs to be minimised/maximised
  (NB: there is only one objective function)
  A solution is an assignment of values to variables where all constraints are satisfied and the value of the function is optimised

For a COP, there is a single value being optimised, so it's relatively simple for the solver to search the solution space as efficiently as possible (e.g. using branch-and-bound or a similar algorithm, plus some heuristics)

Dominance (and why it's necessary)

However, sometimes it is necessary to evaluate the best-case "trade-off" between multiple functions of the solution.
That is, we want to limit our search only to such solutions where at least one of the variables being considered can't be optimised further without "hurting" the others.

Formally, we usually define dominance as follows (assuming maximising):
Solution $A(x_a, y_a)$ dominates solution $B(x_b, y_b)$ if $(x_a\geq x_b) \land (y_a \geq y_b) \land ((x_a \gt x_b) \lor (y_a \gt y_b))$
(I.e. both values are at least as good and at least one is strictly better)

That is, we want to limit our search only to the Pareto front.
Note that:

1. This may be either in the context of an optimisation problem (whether in terms of one of the variables that make up the dominance relation, a combination thereof, or some unrelated objective function), or in the context of a satisfaction problem.
   Dominance is separate from that, and simply restricts our search to the set of Pareto-efficient solutions for a given definition of which solutions are to be preferred.
2. The dominance function may be defined differently for different models. It is not a search optimisation that can be applied transparently by the solver - its definition must be part of the model itself.

Domination Problems

Formally, a Constraints Dominance Problem (CDP) consists of a CSP or COP, plus a dominance relation.
The dominance relation is a boolean function in terms of some decision variables that defines when one solution dominates another.

Implementation

Dominance problems are handled by generating and adding new constraints during a solver's runtime to gradually restrict the search space.

The new constraint is essentially a negation of our definition of dominance, with the current solution's values plugged in.
I.e, "only consider solutions that are not dominated by the ones we've found so far".

Notes:

• This will include solutions that are not dominated yet, but will be dominated by some new solution that we've found.
  These will need to be pruned by a later post-processing step.
• We need not worry about local optima.
  Solutions that are incomparable to the current one (i.e. neither dominating nor dominated by it) will still be considered, we're only pruning away ones that are "strictly worse" than it!
• Dominance just restricts our search to a subset of solutions; then, depending on the problem, we can:
  • Enumerate them all
  • Check that at least one such solution exists (satisfaction)
  • Find the optimal one above them based on a single and separately defined objective function (optimisation)
• Adding new constraints at runtime is "safe" because we are only restricting the search space further, not invalidating previous solutions
• As dominance relations are part of the model, they are expressed using the same language (Essence) and must be rewritten into solver-specific languages using the same rewrite process

Essence Syntax

Consider this example Essence model representing a dominance problem:

given cost : matrix indexed by [int(1..10)] of int
given carbon_footprint : matrix indexed by [int(1..10)] of int

% the answer is a selection of some of the 10 points
find selected : matrix indexed by [int(1..10)] of bool

% select at least 2 options
such that sum([ toInt(selected[i]) | i : int(1..10) ]) >= 2

% total cost of the solutiuon
find total_cost : int(0..1000)
such that total_cost = sum([ cost[i] | i : int(1..10), selected[i] ])

% total carbon in the solution
find total_carbon : int(0..1000)
such that total_carbon = sum([ carbon_footprint[i] | i : int(1..10), selected[i] ])

% dominance: both are at least as good as current solution,
% at least one is strictly better
dominanceRelation
	(total_cost <= fromSolution(total_cost)) /\
	(total_carbon <= fromSolution(total_carbon)) /\
	(
		(total_cost < fromSolution(total_cost)) \/
		(total_carbon < fromSolution(total_carbon))
	)

The dominance relation is expressed here in terms of two variables (which are computed based on the solution's decision variables).
It is essentially a plain definition of the new constraint to be added, where fromSolution() calls must be replaced with the value of the corresponding decision variable in the current solution.

Solver Adaptor

Solvers have different implementations. Some provide built-in methods for incremental solving (i.e. enumerating solutions one by one and potentially adding new constraints at each step). In this case, our task is simply to:

1. Start the solving process as normal and wait for a solution
2. Generate the new constraint based on the solution
3. Call the right method in the solver code (via Rust bindings)
4. Resume the solving process

However, for solvers that do not support incremental solving, we would have to emulate this behaviour by:

1. Running the solver and getting a single solution
2. Constructing a new Model with the added constraints
3. Re-starting the solving process

This is less efficient, but may be necessary for some solvers.
Minion should have most of the required functionality out of the box, but patches to the C++ code may be needed.

Rewriting

For efficiency, we want to rewrite the dominance relation definition itself and generate new constraints directly from its solver-specific representation, rather than running a new rewrite on every iteration. In general this should not be hard, but there may be some edge cases with regards to handling fromSolution correctly.

See Also

• Paper defining the basic terms: Solution Dominance over Constraint Satisfaction Problems
• PhD thesis on dominance in Essence: Exploiting Incomparability in Solution Dominance:
  Improving General Purpose Constraint-Based Mining
• CS4402 (Constraints Programming) lecture slides for basic terminology: Studres

Plan

1. Implement AST types to represent dominance relations in the model
2. Parse the above Essence syntax (via Treesitter, or the old conjure parser)
3. Convert the dominanceRelaion into new top-level constraints (Expression) at runtime
   • (Essentially, just plug the right value to all fromSolution variables)
4. Update rewriter rules and the rewriter code to handle them
5. Update SolverAdaptor code to handle the generated constraints using the solver-specific AST types
6. Find and bind to the right Minion methods to add constraints
   • May require patches to the existing C++ code
7. Build and test a dominance proof of concept problem

The focus will be on Minion first, and implementing a nice generic interface for all of this in other solver adaptors later.
Work on this project will be tracked in sub-issues of this one!

[ozgurakgun]

Thanks for the write up @gskorokhod, it captures the project well.

Don't let this be a blocker for you but I'd like to explore the concrete syntax a bit with at some point. Changes will likely be cosmetic, so any work you do now will still mostly apply, I am sure.

[gskorokhod]

Actually, I just thought of this while walking to labs and I think I've misunderstood the process yet again :)

Notes:

• We need not worry about local optima.

This is actually wrong. If we generate new constraints by just plugging values into the dominance relation definition, then we end up with one non-dominated solution (the last one) and then stop.

We won't get the other Pareto-efficient solutions, as they would require making at least one of the variables "worse".
The problem is: how do we get from one point on the Pareto front to all of it?

[ozgurakgun]

You do get all solutions on the efficient front. Since they do not dominate each other. Does that make sense? Each new dominance blocking constraint removes all solutions that are dominated by the one we just found.

You are also likely to get some solutions-that-will-later-be-dominated during the process, so you'll still have to post filter for those.

[gskorokhod]

Ok, so my understanding at the moment (which is probably wrong) is:

Say we have 2 variables we're considering.
We get the first solution and we start looking for others, where all variables are at least as good and at least one is strictly better. We repeat this process in steps 1..3 (see drawing), but at this point the newly added constraitns block out all other solutions (shown in red).

Where am I making the mistake?

[ozgurakgun]

Assuming this a maximisation problem in both axes:

• When you find 1, the rectangle to the left and bottom of 1 is dominated by 1, add a constraint to make them non-solutions
• When you find 2, the same kind of rectangle is dominated by 2. including 1.
• When you find 3, the same.

We are excluding dominated solutions every time we find a solution. So you red shaded parts were never excluded.

[gskorokhod]

Assuming this a maximisation problem in both axes:

* When you find 1, the rectangle to the left and bottom of 1 is dominated by 1, add a constraint to make them non-solutions

* When you find 2, the same kind of rectangle is dominated by 2. including 1.

* When you find 3, the same.

We are excluding dominated solutions every time we find a solution. So you red shaded parts were never excluded.

Ah, so the dominance breaking constraint is actually the negation of the dominance relation with the current solution's values plugged in

I.e "only consider solutions that are not dominated by the current one"

That's what I was missing I think!

[gskorokhod]

I've updated the writeup, thank you!