Performance Issue with CPMpy's Cumulative Constraint

Question

I'm facing a performance issue using cpmpy's cumulative constraint with the ortools solver. Despite a reasonable number of tasks, performance degrades unexpectedly. Is this a bug, or is there a better way to formulate the problem?

Problem

I have a set of non-preemptive tasks to be completed within a given time horizon. My goal is to determine the minimum number of machines required to complete these tasks. The performance degradation occurs specifically when X machines are fully utilized, and there's a lone unassigned task shorter than the sum of the unused time on the preceding machines.

import cpmpy as cp
import logging
from typing import List


class CumulativeTestModel:
    def __init__(self, task_duration: int, nb_tasks: int, end_date: int):
        self.model: cp.Model = cp.Model()

        # Define variables
        self.objective: cp.IntVar = cp.intvar(0, nb_tasks)
        starts: List[cp.IntVar] = [cp.intvar(0, end_date) for _ in range(nb_tasks)]
        durations: List[int] = [task_duration] * nb_tasks
        ends: List[cp.IntVar] = [cp.intvar(0, end_date) for _ in range(nb_tasks)]
        demands: List[int] = [1] * nb_tasks

        # Add cumulative constraint to the model
        self.model += cp.Cumulative(
            start=starts,
            duration=durations,
            end=ends,
            demand=demands,
            capacity=self.objective,
        )

        # Minimize the objective variable
        self.model.minimize(self.objective)
        logging.info(f"Model created with {nb_tasks} tasks.")

    def run(self):
        solver = cp.model.SolverLookup.get("ortools", self.model)
        has_solution = solver.solve()

        if not has_solution:
            logging.info("No solution found.")
        else:
            logging.info(f"Solution found: {solver.status()} -> {self.objective.value()}")


if __name__ == "__main__":
    # Example usage
    CumulativeTestModel(task_duration=10, nb_tasks=3, end_date=15).run()
    CumulativeTestModel(task_duration=10, nb_tasks=11, end_date=55).run()
    CumulativeTestModel(task_duration=10, nb_tasks=21, end_date=105).run()

Versions Used: Python 3.8.10 ; cpmpy 0.9.18 ; ortools 9.8.3296 ; minizinc 0.9.0

What I've Tried:

Experimented with different problem combinations, observing exponential performance degradation as tasks increase.

[ortools]
Model created with 3 tasks.
Solution found: ExitStatus.OPTIMAL (0.0050022 seconds) -> 3

Model created with 5 tasks.
Solution found: ExitStatus.OPTIMAL (0.006417 seconds) -> 3

Model created with 7 tasks.
Solution found: ExitStatus.OPTIMAL (0.0109515 seconds) -> 3

Model created with 9 tasks.
Solution found: ExitStatus.OPTIMAL (0.263825 seconds) -> 3

Model created with 11 tasks.
Solution found: ExitStatus.OPTIMAL (1.9085797 seconds) -> 3

Model created with 13 tasks.
-Never ends-

Tested with other solvers provided by minizinc freely, and the issue persists to varying degrees.

[minizinc:chuffed]
Model created with 11 tasks.
Solution found: ExitStatus.OPTIMAL (0.564 seconds) -> 3

Model created with 13 tasks.
Solution found: ExitStatus.OPTIMAL (5.762 seconds) -> 3

Model created with 21 tasks.
-Never ends-

Question:

Any similar experiences with cpmpy and ortools? Bug possibility, or is there a more efficient formulation?

Appreciate any insights or guidance!

Answer 1

I have pushed an improvement to the cumulative linear relaxation that fixes the problem:

here is the output:

Model created with 3 tasks.
Solution found: 4 -> 3 in 0.009132000000000001 s
Model created with 11 tasks.
Solution found: 4 -> 3 in 0.002023 s
Model created with 13 tasks.
Solution found: 4 -> 3 in 0.000835 s
Model created with 21 tasks.
Solution found: 4 -> 3 in 0.0011120000000000001 s