chocoteam / chocoteam/choco-solver

[BUG] Exponential performance dropoff in addClauses with increasing number of AND subclauses in OR

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

Description

**Describe the bug**
When creating a clause of the form `LogOp.or(LogOp.and(a, b), LogOp.and(c, d), ...)` and adding it via `Model#addClauses`, the performance drops off exponentially.

I don't encounter the same performance issue when building an equivalent expression with `a.and(b).or(c.and(d).or(...))`.

**To Reproduce**
Here is some toy code that reproduces the issue. On my laptop, I start to see exponential increases in elapsed time around 10 AND clauses, and stop seeing progress above 17 AND clauses.
```
import org.chocosolver.solver.Model;
import org.chocosolver.solver.constraints.nary.cnf.LogOp;
import org.chocosolver.solver.variables.IntVar;

public class ChocoIssue {
public static void main(String[] args) {
Model m = new Model();
IntVar[] vars = m.intVarArray(2, 1, 2);
for (int i = 1; i < 100; i++) {
LogOp[] ops = new LogOp[i];
for (int j = 0; j < ops.length; j++) {
ops[j] = LogOp.and(vars[0].eq(1).decompose().reify(), vars[1].eq(2).decompose().reify());
}
long startTime = System.nanoTime();
m.addClauses(LogOp.or(ops));
long endTime = System.nanoTime();
System.out.println("Elapsed time for " + i + " clauses = " + (endTime - startTime));
}
}
}
```

**Expected behavior**
Since both approaches appear to be logically equivalent, I'd expect performance to be about the same. That said, I admit I'm a novice with this library and may absolutely be missing something silly that I'm doing here.

**Environment (please complete the following information):**
- Choco-solver version: 4.10.7
- JRE : 8

Contributor guide

Open the contributing guide

Research direction

Start at Model#addClauses with the LogOp.or(ops) reproduction shown in the issue, then compare its behavior with the equivalent nested a.and(b).or(...) expression. Profile increasing numbers of AND clauses and trace the relevant LogOp processing to identify the exponential path. Done means the benchmark no longer shows exponential growth and a regression test covers the case.

Written by the indexing model from the issue text.

Assessment

Tech stack
java
Domain
backend
Issue type
Bug
Difficulty
4/5
Estimated time
3-5 days
Activity status
Stale
Clarity
Mostly clear
Newbie friendliness
35/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.