[BUG] Start and end of tasks are always enforced at root

[IgnaceBleukx]

Hi,

I'm attempting to model a half-reified Cumulative constraint (see sample code below).
However, while the "non-overlapness" of the Cumulative constraints is correctly reified, the link between start and end variables in the tasks is not reified with it.

E.g., the model with constraints [e == 1, bv -> Cumulative([s], [3], [e], [1],[1])] should be satisfied when the Boolean variable is set to False.
However, as the task is created at the toplevel of the constraint model, it will fail because of the e == 1 assignment.

Is this considered the expected behaviour of the tasks-constructor? And if so, how should I modify my model to properly reflect a truely half-reified Cumulative constraint?

import org.chocosolver.solver.Model;
import org.chocosolver.solver.variables.IntVar;
import org.chocosolver.solver.variables.BoolVar;
import org.chocosolver.solver.variables.Task;

public class CumulativeModel {
    public static void main(String[] args) {
        // Create a Choco model
        Model model = new Model("Cumulative Scheduling Model");

        // Define variables
        IntVar[] start = new IntVar[3];
        IntVar[] end = new IntVar[3];
        int[] duration = {3, 3, 3};
        IntVar[] demand = new IntVar[3];
        IntVar capacity = model.intVar("cap", 1,1);

        for (int i = 0; i < 3; i++) {
            start[i] = model.intVar("start[" + i + "]", 0, 5);
            end[i] = model.intVar("end[" + i + "]", 0, 5);
            demand[i] = model.intVar("demand[" + i +"]", 1,1);
        }

        // Make the tasks
        Task[] tasks = new Task[3];
        for (int i = 0; i < 3; i++) {
            tasks[i] = new Task(start[i], duration[i], end[i]);
        }

        // Define the Boolean variable
        BoolVar bv = model.boolVar("bv");
        // Add cumulative constraint wrapped in implication
        model.cumulative(tasks, demand, capacity).impliedBy(bv);

        // Add the constraint end[0] == 1
        model.arithm(end[0], "=", 1).post(); // This makes the model UNSAT

        // Solve the model
        if (model.getSolver().solve()) {
            System.out.println("Solution found:");
            for (int i = 0; i < 3; i++) {
                System.out.println("start[" + i + "] = " + start[i].getValue());
                System.out.println("end[" + i + "] = " + end[i].getValue());
            }
        } else {
            System.out.println("No solution found.");
        }
    }
}

I'm running on the latest release (v4.10.17)

Kind regards,
Ignace

[ArthurGodet]

Hi,

Yes, it is the expected behaviour for the Task objects. However, this is something we are questionning as it can lead to true faulty behaviour, such as the one described in #1114. We still have not decided how we will definitely handle such cases. For the case you have described, I would recommend to declare the propagators yourself :

new Constraint(ConstraintsName.CUMULATIVE, new Propagator[]{
    new PropGraphCumulative(start, duration, end, demand, capacity, false, Cumulative.Filter.DEFAULT.make(start.length)),
    new PropGraphCumulative(start, duration, end, demand, capacity, true, Cumulative.Filter.DEFAULT.make(start.length))
}).impliedBy(bv);

[IgnaceBleukx]

Hi, thanks for the quick answer!
I'm trying to post the half-reified propagator directly, but it results in the following exception when asserting the Boolean variable to true.

Unhandled exception: java.lang.ArithmeticException: / by zero
    at org.chocosolver.solver.constraints.nary.cumulative.NRJCumulFilter.lambda$new$0(NRJCumulFilter.java:51)
    at org.chocosolver.util.sort.ArraySort.mergeSort(ArraySort.java:104)
    at org.chocosolver.util.sort.ArraySort.mergeSort(ArraySort.java:110)
    at org.chocosolver.util.sort.ArraySort.sort(ArraySort.java:95)
    at org.chocosolver.solver.constraints.nary.cumulative.NRJCumulFilter.filter(NRJCumulFilter.java:76)
    at org.chocosolver.solver.constraints.nary.cumulative.DefaultCumulFilter.filter(DefaultCumulFilter.java:66)
    at org.chocosolver.solver.constraints.nary.cumulative.PropCumulative.filter(PropCumulative.java:149)
    at org.chocosolver.solver.constraints.nary.cumulative.PropGraphCumulative.filterAround(PropGraphCumulative.java:145)
    at org.chocosolver.solver.constraints.nary.cumulative.PropGraphCumulative.propagate(PropGraphCumulative.java:104)
    at org.chocosolver.solver.propagation.PropagationEngine.propagateEvents(PropagationEngine.java:231)
    at org.chocosolver.solver.propagation.PropagationEngine.propagate(PropagationEngine.java:213)
    at org.chocosolver.solver.Solver.doPropagate(Solver.java:543)
    at org.chocosolver.solver.Solver.propagate(Solver.java:555)
    at org.chocosolver.solver.Solver.searchLoop(Solver.java:343)
    at org.chocosolver.solver.Solver.solve(Solver.java:311)
    at org.chocosolver.solver.search.IResolutionHelper.findSolution(IResolutionHelper.java:102)
    at org.chocosolver.capi.SolverApi.findSolution(SolverApi.java:42)

