Fix VariableExactSumConstraint forwardcheck incorrectly pruning valid domain values - #108
Closed
gaoflow wants to merge 2 commits into
Closed
Fix VariableExactSumConstraint forwardcheck incorrectly pruning valid domain values#108gaoflow wants to merge 2 commits into
gaoflow wants to merge 2 commits into
Conversation
…d variable
In the no-multipliers branch of __call__, `sum_value` includes
`min(domain)` as a placeholder for each unassigned variable. The
forward-check loop then computed `temp_sum = sum_value + value`,
inadvertently double-counting the placeholder for the variable under
scrutiny and pruning valid domain values too aggressively.
Example: with a=[1,2], b=[1,2], c=[3] and a=1 already assigned,
`sum_value` was 2 (1 from a plus min(b)=1 as placeholder).
The forward-check then computed temp_sum = 2 + 2 = 4 > 3 and
incorrectly hid b=2, making a+b=3 unreachable.
Fix: subtract the placeholder for the variable being checked before
adding the candidate value, so only the contribution from *other*
unassigned variables is retained:
var_placeholder = min(domain)
temp_sum = sum_value - var_placeholder + value
This mirrors the intent of the multipliers branch, which never added a
placeholder and was therefore unaffected.
Author
|
CI triage note: the current red
|
fjwillemsen
added a commit
that referenced
this pull request
Jun 29, 2026
Member
|
@gaoflow thank you for submitting this PR! I've checked it and wanted to make some improvements which I couldn't do on your fork, but I've included this fix and a test to prevent it in the future in the just-released 2.6.0. Thank you for your contribution! |
Author
|
Thanks @fjwillemsen — glad it made it into 2.6.0, and nice call adding the regression test. Appreciate the quick turnaround! |
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
Add this suggestion to a batch that can be applied as a single commit.This suggestion is invalid because no changes were made to the code.Suggestions cannot be applied while the pull request is closed.Suggestions cannot be applied while viewing a subset of changes.Only one suggestion per line can be applied in a batch.Add this suggestion to a batch that can be applied as a single commit.Applying suggestions on deleted lines is not supported.You must change the existing code in this line in order to create a valid suggestion.Outdated suggestions cannot be applied.This suggestion has been applied or marked resolved.Suggestions cannot be applied from pending reviews.Suggestions cannot be applied on multi-line comments.Suggestions cannot be applied while the pull request is queued to merge.Suggestion cannot be applied right now. Please check back later.
Summary
VariableExactSumConstraint.__call__(no-multipliers path) buildssum_valueby accumulating assigned variable values plusmin(domain)as a placeholder for each unassigned variable. In theforward-check loop it then computed:
This double-counts the placeholder for the variable whose domain is
being pruned, making
temp_sumtoo large and hiding valid values.Minimal reproducer (returns
[]instead of[{a:1,b:2,c:3}, {a:2,b:1,c:3}]):With
a=1assigned andc=3assigned,sum_valueis1 + min([1,2]) = 2.The check
2 + 2 = 4 > 3then hidesb=2, even thougha + b = 1 + 2 = 3satisfies the constraint.
Fix
Subtract the placeholder for the variable being checked before adding the
candidate value:
The multipliers branch was not affected because it never adds a
placeholder (it only tracks
missing = Truewithout modifyingsum_value).Tests
All 34 existing constraint/solver tests continue to pass. The note
about
test_if_compiledfailing when.sofiles are absent is apre-existing CI condition unrelated to this fix.
This pull request was prepared with the assistance of AI, under my direction and review.