Infeasibility regression for cumulative constraint between 9.1 and 9.2

[lalithsuresh]

I tried upgrading ortools from 9.1 to 9.2. The code is unchanged, but some models that use cumulative constraints that were previously feasible are now being marked infeasible.

What version of OR-Tools and what language are you using?
Version: v9.2
Language: Java

Which solver are you using (e.g. CP-SAT, Routing Solver, GLOP, BOP, Gurobi)

CP-SAT

What operating system (Linux, Windows, ...) and version?

Mac OS 11.6.2

What did you do?
Steps to reproduce the behavior:

The actual code that does the encoding is a big blob of generated code, but here is a minimal test case I was able to produce. Towards the end, I've marked the line that seems to be causing the model to become infeasible in 9.2.

    @Test
    public void capacityTestCase() {
        final CpModel model = new CpModel();
        final IntVar var1 = model.newIntVar(Integer.MIN_VALUE, Integer.MAX_VALUE, "CONTROLLABLE__C1[0]");
        final IntVar var2 = model.newIntVar(Integer.MIN_VALUE, Integer.MAX_VALUE, "CONTROLLABLE__C1[1]");
        model.addLinearExpressionInDomain(var1, Domain.fromValues(new long[] {0, 1}));
        model.addLinearExpressionInDomain(var2, Domain.fromValues(new long[] {0, 1}));
        capacityConstraint(model, List.of(var1, var2), new long[]{0L, 1L}, List.of(List.of(1L, 1L)),
                           List.of(List.of(1L, 1L)));
        final CpSolver solver = new CpSolver();
        solver.getParameters().setLogSearchProgress(true);
        solver.getParameters().setCpModelProbingLevel(0);
        solver.getParameters().setNumSearchWorkers(4);
        solver.getParameters().setMaxTimeInSeconds(1);
        final CpSolverStatus status = solver.solve(model);
        assertNotEquals(status, CpSolverStatus.INFEASIBLE);
    }

    public void capacityConstraint(final CpModel model, final List<IntVar> varsToAssign, final long[] domainArr,
                                   final List<List<Long>> demands, final List<List<Long>> capacities) {
        final int numTasks = varsToAssign.size();
        final int numResources = demands.size();
        final IntervalVar[] tasksIntervals = new IntervalVar[numTasks + capacities.get(0).size()];

        final Domain domainT = Domain.fromValues(domainArr);
        final Domain intervalRange = Domain.fromFlatIntervals(new long[] {domainT.min() + 1, domainT.max() + 1});
        final IntVar unitIntervalSize = model.newConstant(1);
        final List<IntVar> presenceLiterals = new ArrayList<>(numTasks);
        for (int i = 0; i < numTasks; i++) {
            final IntVar intervalEnd = model.newIntVarFromDomain(intervalRange, "");
            final IntVar presence = model.newBoolVar("");
            presenceLiterals.add(presence);
            model.addLinearExpressionInDomain(varsToAssign.get(i), domainT).onlyEnforceIf(presence);
            model.addLinearExpressionInDomain(varsToAssign.get(i), domainT.complement()).onlyEnforceIf(presence.not());
            // interval with start as taskToNodeAssignment and size of 1
            tasksIntervals[i] = model.newOptionalIntervalVar(varsToAssign.get(i), unitIntervalSize, intervalEnd,
                    presence, "");
        }

        // Create dummy intervals
        for (int i = numTasks; i < tasksIntervals.length; i++) {
            final int nodeIndex = i - numTasks;
            tasksIntervals[i] = model.newFixedInterval(domainArr[nodeIndex], 1, "");
        }

        // Convert to list of arrays
        final long[][] nodeCapacities = new long[numResources][];
        final long[] maxCapacities = new long[numResources];

        for (int i = 0; i < capacities.size(); i++) {
            final List<Long> vec = capacities.get(i);
            final long[] capacityArr = new long[vec.size()];
            long maxCapacityValue = Long.MIN_VALUE;
            for (int j = 0; j < capacityArr.length; j++) {
                capacityArr[j] = vec.get(j);
                maxCapacityValue = Math.max(maxCapacityValue, capacityArr[j]);
            }
            nodeCapacities[i] = capacityArr;
            maxCapacities[i] = maxCapacityValue;
        }

        // For each resource, create dummy demands to accommodate heterogeneous capacities
        final long[][] updatedDemands = new long[numResources][];
        for (int i = 0; i < numResources; i++) {
            final long[] demand = new long[numTasks + capacities.get(0).size()];

            // copy ver task demands
            int iter = 0;
            for (final long taskDemand: demands.get(i)) {
                demand[iter] = taskDemand;
                iter++;
            }

            // copy over dummy demands
            final long maxCapacity = maxCapacities[i];
            for (final long nodeHeterogeneityAdjustment: nodeCapacities[i]) {
                demand[iter] = maxCapacity - nodeHeterogeneityAdjustment;
                iter++;
            }
            updatedDemands[i] = demand;
        }

        // 2. Capacity constraints
        for (int i = 0; i < numResources; i++) {
            model.addCumulative(tasksIntervals, updatedDemands[i], maxCapacities[i]);
        }

        // Cumulative score
        for (int i = 0; i < numResources; i++) {
            final IntVar max = model.newIntVar(0, maxCapacities[i], "");
            model.addCumulative(tasksIntervals, updatedDemands[i], max); /// This line seems to be the culprit
            model.minimize(max);
        }
    }

Anything else we should know about your project / environment

[lperron]

Can you show the search log? Is the model infeasible or invalid? I suppose the latter because of potential overflows.

[lperron]

first remark:

calling minimize(max) in sequence will overwrite the objective each time.

[lalithsuresh]

Thanks for the pointer (this actually explains some other anomalies I was seeing)! I thought it was preparing a sum of objectives.

[lperron]

So I pushed the fix on master. It was indeed an overflow during presolve.

A quick note on the 9.3 release. I have completely rewritten the java API:

• I introduced a BoolVar class. You need it for OnlyEnforceIf()
• AddCumulative now takes one argument (the capacity) and returns a Cumulative constraint which contains APIs to add (interval, demand) incrementally. In your case, just model.addCumulative(capacity).addDemands(intervalsArray, demandsArray);

[lperron]

And thanks a lot for the bug report.

[lalithsuresh]

Thanks for the quick fix!