Optimized Constraint scheduling with Google OR Tools slow and not finding a solution

Question

Our team is trying to do constraint scheduling, requiring the model to fill in who will do which tasks on which day. We started from the https://developers.google.com/optimization/scheduling/employee_scheduling example. We succeeded in scheduling simple, obvious things eg assigning a task after another task, but the moment we increase complexity or size the model is always unable to provide a feasible solution. We tried modelling the constraints differently in the ModelWaitingForConstraintsOptimized method. But to no avail.

using Binocs.Scheduling.AI.Host.Data;
using Binocs.Scheduling.AI.Host.Domain
using Google.OrTools.Sat;
using Constraint = Binocs.Scheduling.AI.Host.Domain.Constraint;

namespace Binocs.Scheduling.AI.Host;

public class Program
{

    public static void Main()
    {
        var scheduleItems = new ScheduleItemQuery().Query().ToArray();
        var teamMembers = (new TeamMembersQuery().Query()).ToDictionary(_ => _.Id);
        var equipments = (new EquipmentsQuery().Query()).ToDictionary(_ => _.Id);
        var teamMemberAvailabilities = new TeamMembersAvailabilitiesQuery().Query(teamMembers.Keys);
        var equipmentAvailabilities = new EquipmentAvailabilitiesQuery().Query(equipments.Keys);
        var constraints = (new ConstraintsQuery().Query()).GroupBy(_ => _.From).ToDictionary(_ => _.Key, _ => _.ToArray());

        #region AIData
        var horizon = new Horizon(8);

        var time = new Time(DateTime.Today);

        var aiScheduleItemFactory = new AIScheduleItemFactory(time);
        var aiAvailabilityFactory = new AIAvailabilityFactory(time);
        var aiScheduledItemFactory = new AIScheduledItemFactory(time);

        var aiItems = scheduleItems.Select(aiScheduleItemFactory.Create).ToArray();
        var aiScheduledItems = scheduleItems.Select(aiScheduledItemFactory.Create).ToArray();

        var allAIAvailabilities = teamMemberAvailabilities.Select(aiAvailabilityFactory.Create)
            .Concat(equipmentAvailabilities.Select(aiAvailabilityFactory.Create)).ToArray();

        var availabilitiesPerResource = allAIAvailabilities
            .Where(_ => _.Offset >= 0 && horizon.WithinHorizon(_.Offset))
            .GroupBy(_ => _.Id)
            .OrderBy(_ => _.Key)
            .ToArray();

        var horizonCompensatedAvailabilities = availabilitiesPerResource.ToDictionary(_ => _.Key, _ =>
        {
            var arr = horizon.EmptyHorizon();

            foreach (var aiTeamMemberAvailability in _)
            {
                arr[aiTeamMemberAvailability.Offset] = aiTeamMemberAvailability.Hours;
            }

            return arr;
        });

        var taskSizes = aiItems.Select(_ => _.PlannedHours).ToArray();
        var dueIntervals = aiItems.Select(_ => _.Deadline).ToArray();
        var allAvailabilities = horizonCompensatedAvailabilities.Select(_ => _.Value).ToArray();

        var totalDistinctWorkers = allAvailabilities.Length;
        var totalDistinctTasks = taskSizes.Length;
        var totalDistinctIntervals = horizon.Intervals;

        var indexedDistinctWorkers = Enumerable.Range(0, totalDistinctWorkers).ToArray();
        var indexedDistinctTasks = Enumerable.Range(0, totalDistinctTasks).ToArray();
        var indexedDistinctIntervals = Enumerable.Range(0, totalDistinctIntervals).ToArray();
        #endregion

        #region AIModel

        var model = new CpModel();
        var allVariablesTheAINeedsToFillIn = new IntVar[totalDistinctWorkers, totalDistinctTasks, totalDistinctIntervals];
        var flattenedAllVariablesTheAINeedsToFillIn = new IntVar[totalDistinctWorkers * totalDistinctTasks * totalDistinctIntervals];

        ModelCompetences(indexedDistinctWorkers, indexedDistinctTasks, indexedDistinctIntervals, allAIAvailabilities, scheduleItems, allVariablesTheAINeedsToFillIn, model, totalDistinctWorkers, totalDistinctTasks, flattenedAllVariablesTheAINeedsToFillIn);

        ModelAvailabilities(indexedDistinctIntervals, indexedDistinctWorkers, totalDistinctTasks, indexedDistinctTasks, allVariablesTheAINeedsToFillIn, model, taskSizes, allAvailabilities);

        ModelAssignments(indexedDistinctTasks, totalDistinctWorkers, totalDistinctIntervals, indexedDistinctWorkers, indexedDistinctIntervals, allVariablesTheAINeedsToFillIn, model);

        var taskIntervals = new IntVar[totalDistinctTasks];

        ModelDates(indexedDistinctTasks, taskIntervals, model, totalDistinctIntervals, indexedDistinctWorkers, indexedDistinctIntervals, allVariablesTheAINeedsToFillIn);

        ModelWaitingForConstraints(scheduleItems, constraints, model, taskIntervals);
        //ModelWaitingForConstraintsOptimized(scheduleItems, constraints, model, horizon, indexedDistinctWorkers, flattenedAllVariablesTheAINeedsToFillIn);

        ModelEquipmentAtSameTimeAsTeammember(scheduleItems, model, taskIntervals);

        ModelObjective(flattenedAllVariablesTheAINeedsToFillIn, indexedDistinctWorkers, indexedDistinctTasks, indexedDistinctIntervals, totalDistinctWorkers, totalDistinctTasks, dueIntervals, taskSizes, model);

        #endregion

        #region Solve
        var solver = new CpSolver();
        var status = solver.Solve(model);
        Console.WriteLine($"Solve status: {status}");
        if (status == CpSolverStatus.Optimal || status == CpSolverStatus.Feasible)
        {
            var resourceLookup = availabilitiesPerResource.Select(_ => _.First()).ToArray();
            Console.WriteLine($"Total cost: {solver.ObjectiveValue}\n");
            foreach (var interval in indexedDistinctIntervals)
            {
                foreach (var worker in indexedDistinctWorkers)
                {
                    foreach (var task in indexedDistinctTasks)
                    {
                        if (solver.Value(allVariablesTheAINeedsToFillIn[worker, task, interval]) > 0.5)
                        {
                            var late = interval > dueIntervals[task] ? "L" : "T";
                            aiScheduledItems[task].WithPlanned(interval);
                            aiScheduledItems[task].WithResource(resourceLookup[worker].Id);
                            Console.WriteLine($"{late}{taskSizes[task]}  interval {interval} - Due {dueIntervals[task]} - Size {taskSizes[task]} - Worker {(resourceLookup[worker].ForEquipment ? equipments[resourceLookup[worker].Id].Code : teamMembers[resourceLookup[worker].Id].Code)} assigned to task {scheduleItems[task].ScheduleItemId} - {scheduleItems[task].ServiceItemActivityId} {(scheduleItems[task].EquipmentPlannedHours == 0m ? "" : "EQ")}");
                        }
                    }
                }
            }
        }
        else
        {
            Console.WriteLine("No solution found.");
        }
        Console.WriteLine("Statistics");
        Console.WriteLine($"  - conflicts : {solver.NumConflicts()}");
        Console.WriteLine($"  - branches  : {solver.NumBranches()}");
        Console.WriteLine($"  - wall time : {solver.WallTime()}s");
        #endregion

    }

