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

[hugbelval]

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

[hugbelval]

Commenting out this part in lines 720-723 of PropMultiCostRegular fixes the bug,

 while (this.toUpdateLeft[k].size() > 0) {
        this.graph.updateLeft(this.toUpdateLeft[k], toRemove, k, modifiedBound, this);
        if (toRemove.size() > 0) break;
  }

so the issue seems to be in the updateLeft method of the graph

[cprudhom]

Not easy.
This constraint was developed during a thesis in 2008, and the developer is no longer a contributor to Choco.
Finding the source of the bug may therefore take some time.

In any case, thank you for reporting the bug and providing the code to reproduce it.