Блог

Моя команда создает решатель CP-SAT, который планирует задания (например, домашнее задание) в течение нескольких дней с переменной доступностью (время, доступное для выполнения заданий). Мы пытаемся ускорить нашу модель.

Мы пробовали num_search_workers и другие настройки параметров, но хотим проверить, не увеличивается ли скорость. Цель состоит в том, чтобы решить проблемы с ~100 днями и до 2000 заданиями за 5-10 секунд (сравнительный анализ на M1 mac). Есть какие-нибудь идеи?

Описание проблемы: Разместите задания через d дней, соблюдая эти требования

• Время выполнения задания в день не должно превышать доступное время этого дня
• Зависимости назначения должны соблюдаться (если A нуждается в B, то B не должно возникать после A)
• Задания могут быть разделены (чтобы лучше распределяться по дням с небольшим количеством времени).
• Оптимизируйте для разнообразия типов заданий в один день

Решение резко замедляется с # днями и # заданиями. Это ожидается, но мы хотели бы знать, можете ли вы предложить возможные ускорения

Вот пример модульного теста. Надеюсь, это показывает разделение, упорядочение и временные ограничения.

 days = [{"secondsAvailable": 1200}, {"secondsAvailable": 1200}, {"secondsAvailable": 1200}, {"secondsAvailable": 1200}] assignments = [  {"id": 1, "resourceType": "Type0", "seconds": 2400, "deps": [], "instances": 2},  {"id": 2, "resourceType": "Type0", "seconds": 1200, "deps": [1], "instances": 1},  {"id": 3, "resourceType": "Type0", "seconds": 1200, "deps": [1, 2], "instances": 1},  ] result = cp_sat.CP_SAT_FAST.schedule(days, assignments, options=solver_options) # expect a list of lists where each inner list is a day with the included assignments expected = shared.SolverOutput(feasible=True, solution=[  [{"id": 1, "resourceType": "Type0", "time": 1200, "instances": 2}],  [{"id": 1, "resourceType": "Type0", "time": 1200, "instances": 2}],  [{"id": 2, "resourceType": "Type0", "time": 1200, "instances": 1}],  [{"id": 3, "resourceType": "Type0", "time": 1200, "instances": 1}],  ]) self.assertEqual(result, expected)  