    #region ModelMethods
    static void ModelCompetences(int[] indexedDistinctWorkers, int[] indexedDistinctTasks, int[] indexedDistinctIntervals,
        AIAvailability[] allAiAvailabilities, ScheduleItem[] scheduleItems, IntVar[,,] allVariablesTheAiNeedsToFillIn,
        CpModel cpModel, int totalDistinctWorkers, int totalDistinctTasks,
        IntVar[] flattenedAllVariablesTheAiNeedsToFillIn)
    {
        foreach (var worker in indexedDistinctWorkers)
        {
            foreach (var task in indexedDistinctTasks)
            {
                foreach (var interval in indexedDistinctIntervals)
                {
                    if (allAiAvailabilities[worker].IsCompetentFor(scheduleItems[task]))
                    {
                        allVariablesTheAiNeedsToFillIn[worker, task, interval] =
                            cpModel.NewBoolVar($"allVariablesTheAINeedsToFillIn[{worker},{task},{interval}]");
                    }
                    else
                    {
                        allVariablesTheAiNeedsToFillIn[worker, task, interval] =
                            cpModel.NewConstant(0, $"allVariablesTheAINeedsToFillIn[{worker},{task},{interval}]");
                    }

                    var flattenedIndex =
                        MatrixOperations.Flatten(worker, task, interval, totalDistinctWorkers, totalDistinctTasks);
                    flattenedAllVariablesTheAiNeedsToFillIn[flattenedIndex] =
                        allVariablesTheAiNeedsToFillIn[worker, task, interval];
                }
            }
        }
    }

