jumlah maksimum BoolVar sebelum or-tools tidak lagi layak untuk digunakan

Aug 18 2020

Masalah penjadwalan perawat standar yang digunakan sebagai contoh untuk OR-Tools (lihat misalnya https://developers.google.com/optimization/scheduling/employee_scheduling) mencoba untuk menetapkan nilai boolean ke variabel boolean di baris kode berikut:

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

Untuk masalah mainan ini, OR-Tools berfungsi dengan baik, tetapi hanya 105 variabel boolean yang dibuat (5 perawat, 7 hari, 3 shift $\Rightarrow 3\times 5\times7=105$ boolean untuk menetapkan apakah perawat tertentu bekerja pada shift tertentu).

Saya menjelajahi penggunaan OR-Tools untuk memecahkan masalah penjadwalan dunia nyata yang lebih realistis. Untuk masalah dunia nyata yang saya hadapi, giliran kerja ditugaskan setiap 15 menit dan ada lebih banyak pekerja dan lebih banyak peran yang terlibat. Pada akhirnya, saya mendapatkan 11.064 boolean untuk ditugaskan.

Apakah ini terlalu banyak untuk mengharapkan OR-Tools bekerja secara realistis? Saya menemukan bahwa itu dengan cepat menghasilkan jadwal (tidak terlalu baik) tetapi bahkan jika saya membiarkannya berjalan selama satu jam itu tidak membaik sama sekali pada jadwal awal yang muncul dalam beberapa detik pertama.

Apakah ini perilaku tipikal untuk OR-Tools? Ada pemikiran?

Jawaban

4 LaurentPerron Aug 18 2020 at 19:33

Tidak ada jawaban yang bagus untuk pertanyaan itu. Itu tergantung pada model, pada kompleksitas masalah. Reaksi saya adalah bahwa OR-Tools secara rutin memecahkan masalah yang lebih besar secara optimal, tetapi beberapa masalah yang jauh lebih kecil tidak mungkin dibuktikan, atau bahkan untuk menemukan solusi yang layak.

OR-Tools adalah pemecah CP yang baik (memenangkan semua 4 medali emas dari 2 tantangan minizinc terakhir). Ini juga merupakan pemecah MIP yang layak (menutup 5 instans MIPLIB terbuka 2017 dan meningkatkan batasan pada beberapa instans lainnya).

Saya akan menyarankan, atau ulangi saran di atas:

  • bandingkan dengan pemecah MIP komersial (Gurobi, Cplex, Xpress) dan coba keberuntungan Anda.
  • dibandingkan dengan CPLEX CP-Optimizer. Saya tidak berharap akan lebih baik setelah diskusi saya dengan peneliti akademis yang melakukan perbandingan, tetapi ini mungkin menjadi masalah ketika kinerja CPO luar biasa.
  • kirim model Anda ke milis pengguna or-tools dan mintalah bantuan atau komentar, khususnya seputar parameter pencarian.