И вот решатель:

 import math from typing import List, Dict  from ortools.sat.python import cp_model import numpy as np  import planner.solvers as solvers from planner.shared import SolverOutput, SolverOptions   class CP_SAT_FAST(solvers.Solver):  """  CP_SAT_FAST is a CP_SAT solver with speed optimizations and a time limit (passed in through options).  """   @staticmethod  def schedule(days: List[Dict], assignments: List[Dict], options: SolverOptions) -gt; SolverOutput:  """  Schedules a list of assignments on a studyplan of days   Arguments:  days: list of dicts containing available time for that day  assignments: list of assignments to place on schedule  """   model = cp_model.CpModel()   num_assignments = len(assignments)  num_days = len(days)   # x[d, a] shows is assignment a is on day d  x = np.zeros((num_days, num_assignments), cp_model.IntVar)    # used for resource diversity optimization  total_resource_types = 4  unique_today = []   # upper and lower bounds used for dependency ordering (if a needs b then b must be before or on the day of a)  day_ub = {}  day_lb = {}   # track assignment splitting  instances = {}  assignment_times = {}   id_to_assignment = {}  for a, asm in enumerate(assignments):   # track upper and lower bounds  day_ub[a] = model.NewIntVar(0, num_days, "day_ub")  day_lb[a] = model.NewIntVar(0, num_days, "day_lb")  asm["ub"] = day_ub[a]  asm["lb"] = day_lb[a]  id_to_assignment[asm["id"]] = asm   max_instances = min(num_days, asm.get("instances", num_days))    # each assignment must occur at least once  instances[a] = model.NewIntVar(1, max_instances, f"instances_{a}")  model.AddHint(instances[a], max_instances)   # when split keep a decision variable of assignment time  assignment_times[a] = model.NewIntVar(asm.get("seconds") // max_instances, asm.get("seconds"), f"assignment_time_{a}")  model.AddDivisionEquality(assignment_times[a], asm.get("seconds"), instances[a])    for d in range(num_days):   time_available = days[d].get("secondsAvailable", 0)  if time_available lt;= 0:  # no assignments on zero-time days  model.Add(sum(x[d]) == 0)   else:    # track resource diversity on this day  type0_today = model.NewBoolVar(f"type0_on_{d}")  type1_today = model.NewBoolVar(f"type1_on_{d}")  type2_today = model.NewBoolVar(f"type2_on_{d}")  type3_today = model.NewBoolVar(f"type3_on_{d}")  types_today = model.NewIntVar(0, total_resource_types, f"unique_on_{d}")    task_times = []   for a, asm in enumerate(assignments):   # x[d, a] = True if assignment a is on day d  x[d, a] = model.NewBoolVar(f"x[{d},{a}]")    # set assignment upper and lower bounds for ordering  model.Add(day_ub[a] gt;= d).OnlyEnforceIf(x[d, a])  model.Add(day_lb[a] gt;= (num_days - d)).OnlyEnforceIf(x[d, a])    # track if a resource type is on a day for resource diversity optimization  resourceType = asm.get("resourceType")  if resourceType == "Type0":  model.AddImplication(x[d, a], type0_today)  elif resourceType == "Type1":  model.AddImplication(x[d, a], type1_today)  elif resourceType == "Type2":  model.AddImplication(x[d, a], type2_today)  elif resourceType == "Type3":  model.AddImplication(x[d, a], type3_today)  else:  raise RuntimeError(f"Unknown resource type {asm.get('resourceType')}")   # track of task time (considering splitting), for workload requirements  task_times.append(model.NewIntVar(0, asm.get("seconds"), f"time_{a}_on_{d}"))  model.Add(task_times[a] == assignment_times[a]).OnlyEnforceIf(x[d, a])   # time assigned to day d cannot exceed the day's available time  model.Add(time_available gt;= sum(task_times))   # sum the unique resource types on this day for later optimization  model.Add(sum([type0_today, type1_today, type2_today, type3_today]) == types_today)  unique_today.append(types_today)    """  Resource Diversity:   Keeps track of what instances of a resource type appear on each day  and the minimum number of unique resource types on any day. (done above ^)    Then the model objective is set to maximize that minimum  """  total_diversity = model.NewIntVar(0, num_days * total_resource_types, "total_diversity")  model.Add(sum(unique_today) == total_diversity)   avg_diversity = model.NewIntVar(0, total_resource_types, "avg_diversity")  model.AddDivisionEquality(avg_diversity, total_diversity, num_days)   # Set objective  model.Maximize(avg_diversity)    # Assignment Occurance/Splitting and Dependencies  for a, asm in enumerate(assignments):    # track how many times an assignment occurs (since we can split)  model.Add(instances[a] == sum(x[d, a] for d in range(num_days)))    # Dependencies   for needed_asm in asm.get("deps", []):  needed_ub = id_to_assignment[needed_asm]["ub"]    # this asm's lower bound must be greater than or equal to the upper bound of the dependency  model.Add(num_days - asm["lb"] gt;= needed_ub)   # Solve  solver = cp_model.CpSolver()   # set time limit  solver.parameters.max_time_in_seconds = float(options.time_limit)  solver.parameters.preferred_variable_order = 1  solver.parameters.initial_polarity = 0  # solver.parameters.stop_after_first_solution = True  # solver.parameters.num_search_workers = 8   intermediate_printer = SolutionPrinter()  status = solver.Solve(model, intermediate_printer)    print("nStats")  print(f" - conflicts : {solver.NumConflicts()}")  print(f" - branches : {solver.NumBranches()}")  print(f" - wall time : {solver.WallTime()}s")  print()   if status == cp_model.OPTIMAL or status == cp_model.FEASIBLE:  sp = []   for i, d in enumerate(days):  day_time = 0  days_tasks = []  for a, asm in enumerate(assignments):  if solver.Value(x[i, a]) gt;= 1:  asm_time = math.ceil(asm.get("seconds") / solver.Value(instances[a]))  day_time  = asm_time   days_tasks.append({"id": asm["id"], "resourceType": asm.get("resourceType"), "time": asm_time, "instances": solver.Value(instances[a])})    sp.append(days_tasks)   return SolverOutput(feasible=True, solution=sp)    else:  return SolverOutput(feasible=False, solution=[])   class SolutionPrinter(cp_model.CpSolverSolutionCallback):   def __init__(self):  cp_model.CpSolverSolutionCallback.__init__(self)  self.__solution_count = 0   def on_solution_callback(self):  print(f"Solution {self.__solution_count} objective value = {self.ObjectiveValue()}")  self.__solution_count  = 1   

Прежде чем ответить на ваш фактический вопрос, я хочу указать на несколько вещей в вашей модели, которые, как я подозреваю, работают не так, как вы предполагали.

Ограничения на типы назначений, существующие в данный день

 model.AddImplication(x[d, a], type0_today)  

