Finding solution that satisfies the Maximum possible number of constraints

[YiwenDong98]

Hello, I really like the way we can specify complex relations and requirements using constraints in datalog.

I am wondering in the case where for a relation not all constraints can be satisfied, if there's a fast way to find 1 solution that satisfies the as many constraints as possible.
While the .limitsize directive can be used to limit the solution to 1 tuple, there seems to be no simple way to find a solution that satisfies maximum number of constraints.
I feel like such a feature enables us to use datalog in a more flexible way. Or maybe I am missing something/ using Datalog wrong.

Here's an example of such a problem. In this code we try to find the best seating arrangement for a group of people.

// Some known relations
.decl person(name: symbol)
.decl friend(person: symbol, their_friend: symbol)
.decl hobby(person: symbol, hobby_name: symbol)

// Some computed relations

// People are friendly based on some criteria
.decl friendly(person1: symbol, person2: symbol)
friendly(p1, p2) :-
  person(p1),
  person(p2),
  friend(p1, p2).

friendly(p1, p2) :-
  person(p1),
  person(p2),
  friend(p2, p1).

// People share a hobby
.decl share_hobby(person1: symbol, person2: symbol)
share_hobby(p1, p2) :-
  person(p1),
  person(p2),
  hobby(p1, hobby_name),
  hobby(p2, hobby_name).


// We want to query how to assign seating using certain constraints.
// This is a potentially generated, large relation with some inter-dependency between the elements within.
// For the simplicity of this example, ignore the fact a person can't be at more than 1 table at once. 
//   Additional constraints can be used to specify that.
.decl seating(tb1_per1: symbol, tb1_per2: symbol, tb2_per1: symbol, tb2_per2: symbol)
.output seating
seating(tb1_per1, tb1_per2, tb2_per1, tb2_per2) :-
  friendly(tb1_per1, tb1_per2),
  share_hobby(tb1_per1, tb1_per2),
  friendly(tb2_per1, tb2_per2),
  share_hobby(tb2_per1, tb2_per2).

// Facts
person("p1").
person("p2").
person("p3").
person("p4").
friend("p1","p2").
friend("p2","p1").
friend("p2","p3").
friend("p3","p2").
friend("p3","p4").
hobby("p1", "walk").
hobby("p2", "walk").
hobby("p3", "walk").
hobby("p3", "program").
hobby("p4", "program").
hobby("p4", "nap").

While this outputs a potential seating arrangement when all constraints can be satisfied, suppose if p4 didn't like programming, then there is no output at all even though some subset of constraints can be solved.

Potential solution I thought of is adding optional relations e.g.

optional_friendly(p1, "anyone") :- person(p1).
optional_friendly("anyone", p2) :- person(p2).
optional_friendly(p1, p2) :- friendly(p1,p2).
optional_share_hobby(p1, "anyone") :- person(p1).
optional_share_hobby("anyone", p2) :- person(p2).
optional_share_hobby(p1, p2) :- share_hobby(p1,p2).
// And change the seating constraint to 
seating(tb1_per1, tb1_per2, tb2_per1, tb2_per2) :-
  optional_friendly(tb1_per1, tb1_per2),
  optional_share_hobby(tb1_per1, tb1_per2),
  optional_friendly(tb2_per1, tb2_per2),
  optional_share_hobby(tb2_per1, tb2_per2).

But this kind of solution cause an explosion in number of tuples outputted. Many of which are not interesting. Furthermore, we cannot use .limitsize seating(n=1) in this case as it may truncate the optimal solution.

Another kind of solution is to output each sub-constraint and compute an intersection but my hunch is that it will result in poor performance. Especially in terms of memory usage.

My question is, What are some good ways of solving this type of problem that will be fast and scale to large number of constraints along with large number of facts?

[XiaowenHu96]

Here is my idea of using the choice constraint in Souffle:

Assign each constraint with a score, 1 if the constraint is satisfied and 0 otherwise.
Modify seating so each solution has a score, indicating how many constraints are satisfied.
Assign seating a choice construct such that for each score, we only keep one solution.
Boostraping seating with a score = 0.
Modify seating so seating with score x is fired iff there is a seating with score (x-1).

.decl seating(tb1_per1: symbol, tb1_per2: symbol, 
        tb2_per1: symbol, tb2_per2: symbol, score: number) choice-domain score
.output seating(IO=stdout)
seating("", "", "", "", 0).
seating(tb1_per1, tb1_per2, tb2_per1, tb2_per2, score) :-
  friendly(tb1_per1, tb1_per2, s1),
  share_hobby(tb1_per1, tb1_per2, s2),
  friendly(tb2_per1, tb2_per2, s3),
  share_hobby(tb2_per1, tb2_per2, s4),
  score = s1 + s2 + s3 +s4,
  seating(_, _, _, _, score - 1).

[XiaowenHu96]

On the second thought, the choice approach doesn't do exactly what we want here.
Because at the implementation level, the uniqueness is only checked when performing the final insert. This means all possible solutions for each score are still computed, they just never got inserted. The same will apply to a subsumption approach.

Unfortunately, I don't think there is an easy way to do what you want. For now, I would just use limitsize and just enumerate each score...

[YiwenDong98]

Thank you for the quick response. I did not know about choice-domain before and it seems really cool. Shame that there's no easy way to do this currently. I'm going to try to come up with something hopefully interesting to tackle this.