chocoteam / chocoteam/choco-solver

[BUG] MultiCostRegular constraint finds suboptimal solution, seemingly filters out the correct solution

Open
#1,163 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**
In this example, a model using the MultiCostRegular constraint seems to filter out the correct solution. As shown in the output, the model finds a solution with a sum of 118, but there exists a solution with a sum of 138 which is better.
The correct solution is found when we enforce periods[3] = 0.

**To Reproduce**
```
package org.example;

import org.chocosolver.solver.Model;
import org.chocosolver.solver.constraints.nary.automata.FA.CostAutomaton;
import org.chocosolver.solver.constraints.nary.automata.FA.FiniteAutomaton;
import org.chocosolver.solver.constraints.nary.automata.FA.ICostAutomaton;
import org.chocosolver.solver.variables.IntVar;

import java.util.Random;

public class ChocoBugMultiCostReg {
private static final Random generator = new Random(29);
private static int[][] valueGainedFromActivity;
private static Model model;
private static IntVar[] occurrences;
private static IntVar[] periods;
private static FiniteAutomaton automaton;

private static FiniteAutomaton getFiniteAutomaton() {
FiniteAutomaton auto = new FiniteAutomaton();

int startState = auto.addState();
int endState = auto.addState();
int[] before0 = new int[5];
int[] after0 = new int [5];
int[] zero = new int [5];
for (int i = 0; i < 5; i++) {
before0[i] = auto.addState();
after0[i] = auto.addState();
zero[i] = auto.addState();
}
auto.setInitialState(startState);
auto.addTransition(startState, before0[0], 1);
for(int i = 0; i< 2; i++) {
auto.addTransition(before0[i], before0[i+1], 1);
}

for(int i = 0; i< 3; i++) {
auto.addTransition(before0[i], zero[i+1], 0);
}

for(int i = 1; i< 4; i++) {
auto.addTransition(zero[i], after0[i+1], 1);
}
for(int i = 2; i< 4; i++) {
auto.addTransition(after0[i], after0[i+1], 1);
}
auto.addTransition(after0[4], endState, 1);

auto.setFinal(endState);
return auto;
}

private static void generateCosts() {
valueGainedFromActivity = new int[6][2];
for(int i = 0; i < 6; i++) {
valueGainedFromActivity[i][0] = 0;
valueGainedFromActivity[i][1] = generator.nextInt(50);
}
}

public static void main(String[] args){
generateCosts();

System.out.println("Suboptimal solution: ");
createModel();
searchNormal();

System.out.println("Optimal solution with added constraint: ");
createModel();
searchWithConstraint();
}

private static void createModel(){
model = new Model();

occurrences = new IntVar[2];
occurrences[0] = model.intVar("occZero", 1, 1);
occurrences[1] = model.intVar("occOne", 5, 5);

periods = new IntVar[6];
for(int i = 0; i < periods.length; i++) {
periods[i] = model.intVar("per" + i, 0, 1);
}
automaton = getFiniteAutomaton();

makeMultiCostRegConstraint();
}

private static void makeMultiCostRegConstraint() {
int[] infs = new int[occurrences.length];
int[] sups = new int[occurrences.length];

for (int i = 0; i < occurrences.length; i++) {
infs[i] = occurrences[i].getLB();
sups[i] = occurrences[i].getUB();
}

ICostAutomaton costAuto = CostAutomaton.makeMultiResources(automaton, getLayerValueResourceArray(), infs, sups);
model.multiCostRegular(periods, occurrences, costAuto).post();
}

private static void searchNormal(){
generalSearch();
}

private static void searchWithConstraint(){
model.arithm(periods[3], "=", 0).post();
generalSearch();
}

private static void generalSearch(){
IntVar[] valueGainedByPeriod = new IntVar[periods.length];
for(int i = 0; i < valueGainedByPeriod.length; i++) {
valueGainedByPeriod[i] = model.intVar("valueGainedPeriod"+i,0,1000);
model.element(valueGainedByPeriod[i], valueGainedFromActivity[i], periods[i]).post();
}
IntVar sum = model.intVar("sum", 0,100000);
model.sum(valueGainedByPeriod, "=", sum).post();
System.out.println(model.getSolver().findOptimalSolution(sum, true));
}

private static int[][][] getLayerValueResourceArray(){
int[][][] lvrArray = new int[periods.length][occurrences.length][occurrences.length];
for (int i = 0; i < periods.length; i++) {
for (int j = 0; j < occurrences.length; j++) {
for (int k = 0; k < occurrences.length; k++) {
lvrArray[i][j][k] = 0;
}
lvrArray[i][j][j] = 1;
}
}
return lvrArray;
}
}

```

**Expected behavior**
Expected the solver to find the solution with sum=138

**Possible solution**
The issue may be in the updateLeft method of the StoredDirectedMultiGraph class. It seems to flag a node to be removed that should not be. I can investigate further.

**Environment (please complete the following information):**
- Choco-solver version: 4.10.14

Contributor guide

Open the contributing guide

Assessment

This issue has not been assessed yet.

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.