и т.д., Убедитесь в этом type0_today == 1 , если в этот день есть задание такого типа. Однако это не гарантирует, type0_today == 0 что в этот день не будет назначений такого типа. Решатель по-прежнему свободен в выборе type0_today == 1 , и он будет это делать, потому что это удовлетворяет этому ограничению, а также напрямую увеличивает целевую функцию. Вы, вероятно, обнаружите в оптимальном решении для данного вами тестового случая, что все type0_today type3_today переменные to равны 1 и что avg_diversity == 4 в оптимальном решении, даже если во входных данных нет назначений любого типа, кроме 0. На ранних стадиях моделирования всегда полезно проверить значения всех переменных в модели на предмет правдоподобия.

Поскольку у меня нет установки Python, я перевел вашу модель на c#, чтобы иметь возможность провести некоторые эксперименты. Извините, вам придется перевести на эквивалентный код Python. Я переформулировал ограничение на type0_today переменные, чтобы использовать массив type_today[d, t] (для дня d и типа t ) и использовать AddMaxEquality ограничение, которое для булевых переменных эквивалентно логическому ИЛИ всех участвующих переменных:

 // For each day...  for (int d = 0; d lt; num_days; d  )  {  // ... make a list for each assignment type of all x[d, a] where a has that type.  Listlt;IntVargt;[] assignmentsByType = new Listlt;IntVargt;[total_resource_types];  for (int t = 0; t lt; total_resource_types; t  )  {  assignmentsByType[t] = new Listlt;IntVargt;();  }  for (int a = 0; a lt; num_assignments; a  )  {  int t = getType(assignments[a].resourceType);  assignmentsByType[t].Add(x[d, a]);  }  // Constrain the types present on the day to be the logical OR of assignments with that type on that day  for (int t = 0; t lt; total_resource_types; t  )  {  if (assignmentsByType[t].Count gt; 0)  {  model.AddMaxEquality(type_today[d, t], assignmentsByType[t]);   }  else  {  model.Add(type_today[d, t] == 0);  }   }  }  

You compute the average diversity as

 avg_diversity = model.NewIntVar(0, total_resource_types, "avg_diversity")  model.AddDivisionEquality(avg_diversity, total_diversity, num_days)  

Since the solver only works with integer variables, avg_diversity will be exactly one of the values 0, 1, 2, 3 or 4 with no fractional part. The constraint AddDivisionEquality will also ensure that total_diversity is an exact integer multiple of both avg_diversity and num_days . This is a very strong restriction on the solutions and will lead to infeasibility in many cases that I don’t think you intended.

For example, avg_diversity == 3 , num_days == 20 and total_diversity == 60 would be an allowed solution, but total_diversity == 63 would not be allowed, although there are three days in that solution with higher diversity than in the one with total_diversity == 60 .

Instead, I recommend that you eliminate the variable avg_diversity and its constraint and simply use total_diversity as your objective function. Since the number of days is a fixed constant during the solution, maximizing the total diversity will be equivalent without introducing artificial infeasibilities.

That said, here is my answer.

Generic constraint satisfaction problems are in general NP problems and should not be expected to scale well. Although many specific problem formulations can actually be solved quickly, small changes in the input data or the formulation can push the problem into a black hole of exponentiality. There is really no other approach than trying out various methods to see what works best with your exact problem.

Хотя это звучит парадоксально, решателю легче найти оптимальные решения для сильно ограниченных задач, чем для слегка ограниченных (при условии, что они выполнимы!). Пространство поиска в сильно ограниченной задаче меньше, чем в слабо ограниченной, поэтому у решателя меньше вариантов, с чем экспериментировать для оптимизации, и поэтому он быстрее выполняет работу.

Первое предложение

В вашей задаче у вас есть переменные day_ub и day_lb для каждого задания. Они имеют диапазон от 0 до num_days . Ограничения, накладываемые на них

 model.Add(day_ub[a] gt;= d).OnlyEnforceIf(x[d, a])  model.Add(day_lb[a] gt;= (num_days - d)).OnlyEnforceIf(x[d, a])  

позвольте решателю свободно выбирать любое значение от 0 до наибольшего d значения соответственно. самый большой (num_days - d) (включительно). Во время оптимизации решатель, вероятно, тратит время на опробование различных значений для этих переменных, но редко обнаруживает, что это приводит к улучшению; это произойдет только тогда, когда будет изменено размещение зависимого назначения.

Вы можете исключить переменные day_ub day_lb и их ограничения и вместо этого сформулировать зависимости непосредственно с x переменными.

В моей модели c# я переформулировал ограничение зависимости назначения следующим образом:

 for (int a = 0; a lt; num_assignments; a  )  {  Assignment assignment = assignments[a];  foreach (int predecessorIndex in getPredecessorAssignmentIndicesFor(assignment))  {  for (int d1 = 0; d1 lt; num_days; d1  )  {  for (int d2 = 0; d2 lt; d1; d2  )  {  model.AddImplication(x[d1, predecessorIndex], x[d2, a].Not());  }  }  }  }  