    static void ModelAvailabilities(int[] indexedDistinctIntervals, int[] indexedDistinctWorkers, int totalDistinctTasks, int[] indexedDistinctTasks,
        IntVar[,,] intVars, CpModel model, int[] taskSizes, int[][] allAvailabilities)
    {
        foreach (var interval in indexedDistinctIntervals)
        {
            foreach (var worker in indexedDistinctWorkers)
            {
                var vars = new IntVar[totalDistinctTasks];
                foreach (var task in indexedDistinctTasks)
                {
                    vars[task] = intVars[worker, task, interval];
                }

                model.Add(LinearExpr.ScalProd(vars, taskSizes) <= allAvailabilities[worker][interval]);
            }
        }
    }

    static void ModelAssignments(int[] totalDistinctTasks, int totalDistinctWorkers, int totalDistinctIntervals,
        int[] indexedDistinctWorkers, int[] indexedDistinctIntervals, IntVar[,,] allVariablesTheAiNeedsToFillIn,
        CpModel model)
    {
        foreach (var task in totalDistinctTasks)
        {
            var vars = new IntVar[totalDistinctWorkers * totalDistinctIntervals];
            foreach (var worker in indexedDistinctWorkers)
            {
                foreach (var interval in indexedDistinctIntervals)
                {
                    vars[MatrixOperations.Flatten(worker, interval, totalDistinctWorkers)] = allVariablesTheAiNeedsToFillIn[worker, task, interval];
                }
            }

            model.Add(LinearExpr.Sum(vars) == 1);
        }
    }

    static void ModelWaitingForConstraints(ScheduleItem[] scheduleItems, Dictionary<int, Constraint[]> constraintsMap, CpModel model,
        IntVar[] taskIntervals)
    {
        for (var i = 0; i < scheduleItems.Length; i++)
        {
            var current = scheduleItems[i];
            if (!constraintsMap.TryGetValue(current.ServiceItemActivityId, out var applicableConstraints)) continue;
            foreach (var c in applicableConstraints)
            {
                var related = scheduleItems.Select((si, i) => new { si, i }).Where(_ =>
                    _.si.ScheduleItemId == current.ScheduleItemId && _.si.ServiceItemActivityId == c.To);
                foreach (var otherSi in related)
                {
                    switch (c.WaitingForType)
                    {
                        case 0:
                            model.Add(taskIntervals[i] >= taskIntervals[otherSi.i] + c.Value);
                            break;
                        case 1:
                            model.Add(taskIntervals[i] == taskIntervals[otherSi.i] + c.Value);
                            break;
                        case 2:
                            model.Add(taskIntervals[i] <= taskIntervals[otherSi.i] + c.Value);
                            break;
                    }
                }
            }
        }
    }

