Есть ли способ установить дизъюнктивные ограничения с помощью Google OR Tools для python? - PullRequest
Новая
       28

Есть ли способ установить дизъюнктивные ограничения с помощью Google OR Tools для python?

2 голосов
/ 14 апреля 2019

Я пытаюсь построить целочисленную модель LP, используя Google OR для Python 3.7. И я не могу понять, как создать дизъюнктивные ограничения. Предположим, есть переменные {x1, x2, x3, x4, x5, ...}, и я хочу разделить несколько условий в одном: x1 + x2 = 2 | х2 + х3 = 2 | х3 + х4 = 2 Таким образом, для выполнения этого условия достаточно x2 + x3 = 2.

Как я понял, это возможно и называется дизъюнктивными условиями. Для OR Tools я нашел некоторое объяснение , но это для C ++ и выглядит устаревшим. Есть также учебник от Google , но он предназначен для CP, а не для задачи LP, поэтому я не знаю, как использовать его в моем случае (у меня нет модели, только решатель)

Моя задача - определить время обеда (скажем, 2 часа) во время рабочей смены с минимальным перекрытием. Для переменной 0 обозначает обед и 1 за рабочее время. Итак, вот несколько упрощенная версия того, что я получил сейчас: 

...
solver = pywraplp.Solver('SolveIntegerProblem', pywraplp.Solver.CBC_MIXED_INTEGER_PROGRAMMING)
objective = solver.Objective()

for e in employees:
  for d in days:
    # setting up a constraint that during workday employee should have a dinner time for 2 hours
    dinner_constraint = solver.Constraint(-solver.infinity(), e.end_hour - e.start_hour - 1) # force to spend at least 2 hours for dinner
    for h in range(e.start_hour, e.end_hour):
      variables[(e, d, h)] = solver.IntVar(0.0, 1.0, 'mhr_{}_{}_{}'.format(e, d, h))
      objective.SetCoefficient(variables[(e, d, h)], 1)
      dinner_constraint.SetCoefficient(variables[(e, d, h)], 1)
    for h in range(e.start_hour, e.end_hour - 1): # e.end_hour - 1 due to dinner is 2 hours
      dinner_sub_constraint = solver.Constraint(2)
      dinner_sub_constraint.SetCoefficient(variables[(e, d, h)], 1)
      dinner_sub_constraint.SetCoefficient(variables[(e, d, h + 1)], 1)
      # here I want to disjunct dinner_sub_constraint for each iteration in one constraint
objective.SetMaximization()
result_status = solver.Solve()
...

Итак, я просто хочу разделить все атрибуты dinner_sub_constraint и установить его в качестве одного ограничения.

Это может быть изнурительный подход, но я понятия не имею, как обеспечить два часа подряд обедом, поэтому недопустимо два обеда по 1 часу в течение одной смены. Есть ли способ разграничить условия? Или мой подход неверен? Или я должен использовать другую библиотеку?

1 Ответ

4 голосов
/ 15 апреля 2019

Вы должны использовать решатель CP-SAT. Ищите shift_scheduling_sat.py в examples / python.

...