Другими словами: если назначение B ( predecessorIndex ), от которого зависит назначение A ( a ), помещено в день d1 , то все x[0..d1, a] должно быть ложным. Это напрямую связывает зависимости с использованием x переменных вместо введения вспомогательных переменных с дополнительной свободой, которые мешают решателю. Это изменение уменьшает количество переменных в задаче и увеличивает количество ограничений, оба из которых помогают решателю.

В эксперименте, который я провел с 25 днями и 35 заданиями, проверка статистики модели показала

Оригинал:

 #Variables: 2020 #kIntDiv: 35 #kIntMax: 100 #kLinear1: 1750 #kLinear2: 914 #kLinearN: 86 Total constraints 2885  

Новая формулировка:

 #Variables: 1950 #kBoolOr: 11700 #kIntDiv: 35 #kIntMax: 100 #kLinear2: 875 #kLinearN: 86 Total constraints 12796  

Таким образом, новая формулировка имеет меньше переменных, но гораздо больше ограничений.

Время решения в эксперименте было улучшено, решателю потребовалось всего 2,6 с total_diversity == 68 вместо более чем 90 с.

Оригинальная рецептура

 Time Objective 0,21 56 0,53 59 0,6 60 0,73 61 0,75 62 0,77 63 2,9 64 3,82 65 3,84 66 91,01 67 91,03 68 91,05 69  

Новая формулировка

 Time Objective 0,2347 41 0,3066 42 0,4252 43 0,4602 44 0,5014 49 0,6437 50 0,6777 51 0,6948 52 0,7108 53 0,9593 54 1,0178 55 1,1535 56 1,2023 57 1,2351 58 1,2595 59 1,2874 60 1,3097 61 1,3325 62 1,388 63 1,5698 64 2,4948 65 2,5993 66 2,6198 67 2,6431 68 32,5665 69  

Of course, the solution times you get will be strongly dependent on the input data.

Second suggestion

During my experiments I observed that solutions are found much more quickly when the assignments have a lot of dependencies. This is consistent with more highly constrained models being easier to solve.

If you often have assignments of the same type and duration (like the numbers 2 and 3 in your test data) and they both have instance == 1` and either no dependencies or the same ones, then exchanging their position in the solution will not improve the objective.

In a pre-processing step you could look for such duplicates and make one of them dependent on the other. This is essentially a symmetry-breaking constraint. This will prevent the solver from wasting time with an attempt to see if exchanging their positions would improve the objective.

Third suggestion

The solution needs to deal with determining how many instances of each assignment will be present in a solution. That requires two variables for each assignment instances[a] and assignment_times[a] with an associated constraint.

Вместо этого вы могли бы избавиться от переменных instances[a] assignment_times[a] и вместо этого разделить назначения instances gt; 1 на несколько назначений на этапе предварительной обработки. Например, в ваших тестовых данных задание 1 будет разделено на два задания 1_1 и 1_2, каждое из которых имеет instances == 1 и seconds = 1200 . Для этого тестового случая, когда instances == 2 для задания 1 это не окажет никакого влияния на окончательное решение-возможно, решатель запланирует 1_1 и 1_2 в один и тот же день, возможно, нет, но конечный результат эквивалентен разделению или нет, но не нуждается в дополнительных переменных.

На этапе предварительной обработки, когда задание разделяется, вы должны добавить ограничения, нарушающие симметрию, чтобы сделать 1_2 зависимым от 1_1 и т. Д. По причинам, упомянутым выше.

Когда задание выполнено instances gt; 2 , разделение его на несколько назначений перед запуском фактически является изменением модели. Например, если instances == 3 и seconds = 2400 вы не можете получить решение, в котором задание разделено на два дня по 1200 с каждое; решатель всегда будет планировать 3 задания по 800 с каждое.

Таким образом, это предложение на самом деле является изменением модели, и вам придется определить, приемлемо это или нет.

Общему разнообразию, как правило, будет способствовать наличие большего количества экземпляров задания, поэтому изменение может не иметь больших практических последствий. Это также позволило бы запланировать 2/3 задания на один день, а оставшуюся 1/3-на другой день, так что это даже добавляет некоторую гибкость.

Но это может быть или не быть приемлемым с точки зрения ваших общих требований.

Во всех случаях вам придется протестировать изменения с вашими точными данными, чтобы увидеть, действительно ли они приводят к улучшению или нет.

Я надеюсь, что это поможет (и что это проблема реального мира, а не домашнее задание, как я потратил несколько часов на расследование…).