search

chocoteam / choco-solver

An open-source Java library for Constraint Programming
http://choco-solver.org/
BSD 4-Clause "Original" or "Old" License
690 stars 143 forks source link

Fix issue relative to incomplete filtering of atLeastNValues and atMostNValues #966

Closed cprudhom closed 2 years ago

cprudhom commented 2 years ago

The two constraints model.atMostNValues() and model.atLeastNValues() do not filter correctly the n variable. Actually, atMostNValuesonly sharps the lower bound and atLeastNValues the upper bound. So they can produce inconsistent solutions like:

6  = atMostNValues([0,0,0,0,0])
2 = atLeastNValues([1,2,3,4,5])

This PR fixes this issue.

jgFages commented 2 years ago

Unless I misunderstood something, I disagree, atMostNValue and atLeastNValues are not supposed to be sharp, so those solutions are consistent : 6 = atMostNValues([0,0,0,0,0]) if the requirement is to have at most 6 values then 0,0,0,0 (only one value) is perfecty fine. And the filtering is not supposed to reduce the ub from 6 to 1. It is the same for the atLeastNValues.

If one wants to compute sharp bounds, then the "nvalues" constraint should be used instead.

cprudhom commented 2 years ago

Hmmm. I think I understand what I did wrong. I was referring to the global constraint catalog to check the right definition. However the name used in choco is not consistent with the one in the catalog. In choco, we use atMostNValue which refers to atmost_nvalue in the catalog but I was looking for atmost in the catalog. So you are right.

The only confusing thing is that Nmight not be fixe by propagation.