chocoteam / chocoteam/choco-solver

LastConflict is not state-of-the-art

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

Description

Not sure if this is actually a problem, but if I refer to Chapter 9.4.2 of the [following book](https://cse.unl.edu/~choueiry/Documents/Lecoutre-eBook-Constraint%20Networks.pdf) (p. 418), the version of LastConflict currently in the code is slightly incorrect.

The patch is, instead of this:
```java
V curDecVar = (V) decisionPath.getLastDecision().getDecisionVariable();
```
do this:
```java
Decision curDec = decisionPath.getLastDecision();
if (!curDec.hasNext() && curDec.getArity() > 1) return;
V curDecVar = curDec.getDecisionVariable();
```

I tested the two versions on XCSP3 instances:
- 'base' : current version
- 'sota': state of the art version

Image

There is no clear winner.
We could consider a new option… or not.

Contributor guide

Open the contributing guide

Research direction

Start by locating the LastConflict implementation and the decisionPath.getLastDecision() entry point, then compare its behavior with Chapter 9.4.2 of the linked book. Validate the current and proposed variants against the mentioned XCSP3 instances; done means the algorithmic choice and whether a new option is needed are resolved.

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
Active
Clarity
Mostly clear
Newbie friendliness
45/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.