chocoteam / chocoteam/choco-solver

Deal with large domains in at_most and at_least

Open
#530 0 comments 0 reactions 0 assignees View on GitHub
feature
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

Open the contributing 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

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.