chocoteam / chocoteam/choco-solver

Reduce memory footprint for CompactTable

Open
#1,017 1 comment 0 reactions 0 assignees View on GitHub
Dominant language
Java
Stars
779
Forks
159
Avg merge
6d 9h
Merged PRs (30d)
10

Description

I think there is room to reduce CT+ structure initialization when tuples' ranges are smaller than domains' range.

For instance:
```java
IntVar[] xs = model.intVarArray("X", 4, 0, 99_999);
Tuples comb = new Tuples(true);
comb.setUniversalValue(-1);
comb.add(1, 0, -1, 0);
comb.add(1, 3, -1, 3500);
comb.add(2, 3, -1, 3500);
comb.add(4, 3, -1, 3500);
model.table(xs, comb, "CT+").post();
```
CT will allocate `supports` array (of longs) of size 99_999, whereas smaller size would do the job.

I'm not saying it is easy to do, but it could be useful.

Note that I agree that the domain could be reduced at the first place, but sometimes (when parsing instances for instance) this is quite complicated.

PS: same goes for "STR2+"

Contributor guide

Open the contributing guide

Research direction

Start by locating the CompactTable implementation behind the CT+ option and the corresponding STR2+ implementation, then inspect how supports are sized from tuple and domain ranges. Measure the example's allocation and define completion as preserving solver behavior while avoiding arrays sized to the full domain when smaller tuple ranges suffice, with regression coverage for both propagators.

Written by the indexing model from the issue text.

Assessment

Tech stack
java
Domain
backend
Issue type
Feature
Difficulty
5/5
Estimated time
Over a week
Activity status
Stale
Clarity
Mostly clear
Newbie friendliness
35/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.