จำนวนสูงสุดของ BoolVar ก่อนหน้าหรือเครื่องมือไม่สามารถใช้งานได้อีกต่อไป

Aug 18 2020

ปัญหาการจัดตารางเวลาพยาบาลมาตรฐานซึ่งใช้เป็นตัวอย่างสำหรับ OR-Tools (ดูตัวอย่าง 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-Tools เพื่อแก้ปัญหาการตั้งเวลาในโลกแห่งความเป็นจริงที่สมจริงยิ่งขึ้น สำหรับปัญหาในโลกแห่งความเป็นจริงที่ฉันกำลังเผชิญอยู่มีการกำหนดกะโดยเพิ่มทีละ 15 นาทีและมีคนงานมากขึ้นและมีบทบาทที่เกี่ยวข้องมากขึ้น ในท้ายที่สุดฉันจะได้รับการกำหนดบูลีน 11,064 รายการ

มีมากเกินไปที่จะคาดหวังว่า OR-Tools จะทำงานได้อย่างสมจริงหรือไม่? ฉันพบว่ามันสร้างตารางเวลา (ไม่ดีมาก) อย่างรวดเร็ว แต่ถึงแม้ว่าฉันจะปล่อยให้มันทำงานเป็นเวลาหนึ่งชั่วโมงมันก็ไม่ดีขึ้นเลยตามกำหนดการเริ่มต้นที่เกิดขึ้นในสองสามวินาทีแรก

นี่เป็นพฤติกรรมทั่วไปสำหรับ OR-Tools หรือไม่? ความคิดใด ๆ ?

คำตอบ

4 LaurentPerron Aug 18 2020 at 19:33

ไม่มีคำตอบที่ดีสำหรับคำถามนั้น ขึ้นอยู่กับรุ่นขึ้นอยู่กับความซับซ้อนของปัญหา ปฏิกิริยาทางเดินอาหารของฉันคือ OR-Tools มักจะแก้ปัญหาที่ใหญ่กว่าในการเพิ่มประสิทธิภาพเป็นประจำ แต่ปัญหาเล็ก ๆ บางอย่างไม่สามารถพิสูจน์ได้หรือแม้แต่หาวิธีแก้ปัญหาที่เป็นไปได้

OR-Tools เป็นตัวแก้ CP ที่ดี (ได้รับรางวัลทั้งหมด 4 เหรียญทองจาก 2 minizinc ชาเลนจ์ล่าสุด) นอกจากนี้ยังเป็นตัวแก้ MIP ที่ดี (มันปิด 5 อินสแตนซ์ MIPLIB 2017 ที่เปิดอยู่และปรับปรุงขอบเขตในอีกสองสามรายการ)