title: Optimized Constraint scheduling with Google OR Tools slow and not finding a solution
body: <p>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 <a href="https://developers.google.com/optimization/scheduling/employee_scheduling" rel="nofollow noreferrer">https://developers.google.com/optimization/scheduling/employee_scheduling</a> 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.</p>
  <pre><code>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(_ =&gt; _.Id);
          var equipments = (new EquipmentsQuery().Query()).ToDictionary(_ =&gt; _.Id);
          var teamMemberAvailabilities = new TeamMembersAvailabilitiesQuery().Query(teamMembers.Keys);
          var equipmentAvailabilities = new EquipmentAvailabilitiesQuery().Query(equipments.Keys);
          var constraints = (new ConstraintsQuery().Query()).GroupBy(_ =&gt; _.From).ToDictionary(_ =&gt; _.Key, _ =&gt; _.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(_ =&gt; _.Offset &gt;= 0 &amp;&amp; horizon.WithinHorizon(_.Offset))
              .GroupBy(_ =&gt; _.Id)
              .OrderBy(_ =&gt; _.Key)
              .ToArray();
  
          var horizonCompensatedAvailabilities = availabilitiesPerResource.ToDictionary(_ =&gt; _.Key, _ =&gt;
          {
              var arr = horizon.EmptyHorizon();
  
              foreach (var aiTeamMemberAvailability in _)
              {
                  arr[aiTeamMemberAvailability.Offset] = aiTeamMemberAvailability.Hours;
              }
  
              return arr;
          });
  
          var taskSizes = aiItems.Select(_ =&gt; _.PlannedHours).ToArray();
          var dueIntervals = aiItems.Select(_ =&gt; _.Deadline).ToArray();
          var allAvailabilities = horizonCompensatedAvailabilities.Select(_ =&gt; _.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($&quot;Solve status: {status}&quot;);
          if (status == CpSolverStatus.Optimal || status == CpSolverStatus.Feasible)
          {
              var resourceLookup = availabilitiesPerResource.Select(_ =&gt; _.First()).ToArray();
              Console.WriteLine($&quot;Total cost: {solver.ObjectiveValue}\n&quot;);
              foreach (var interval in indexedDistinctIntervals)
              {
                  foreach (var worker in indexedDistinctWorkers)
                  {
                      foreach (var task in indexedDistinctTasks)
                      {
                          if (solver.Value(allVariablesTheAINeedsToFillIn[worker, task, interval]) &gt; 0.5)
                          {
                              var late = interval &gt; dueIntervals[task] ? &quot;L&quot; : &quot;T&quot;;
                              aiScheduledItems[task].WithPlanned(interval);
                              aiScheduledItems[task].WithResource(resourceLookup[worker].Id);
                              Console.WriteLine($&quot;{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 ? &quot;&quot; : &quot;EQ&quot;)}&quot;);
                          }
                      }
                  }
              }
          }
          else
          {
              Console.WriteLine(&quot;No solution found.&quot;);
          }
          Console.WriteLine(&quot;Statistics&quot;);
          Console.WriteLine($&quot;  - conflicts : {solver.NumConflicts()}&quot;);
          Console.WriteLine($&quot;  - branches  : {solver.NumBranches()}&quot;);
          Console.WriteLine($&quot;  - wall time : {solver.WallTime()}s&quot;);
          #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($&quot;allVariablesTheAINeedsToFillIn[{worker},{task},{interval}]&quot;);
                      }
                      else
                      {
                          allVariablesTheAiNeedsToFillIn[worker, task, interval] =
                              cpModel.NewConstant(0, $&quot;allVariablesTheAINeedsToFillIn[{worker},{task},{interval}]&quot;);
                      }
  
                      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) &lt;= 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&lt;int, Constraint[]&gt; constraintsMap, CpModel model,
          IntVar[] taskIntervals)
      {
          for (var i = 0; i &lt; 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) =&gt; new { si, i }).Where(_ =&gt;
                      _.si.ScheduleItemId == current.ScheduleItemId &amp;&amp; _.si.ServiceItemActivityId == c.To);
                  foreach (var otherSi in related)
                  {
                      switch (c.WaitingForType)
                      {
                          case 0:
                              model.Add(taskIntervals[i] &gt;= taskIntervals[otherSi.i] + c.Value);
                              break;
                          case 1:
                              model.Add(taskIntervals[i] == taskIntervals[otherSi.i] + c.Value);
                              break;
                          case 2:
                              model.Add(taskIntervals[i] &lt;= taskIntervals[otherSi.i] + c.Value);
                              break;
                      }
                  }
              }
          }
      }
  
      static void ModelWaitingForConstraintsOptimized(ScheduleItem[] scheduleItems, Dictionary&lt;int, Constraint[]&gt; constraintsMap, CpModel model, Horizon horizon, int[] indexedDistinctWorkers, IntVar[] flattenedAllVariablesTheAINeedsToFillIn)
      {
          for (var scheduleItemIndex = 0; scheduleItemIndex &lt; 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) =&gt; new { si, i }).Where(_ =&gt;
                        _.si.ScheduleItemId == current.ScheduleItemId &amp;&amp; _.si.ServiceItemActivityId == c.To).ToList();
                  for (var horizonDayIndex = 0; horizonDayIndex &lt; horizon.Value.Length; horizonDayIndex++)
                  {
                      for (var workerIndex = 0; workerIndex &lt; 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 &lt; 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 &gt; 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 &lt; 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) =&gt; new { si, i })
                       .GroupBy(_ =&gt; new { _.si.ScheduleItemId, _.si.ServiceItemActivityId }).Where(_ =&gt; _.Count() &gt; 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, &quot;taskInterval&quot;);
              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
  }
  </code></pre>