    static void ModelWaitingForConstraintsOptimized(ScheduleItem[] scheduleItems, Dictionary<int, Constraint[]> constraintsMap, CpModel model, Horizon horizon, int[] indexedDistinctWorkers, IntVar[] flattenedAllVariablesTheAINeedsToFillIn)
    {
        for (var scheduleItemIndex = 0; scheduleItemIndex < scheduleItems.Length; scheduleItemIndex++)
        {
            var current = scheduleItems[scheduleItemIndex];
            if (!constraintsMap.TryGetValue(current.ServiceItemActivityId, out var applicableConstraints)) continue;
            foreach (var c in applicableConstraints)
            {
                var related = scheduleItems.Select((si, i) => new { si, i }).Where(_ =>
                      _.si.ScheduleItemId == current.ScheduleItemId && _.si.ServiceItemActivityId == c.To).ToList();
                for (var horizonDayIndex = 0; horizonDayIndex < horizon.Value.Length; horizonDayIndex++)
                {
                    for (var workerIndex = 0; workerIndex < indexedDistinctWorkers.Length; workerIndex++)
                    {
                        var d1 =
                            MatrixOperations.Flatten(workerIndex, scheduleItemIndex, horizonDayIndex, indexedDistinctWorkers.Length, scheduleItems.Length);

                        foreach (var otherSi in related)
                        {
                            switch (c.WaitingForType)
                            {
                                case 0:
                                    var endDayAtLeast = Math.Min(horizonDayIndex + c.Value, horizon.Value.Length - 1);
                                    for (var day = 0; day < endDayAtLeast; day++)
                                    {
                                        var d2Atleast =
                                            MatrixOperations.Flatten(workerIndex, otherSi.i, day, indexedDistinctWorkers.Length, scheduleItems.Length);
                                        model.AddImplication(flattenedAllVariablesTheAINeedsToFillIn[d1], flattenedAllVariablesTheAINeedsToFillIn[d2Atleast].Not());
                                    }
                                    break;
                                case 1:
                                    var exactDay = horizonDayIndex + c.Value;
                                    if (exactDay > horizon.Value.Length - 1) break;
                                    var d2Exact =
                                        MatrixOperations.Flatten(workerIndex, otherSi.i, exactDay, indexedDistinctWorkers.Length, scheduleItems.Length);
                                    model.AddImplication(flattenedAllVariablesTheAINeedsToFillIn[d1], flattenedAllVariablesTheAINeedsToFillIn[d2Exact]);
                                    break;
                                case 2:
                                    var startDayAtMost = horizonDayIndex + c.Value;
                                    var endDayAtMost = horizon.Value.Length;
                                    for (var day = startDayAtMost; day < endDayAtMost; day++)
                                    {
                                        var d2AtMost =
                                            MatrixOperations.Flatten(workerIndex, otherSi.i, day, indexedDistinctWorkers.Length, scheduleItems.Length);
                                        model.AddImplication(flattenedAllVariablesTheAINeedsToFillIn[d1], flattenedAllVariablesTheAINeedsToFillIn[d2AtMost].Not());
                                    }
                                    break;
                            }
                        }
                    }
                }

            }
        }
    }

    static void ModelEquipmentAtSameTimeAsTeammember(ScheduleItem[] scheduleItems, CpModel model, IntVar[] taskIntervals)
    {
        foreach (var g in scheduleItems.Select((si, i) => new { si, i })
                     .GroupBy(_ => new { _.si.ScheduleItemId, _.si.ServiceItemActivityId }).Where(_ => _.Count() > 1))
        {
            model.Add(taskIntervals[g.First().i] == taskIntervals[g.Skip(1).First().i]);
        }
    }

    static void ModelDates(int[] indexedDistinctTasks, IntVar[] taskIntervals, CpModel model, int totalDistinctIntervals,
        int[] indexedDistinctWorkers, int[] indexedDistinctIntervals, IntVar[,,] allVariablesTheAiNeedsToFillIn)
    {
        foreach (var task in indexedDistinctTasks)
        {
            taskIntervals[task] = model.NewIntVar(0, totalDistinctIntervals, "taskInterval");
            foreach (var worker in indexedDistinctWorkers)
            {
                foreach (var interval in indexedDistinctIntervals)
                {
                    model.Add(taskIntervals[task] == interval).OnlyEnforceIf(allVariablesTheAiNeedsToFillIn[worker, task, interval]);
                }
            }
        }
    }

