2

I have a list of people and I want to pair them all then do some filtering based on preferences. When I generate my candidate solutions, how do I avoid creating candidate solutions that re-pair a people.

For example:

person(a;b;c;d) .
{match(X, Y): person(Y)}1 :- person(X) .

This generates candidate solutions that include match(a,b) match(c,b) ...

I would like ONLY candidate solutions that do not rematch anyone like: match(a,b) match(c,d) ...

My goal is to not have to filter rematches out via additional constraints. Also, not everyone needs to be matched. Thanks!

exchez
  • 493
  • 1
  • 4
  • 13

2 Answers2

4
person(a;b;c;d).
{match(A,B) : person(A), person(B), A < B}.
:- person(A), 1 < {match(A,B); match(B,A)}.

You exclude solutions that have more than 1 match for a single person.

It is not possible to simply choose a correct set of atoms without additional constraints. As match(a,b) and match(b,c) can occur in different answer sets, both variables need to be created. Only a constraint can rule out that both do not occur in the same answer set.

Also note that your generator rule

{match(X, Y): person(Y)}1 :- person(X) .

already is a shortcut writing for

{match(X, Y): person(Y)} :- person(X).
:- person(X), 2 {match(X, Y): person(Y)}.

And therefore you are already using a constraint whenever your generator choice rule has non-trivial bounds.

PS: Check the different versions using --stats=2 for constraint count and --text for a rough approximation of what kind of constraints are generated.

Max Ostrowski
  • 575
  • 1
  • 3
  • 15
  • Your constraint to exclude multiple matches for a single person is very nice. However, my problem is that it won't scale because too many undesirable combinations are being created by the candidate solution generator. I'm wondering if there's a way we can make a generator that excludes multiple matches for the same person--sort of like how you added A < B in the generator but also covers multiple matches as well. – exchez Jun 16 '21 at 15:30
  • No, this is not possible, as every single atom can be valid on its own it has to be created. If you can give me an example that does not scale and can try to optimize it. – Max Ostrowski Jun 16 '21 at 21:33
  • I see your point now that I have experimented with clingo some more. Ideally, I'd like to do this matching with about 2000 people and optimize for preferences, but I now realize that optimizing over all the possible matches of 2000 people is computationally intractable. – exchez Jun 23 '21 at 17:38
  • You can always post the problematic part of your encoding and we can give it a try ;-) – Max Ostrowski Jun 23 '21 at 21:40
  • That would be great. I'm actually trying to write some code that matches vacuum tubes. Each tube has two triodes and I want to match tubes together so that one average of the matched pair's triodes are within 8% of the other's. The goal of the program to find the set of matches with the lowest triode deviation. I want this to work with up to 2,000 tubes. Example: tube(id, triode1, triode2). – exchez Jul 19 '21 at 18:02
  • Sure, lets do this offsite. Just write me a mail with your encoding (find me on the web related to the potassco.org page) or simply write to the potassco mailing list. Or open a new question here ? – Max Ostrowski Jul 19 '21 at 19:19
1

I'd go for Max Ostrowskis answer.

One of the difficulties is to handle the order of the attributes for the match predicate: this is a tuple, there is a difference if your value shows up on first or second position. Adding a rule to make the predicate commutative should do the trick since you don't need to distinguish for a value to be on first or second position. This method does not use a constraint (on first sight), but it duplicates the generated values so the output differs from your desired solution. Also it adds a line to the code.

person(a;b;c;d).
{match(X,Y): person(Y), X!=Y}1 :- person(X).
match(Y,X) :- match(X,Y).
#show match/2.

Output

Answer: 1

Answer: 2
match(c,a) match(a,c)
Answer: 3
match(b,a) match(a,b)
Answer: 4
match(c,d) match(d,c)
Answer: 5
match(b,a) match(a,b) match(c,d) match(d,c)
Answer: 6
match(b,d) match(d,b)
Answer: 7
match(c,a) match(a,c) match(b,d) match(d,b)
Answer: 8
match(b,c) match(c,b)
Answer: 9
match(d,a) match(a,d)
Answer: 10
match(d,a) match(a,d) match(b,c) match(c,b)
SATISFIABLE
DuDa
  • 3,718
  • 4
  • 16
  • 36