We could think about specialised nogood data structures that would improve the performance of our extended nogood propagation. Currently we mainly inherit the data structure that is used for unit propagation, which simply takes an array of predicates. But this may not be the most efficient representation. We may also want to change our assignment data structure to account for this.
Idea 1. Extended nogood propagators does the propagation by looking at the domains represented by atomic constraints. It then might make sense to group the predicates by domain_id. Here are some examples:
[x >= 5] & .... & [x <= 10] & ... -> false
In this case, when we look over the ngood, we will first check [x >= 5], go through the if statements and checks, and then assess its truth statement. Then we do the same with [x <= 10]. But if we were to check [x >= 5] and [x <= 10] as a batch, we might save some operations.
This problem is more evident with nogoods with many not equals. Say
[x != 7] & [x != 8] & [x != 9] & [x != 11] & ...
Currently this is not great for our data structures, it looks at each query separately. But if we assess the truth values of all these predicates in a batch, we might gain efficiency.
[edit: when writing the next part I somehow forgot about our PredicateIDs, please keep this in mind! On this note, it would be nice to know how often do assignments in predicateid get used without needing to look up the value. If we think about predicateIds as cached values, then we may be interested in the "hit rate"!]
We can also save space by using a different struct instead of predicates. Say
[x >= 5] & [x !=7] & [x != 9] & [x <= 10] ...
This part takes 4*|predicate| size, so 4 * 8 bytes = 32 bytes. But we could store this as
[domain_id = 4 bytes] [num_predicates = 4 bytes] and then follow up with a series of simplified predicates that look like "[operation type - 2 bits] [right_hand_side value - 30 bits]"
In this case, we get 24 bytes. If nogoods contain many predicates of the same domain_id, this could also be a good saving. It would be useful to gather some statistics to see 1) how many predicates per variables are there in nogoods, 2) how often we both have the lower and upper bound of a variable in the nogoods, and 3) if there are holes, how many are usually there? Extended nogood propagation might introduce holes even in problems with non-hole propagators.
Plus we may be able to evaluate predicates in a batch operation, rather than query one by one. This could be valuable for extended nogoods, but also for unit propagation? Basically we are using information about domain_ids to make propagation more efficient.
The idea above probably needs further development to truly be useful, but I think it is a good start (batch evaluation + more efficient storage)!
Idea 2 (probably too low level). The nogood contains essentially many domain representations. Once the nogood representation a single domain, it propagates. If many domain representations are used across different nogoods, it could be useful to create a new variable for it. This looks like extended resolution. Probably this is not that useful, but it might be, since explanations might be the same for many propagations, and in that case there may be value having extended variables for it.
We could think about specialised nogood data structures that would improve the performance of our extended nogood propagation. Currently we mainly inherit the data structure that is used for unit propagation, which simply takes an array of predicates. But this may not be the most efficient representation. We may also want to change our assignment data structure to account for this.
Idea 1. Extended nogood propagators does the propagation by looking at the domains represented by atomic constraints. It then might make sense to group the predicates by domain_id. Here are some examples:
[x >= 5] & .... & [x <= 10] & ... -> false
In this case, when we look over the ngood, we will first check [x >= 5], go through the if statements and checks, and then assess its truth statement. Then we do the same with [x <= 10]. But if we were to check [x >= 5] and [x <= 10] as a batch, we might save some operations.
This problem is more evident with nogoods with many not equals. Say
[x != 7] & [x != 8] & [x != 9] & [x != 11] & ...
Currently this is not great for our data structures, it looks at each query separately. But if we assess the truth values of all these predicates in a batch, we might gain efficiency.
[edit: when writing the next part I somehow forgot about our PredicateIDs, please keep this in mind! On this note, it would be nice to know how often do assignments in predicateid get used without needing to look up the value. If we think about predicateIds as cached values, then we may be interested in the "hit rate"!]
We can also save space by using a different struct instead of predicates. Say
[x >= 5] & [x !=7] & [x != 9] & [x <= 10] ...
This part takes 4*|predicate| size, so 4 * 8 bytes = 32 bytes. But we could store this as
[domain_id = 4 bytes] [num_predicates = 4 bytes] and then follow up with a series of simplified predicates that look like "[operation type - 2 bits] [right_hand_side value - 30 bits]"
In this case, we get 24 bytes. If nogoods contain many predicates of the same domain_id, this could also be a good saving. It would be useful to gather some statistics to see 1) how many predicates per variables are there in nogoods, 2) how often we both have the lower and upper bound of a variable in the nogoods, and 3) if there are holes, how many are usually there? Extended nogood propagation might introduce holes even in problems with non-hole propagators.
Plus we may be able to evaluate predicates in a batch operation, rather than query one by one. This could be valuable for extended nogoods, but also for unit propagation? Basically we are using information about domain_ids to make propagation more efficient.
The idea above probably needs further development to truly be useful, but I think it is a good start (batch evaluation + more efficient storage)!
Idea 2 (probably too low level). The nogood contains essentially many domain representations. Once the nogood representation a single domain, it propagates. If many domain representations are used across different nogoods, it could be useful to create a new variable for it. This looks like extended resolution. Probably this is not that useful, but it might be, since explanations might be the same for many propagations, and in that case there may be value having extended variables for it.