    static void ModelObjective(IntVar[] flattenedAllVariablesTheAiNeedsToFillIn, int[] indexedDistinctWorkers, int[] indexedDistinctTasks,
        int[] indexedDistinctIntervals, int totalDistinctWorkers, int totalDistinctTasks, int[] dueIntervals, int[] taskSizes,
        CpModel model)
    {
        var xDuePassedFlat = Enumerable.Range(0, flattenedAllVariablesTheAiNeedsToFillIn.Length).ToArray();
        foreach (var worker in indexedDistinctWorkers)
        {
            foreach (var task in indexedDistinctTasks)
            {
                foreach (var interval in indexedDistinctIntervals)
                {
                    xDuePassedFlat[MatrixOperations.Flatten(worker, task, interval, totalDistinctWorkers, totalDistinctTasks)] = Math.Max(0, (interval - dueIntervals[task])) - dueIntervals[task];
                }
            }
        }

        model.Minimize(LinearExpr.ScalProd(flattenedAllVariablesTheAiNeedsToFillIn, xDuePassedFlat));
    }
    #endregion
}

Answer 1

just try

solver.StringParameters = "num_search_workers:8,log_seach_progress:true";

Furthermore, this example uses the assumptions that num_shift_types == num_nurses. If this is false, there are no solutions.

When I run the model you sent me, I get:

Starting Search at 14.24s with 16 workers.
10 full subsolvers: [default_lp, no_lp, max_lp, core, reduced_costs, pseudo_costs, quick_restart, quick_restart_no_lp, lb_tree_search, probing]
Interleaved subsolvers: [feasibility_pump, rnd_var_lns_default, rnd_cst_lns_default, graph_var_lns_default, graph_cst_lns_default, rins_lns_default, rens_lns_default]
#Bound  17.99s best:inf   next:[-91170,1793684] am1_presolve num_literals:163919 num_am1:129 increase:357955 work_done:100382751
#1      18.23s best:-514  next:[-91170,-515] core fixed_bools:63/171500
#Bound  18.24s best:-514  next:[-90570,-515] bool_core num_cores:0 [] assumptions:139518 depth:0 fixed_bools:63/171500
#2      18.30s best:-1043 next:[-90570,-1044] core fixed_bools:83/171500
#Bound  18.31s best:-1043 next:[-90370,-1044] bool_core num_cores:0 [] assumptions:139498 depth:0 fixed_bools:83/171500
#3      18.36s best:-1504 next:[-90370,-1505] quick_restart_no_lp fixed_bools:185/171371
#Bound  18.62s best:-1504 next:[-2305,-1505] probing initial_propagation
#Bound  20.50s best:-1504 next:[-1880,-1505] probing
#4      21.48s best:-1593 next:[-1880,-1594] graph_cst_lns_default(d=0.29 s=219 t=0.10 p=0.00)
#Bound  22.11s best:-1593 next:[-1600,-1594] max_lp
#5      22.38s best:-1594 next:[-1600,-1595] graph_cst_lns_default(d=0.28 s=224 t=0.10 p=0.33)
#6      24.04s best:-1595 next:[-1600,-1596] graph_var_lns_default(d=0.94 s=233 t=0.10 p=1.00)
#7      25.90s best:-1596 next:[-1600,-1597] rnd_var_lns_default(d=0.57 s=246 t=0.10 p=0.50)
#8      26.53s best:-1597 next:[-1600,-1598] graph_cst_lns_default(d=0.53 s=249 t=0.10 p=0.57)
#9      28.21s best:-1598 next:[-1600,-1599] rnd_var_lns_default(d=0.75 s=256 t=0.10 p=0.60)
#10     28.45s best:-1599 next:[-1600,-1600] rnd_cst_lns_default(d=0.58 s=257 t=0.10 p=0.56)
#11     30.27s best:-1600 next:[]         graph_cst_lns_default(d=0.80 s=259 t=0.10 p=0.70)
#Done   30.28s core
#Done   30.31s probing
#Done   30.45s pseudo_costs

...

CpSolverResponse summary:
status: OPTIMAL
objective: -1600
best_bound: -1600
booleans: 171371
conflicts: 0
branches: 10123
propagations: 10736218
integer_propagations: 10978261
restarts: 10077
lp_iterations: 24982
walltime: 31.5911
usertime: 252.682
deterministic_time: 67.9784
gap_integral: 7.71199

For a more general problem, you should look at the shift scheduling example