chocoteam / chocoteam/choco-solver
Deal with large domains in at_most and at_least
- Dominant language
- Java
- Stars
- 779
- Forks
- 159
- Avg merge
- 6d 9h
- Merged PRs (30d)
- 10
Description
Since at_most and at_least are used to decompose, resp., all_equal and not_all_equal, in `IIntConstraintFactory`, wouldn't it be nice to avoid computing the union of variables domain when domains are very big (which may occur when using (not_)all_equal) ?
The domain union is used to :
- to iterate over concerned variables, in `PropAtLeastNValues` and `PropAtMostNValues`
- to have an estimation of the map size required in `PropAtLeastNValues_AC`
I think these 3 propagators can be duplicated to deal with a range instead of the list of values.
That would prevent `OutOfMemoryError`.
See for instance: ChessboardColoration-40-40.xml.lzma (XCSP3)
Contributor guide
Research direction
Start with IIntConstraintFactory and the three named propagators: PropAtLeastNValues, PropAtMostNValues, and PropAtLeastNValues_AC. Reproduce the large-domain case using ChessboardColoration-40-40.xml.lzma, then trace where the domain union is built and how it drives iteration and map sizing. Done means large domains no longer cause OutOfMemoryError while these propagators retain their required behavior.
Written by the indexing model from the issue text.
Assessment
- Tech stack
- java
- Domain
- tooling
- Issue type
- Feature
- Difficulty
- 5/5
- Estimated time
- Over a week
- Activity status
- Stale
- Clarity
- Mostly clear
- Newbie friendliness
- 30/100