or-tools 이전의 최대 BoolVar 수는 더 이상 사용할 수 없습니다.

Aug 18 2020

OR 도구의 예로 사용되는 표준 간호사 일정 문제 (예 : https://developers.google.com/optimization/scheduling/employee_scheduling)는 다음 코드 줄에서 부울 값을 부울 변수에 할당하려고합니다.

shifts[(n, d, s)] = model.NewBoolVar('shift_n%id%is%i' % (n, d, s))

이 장난감 문제의 경우 OR-Tools는 정상적으로 실행되지만 부울 변수는 105 개만 생성됩니다 (간호사 5 명, 7 일, 3 교대 $\Rightarrow 3\times 5\times7=105$ 주어진 간호사가 주어진 교대 근무를하는지 여부에 대해 할당 할 부울).

더 현실적인 실제 스케줄링 문제를 해결하기 위해 OR 도구를 사용하는 방법을 모색하고 있습니다. 제가 다루고있는 실제 문제의 경우, 교대 근무가 15 분 단위로 할당되고 더 많은 작업자와 더 많은 역할이 관련됩니다. 결국 11,064 개의 부울이 할당됩니다.

OR 도구가 현실적으로 작동하기를 기대하기에는 너무 많습니까? 나는 그것이 (그다지 좋지 않은) 일정을 신속하게 생성한다는 것을 알지만 한 시간 동안 실행해도 처음 몇 초 동안 만들어진 초기 일정에서 전혀 개선되지 않습니다.

OR-Tools의 일반적인 동작입니까? 이견있는 사람?

답변

4 LaurentPerron Aug 18 2020 at 19:33

그 질문에 대한 좋은 답이 없습니다. 모델, 문제의 복잡성에 따라 다릅니다. 내 직감 반응은 OR-Tools가 일상적으로 더 큰 문제를 최적으로 해결하지만 훨씬 더 작은 문제는 증명하거나 실행 가능한 솔루션을 찾는 것이 불가능할 수 있다는 것입니다.

OR-Tools는 좋은 CP 솔버입니다 (최근 2 개의 미니 아연 챌린지에서 4 개의 금메달을 모두 획득했습니다). 또한 괜찮은 MIP 솔버입니다 (5 개의 열린 MIPLIB 2017 인스턴스를 닫고 몇 가지 더 개선 된 경계).

위의 제안을 제안하거나 반복합니다.

  • 상용 MIP 솔버 (Gurobi, Cplex, Xpress)와 비교하여 운을 시험해보십시오.
  • CPLEX CP-Optimizer와 비교하십시오. 비교를 한 학계 연구자들과의 토론 후에는 더 나을 것이라고 기대하지 않지만 CPO가 훌륭하게 수행하면 문제가 될 수 있습니다.
  • or-tools 사용자 메일 링리스트에 모델을 보내고 특히 검색 매개 변수와 관련하여 도움이나 의견을 요청하십시오.