การเพิ่มประสิทธิภาพแบบจํากัด หรือการจัดโปรแกรมแบบจำกัด (CP) คือชื่อที่ใช้ระบุวิธีแก้ปัญหาที่เป็นไปได้จากตัวเลือกจำนวนมาก ซึ่งสามารถจำลองปัญหาในรูปแบบของข้อจำกัดที่กำหนดเอง ปัญหา CP เกิดขึ้นในหลากหลายสาขาวิชาทางวิทยาศาสตร์และวิศวกรรม (คำว่า "การเขียนโปรแกรม" เป็นคำเรียกที่เรียกกันยากๆ คล้ายกับคำว่า "คอมพิวเตอร์" ครั้งหนึ่งที่แปลว่า "ผู้ที่คำนวณ" ในที่นี้ "การเขียนโปรแกรม" หมายถึงการจัดแผน ไม่ใช่การเขียนโปรแกรมในภาษาคอมพิวเตอร์)
CP อิงตามความเป็นไปได้ (ค้นหาโซลูชันที่เป็นไปได้) ไม่ใช่การเพิ่มประสิทธิภาพ (ค้นหาโซลูชันที่ดีที่สุด) และมุ่งเน้นที่ข้อจำกัดและตัวแปร ไม่ใช่ฟังก์ชันที่เป็นวัตถุประสงค์ อันที่จริง ปัญหา CP อาจไม่มีฟังก์ชันที่เป็นรูปธรรม เป้าหมายอาจเป็นการจํากัดชุดวิธีแก้ปัญหาขนาดใหญ่ที่เป็นไปได้ให้แคบลงให้กับชุดย่อยที่จัดการได้มากขึ้นโดยการเพิ่มข้อจํากัดลงในโจทย์
ตัวอย่างของปัญหาที่เหมาะสมกับ CP คือการกำหนดเวลาจ้างพนักงาน
ปัญหาเกิดขึ้นเมื่อบริษัทที่ดำเนินงานอย่างต่อเนื่อง เช่น โรงงาน ต้องสร้างตารางเวลารายสัปดาห์สำหรับพนักงาน ลองดูตัวอย่างที่เข้าใจง่ายมากๆ คือ บริษัทมีกะ 8 ชั่วโมง 3 กะต่อวัน และกำหนดพนักงาน 3 ใน 4 คนที่ลดกะวันละ 4 กะ และเลิกลา 4 วัน แม้จะเป็นในกรณีเล็กๆ แต่กำหนดการที่เป็นไปได้นั้นถือว่ามีมากมายมาก เพราะในแต่ละวันมีพนักงานมอบหมายได้ถึง 4! = 4 * 3 * 2 * 1 = 24 คน ดังนั้นจำนวนตารางเวลารายสัปดาห์ที่เป็นไปได้เท่ากับ 24/7 ซึ่งเท่ากับ 24/7
โดยปกติแล้วจะมีข้อจำกัดอื่นๆ ที่ทำให้จำนวนโซลูชันที่เป็นไปได้ลดลง เช่น พนักงานแต่ละคนต้องทำงานอย่างน้อยสัปดาห์ละวัน วิธี CP จะติดตามว่าโซลูชันใดที่ยังคงเป็นไปได้เมื่อคุณเพิ่มข้อจำกัดใหม่ ซึ่งทำให้เป็นเครื่องมือที่มีประสิทธิภาพสำหรับการแก้ปัญหาขนาดใหญ่และการกำหนดเวลาในสถานการณ์จริง
CP มีชุมชนที่กว้างขวางและกระตือรือร้นทั่วโลก โดยมีวารสารวิทยาศาสตร์โดยเฉพาะ การประชุม และคลังเทคนิคการแก้ไขปัญหาต่างๆ ได้นำ CP ไปใช้ในการวางแผน การกำหนดเวลา และโดเมนอื่นๆ อีกจำนวนมากที่มีข้อจำกัดที่แตกต่างกัน
เครื่องมือ
Google มีวิธีแก้ปัญหา CP ดังนี้
- เครื่องมือแก้โจทย์คณิต CP-SAT: โซลูชันการเขียนโปรแกรมแบบจํากัดที่ใช้เมธอด SAT (ความพอใจ)
- เครื่องมือแก้โจทย์คณิตเดิมของ CP: เครื่องมือแก้โจทย์ constraint Programming ที่ใช้ในไลบรารีการกำหนดเส้นทาง
หากคุณจำลองปัญหาได้โดยใช้วัตถุประสงค์เชิงเส้นและข้อจํากัดเชิงเส้น แสดงว่าคุณมีปัญหาการเขียนโปรแกรมเชิงเส้น และควรใช้ MPSolver (อย่างไรก็ตาม ปัญหาการกำหนดเส้นทางมักจะแก้ไขได้ดีที่สุดด้วยไลบรารีการกำหนดเส้นทางยานพาหนะของเรา แม้ว่าปัญหาเหล่านั้นจะแสดงด้วยโมเดลเชิงเส้นก็ตาม)
ตัวอย่าง
ส่วนถัดไปจะอธิบายถึงเครื่องมือแก้โจทย์ CP-SAT ซึ่งเป็นเครื่องมือแก้โจทย์ OR-เครื่องมือ หลักสำหรับการเขียนโปรแกรมข้อจำกัด (SAT ย่อมาจาก satifability: เครื่องมือแก้โจทย์คณิตใช้เทคนิคการแก้ไขปัญหา SAT ร่วมกับวิธีการ CP)
ตัวอย่างบางส่วนของปัญหาการตั้งเวลาที่เหมาะสำหรับเครื่องมือแก้โจทย์ CP-SAT มีดังนี้
โจทย์ CP แบบดั้งเดิม 2 ข้อ ได้แก่ โจทย์ N-queens และปริศนาคริปโตเคอเรนซี