I'm not really experienced with the Choco solver so not entirely sure how to continue with this.

Kind regards,
Ignace

[ArthurGodet]

Hi, I will look at this in more details at the end of the week. I'll try to find a way to make it work

[IgnaceBleukx]

Hi,
Thanks!
Below I attached the full model:

import org.chocosolver.solver.Model;
import org.chocosolver.solver.constraints.Constraint;
import org.chocosolver.solver.constraints.ConstraintsName;
import org.chocosolver.solver.constraints.Propagator;
import org.chocosolver.solver.constraints.nary.cumulative.PropGraphCumulative;
import org.chocosolver.solver.variables.BoolVar;
import org.chocosolver.solver.variables.IntVar;
import org.chocosolver.solver.constraints.nary.cumulative.Cumulative;
import java.util.ArrayList;

public class Example {

    public static void main(String[] args) {

        int nJobs = 60;
        int nMachines = 4;
        int horizon = 329;

        int [] capacities = {13,11,12,13};
        int [] machines =   {0,1,1,1,3,0,2,3,1,3,1,0,3,3,0,0,2,0,0,2,1,2,1,2,0,1,0,2,2,0,3,1,3,2,0,1,0,2,3,3,3,2,3,3,3,0,1,1,2,1,0,1,2,3,2,1,2,3,1,3};
        int [] resources = {10,1,9,4,1,10,6,8,6,3,7,8,1,9,6,2,2,7,5,8,4,4,5,1,9,7,3,3,7,6,4,7,4,1,9,7,5,1,5,1,9,6,1,9,7,4,8,2,7,5,2,1,6,7,3,4,9,7,3,1};
        int [] duration = {8,1,10,6,5,8,9,1,9,8,3,6,2,5,1,3,10,9,1,3,6,3,3,7,6,10,9,8,4,3,3,6,1,9,9,1,2,4,9,10,8,4,3,6,6,7,3,2,10,4,2,1,4,10,8,6,10,3,10,1,0};

    Model model = new Model("RCPSP");

        // Define start and end variables
        IntVar[] start = new IntVar[nJobs];
        IntVar[] end = new IntVar[nJobs];
        for (int i = 0; i < nJobs; i++) {
            start[i] = model.intVar("start_" + i,0,horizon);
            end[i] = model.intVar("end_" + i,0,horizon);
        }

        for (int mId =0; mId < nMachines; mId++) {
            // collect the tasks to run on this machine
            ArrayList<IntVar> mStart = new ArrayList<IntVar>() ;
            ArrayList<IntVar> mDur = new ArrayList<IntVar>() ;
            ArrayList<IntVar> mEnd = new ArrayList<IntVar>() ;
            ArrayList<IntVar> mRes = new ArrayList<IntVar>() ;
            for (int idx = 0; idx < nJobs; idx++) {
                if (machines[idx] == mId) {
                    mStart.add(start[idx]);
                    mDur.add(model.intVar(duration[idx]));
                    mEnd.add(end[idx]);
                    mRes.add(model.intVar(resources[idx]));
                }
            }

            // cast to arr
            BoolVar bv = model.boolVar("Machine"+mId);
            IntVar[] arrStart = mStart.toArray(new IntVar[0]);
            IntVar[] arrDur = mDur.toArray(new IntVar[0]);
            IntVar[] arrEnd = mEnd.toArray(new IntVar[0]);
            IntVar[] arrRes = mRes.toArray(new IntVar[0]);

            new Constraint(ConstraintsName.CUMULATIVE,new Propagator[]{
                    new PropGraphCumulative(arrStart, arrDur, arrEnd, arrRes, model.intVar(capacities[mId]), false, Cumulative.Filter.DEFAULT.make(start.length)),
                    new PropGraphCumulative(arrStart, arrDur, arrEnd, arrRes, model.intVar(capacities[mId]),true,Cumulative.Filter.DEFAULT.make(start.length)),
            }).impliedBy(bv);

            model.arithm(bv, ">=", 1).post();
        }

        System.out.println(model.getSolver().findSolution());
    }

}

[ArthurGodet]

Il seems that adding the following code solves the problem you are having :

for (int i = 0; i < arrStart.length; i++) {
    model.arithm(arrStart[i], "+", arrDur[i], "=", arrEnd[i]).impliedBy(bv);
}

Code on the branch of MR #1117 works fine on your code without adding the code above, which is a good news, despite this branch having other problems