How to speed up construction phase whilst having an trivial overlapping constraint

Question

We're are trying to put together a proof of concept planning constraints solver using OptaPlanner. However the construction phase seems slow for even a trivial set of constraints i.e. assign to one User with no overlapping Tasks for that User.

Problem overview:

We are assigning Tasks to Users Only one Task can be assigned to User The Tasks can be variable length: 1-16 hours Users can only do one Task at a time Users have 8 hours per day We are using the Time Grain pattern - 1 grain = 1 hour. See constraints configuration below.

This works fine (returns in a 20 seconds) for a small number of Users and Tasks e.g. 30 Users / 1000 Tasks but when we start scaling up the performance rapidly drops off. Simply increasing the number of Users without increasing the number of Tasks (300 Users / 1000 Tasks) increases the solve time to 120 seconds.

But we hope to scale up to 300 Users / 10000 Tasks and incorporate much more elaborate constraints.

Is there a way to optimise the constraints/configuration?

Constraint constraint1 = constraintFactory.forEach(Task.class)
                            .filter(st -> st.getUser() == null)
                            .penalize("Assign Task", HardSoftLongScore.ONE_HARD);

Constraint constraint2 = constraintFactory.forEach(Task.class)
                            .filter(st -> st.getStartDate() == null)
                            .penalize("Assign Start Date", HardSoftLongScore.ONE_HARD);      

Constraint constraint3 = constraintFactory
                            .forEachUniquePair(Task.class,
                                                equal(Task::getUser), 
                                                overlapping(st -> st.getStartDate().getId(), 
                                                                st -> st.getStartDate().getId() + st.getDurationInHours()))
                            .penalizeLong("Crew conflict", HardSoftLongScore.ONE_HARD,
                            (st1, st2) -> {
                                int x1 = st1.getStartDate().getId() > st2.getStartDate().getId() ? st1.getStartDate().getId(): st2.getStartDate().getId();
                                int x2 = st1.getStartDate().getId() + st1.getDurationInHours()  < st2.getStartDate().getId() + st2.getDurationInHours() ? 
                                            st1.getStartDate().getId() + st1.getDurationInHours(): st2.getStartDate().getId() + + st2.getDurationInHours();
                                
                                return Math.abs(x2-x1);
                                
                            });

Answer 1

constraint1 and constraint2 seem redundant to me. The Construction Heuristic phase will initialize all planning variables (automatically, without being penalized for not doing so) and Local Search will never set a planning variable to null (unless you're optimizing an over-constrained problem).

You should be able to remove constraint1 and constraint2 without impact on the solution quality.

Other than that, it seems you have two planning variables (Task.user and Task.startDate). By default, in each CH step, both variables of a selected entity are initialized "together". That means OptaPlanner looks for the best initial pair of values for that entity in the Cartesian product of all users and all time grains. This scales poorly.

See the Scaling construction heuristics chapter to learn how to change that default behavior and for other ways how to make Construction Heuristic algorithms scale better.