Skip to content
กลับไปยังผลการค้นหา

การโปรแกรมเชิงข้อจำกัด

ผู้เสนอ
Rossi, van Beek & Walsh
ปี
2006
ประเภท
Declarative combinatorial optimization
กลุ่มวิธี
Mathematical programming

ข้อความนี้เป็นการแปลด้วยเครื่องและยังไม่ได้รับการตรวจทาน อ่านต้นฉบับภาษาอังกฤษ

ขนาดตัวอักษร

ใช้ทำอะไร?

การโปรแกรมเชิงข้อจำกัด (Constraint Programming: CP) เป็นกระบวนทัศน์การหาค่าเหมาะที่สุดเชิงประกาศ (declarative optimization paradigm) ซึ่งปัญหาจะถูกกำหนดในรูปของชุดตัวแปร โดเมนจำกัด และข้อจำกัด และตัวแก้ปัญหาจะทำการค้นหาอย่างเป็นระบบเพื่อกำหนดค่าที่สอดคล้องกับข้อจำกัดทั้งหมด Rossi, van Beek, และ Walsh ได้วางกรอบแนวคิดของ CP ไว้อย่างครอบคลุมใน Handbook of Constraint Programming ปี 2006 โดย CP ได้รวมการตัดทอนพื้นที่ค้นหาด้วยการแพร่กระจาย (propagation-based pruning) เข้ากับการค้นหาแบบย้อนรอยอัจฉริยะ (intelligent backtracking search) เพื่อแก้ปัญหาเชิงการจัดหมู่ (combinatorial problems) ในด้านการจัดตารางเวลา การวางแผน และการกำหนดค่า

แนวคิดเบื้องหลังวิธีการ

ลองนึกภาพ CP เหมือนกับการต่อจิ๊กซอว์ที่ซับซ้อน: แต่ละช่องคือตัวแปรที่มีชุดของค่าที่ถูกต้อง และทุกกฎของจิ๊กซอว์คือข้อจำกัด แทนที่จะเดาสุ่ม CP ใช้กฎเพื่อกำจัดค่าที่เป็นไปไม่ได้ออกจากช่องข้างเคียงทันทีเมื่อมีการเติมค่าในช่องใดช่องหนึ่ง การแพร่กระจายนี้ช่วยลดพื้นที่การค้นหาลงอย่างมาก ทำให้ตัวแก้ปัญหาสำรวจเฉพาะชุดค่าผสมที่เป็นไปได้เท่านั้น โดยจะย้อนรอยและแก้ไขเมื่อพบทางตัน

ประวัติศาสตร์

การโปรแกรมเชิงข้อจำกัดเกิดขึ้นจากการวิจัยปัญญาประดิษฐ์ในช่วงทศวรรษ 1970 โดยมีงานเริ่มต้นเกี่ยวกับการสอดคล้องข้อจำกัดโดย Montanari และ Mackworth พัฒนาขึ้นในช่วงทศวรรษ 1980 และ 1990 ด้วยการพัฒนาอัลกอริทึม arc consistency ข้อจำกัดทั่วโลก และตัวแก้ปัญหาเชิงปฏิบัติ เช่น CHIP และ ILOG Solver สาขาวิชานี้ได้รับการรวบรวมอย่างเป็นทางการโดย Rossi, van Beek, และ Walsh ใน Handbook of Constraint Programming ปี 2006 ซึ่งยังคงเป็นเอกสารอ้างอิงที่ชัดเจน ครอบคลุมทฤษฎี อัลกอริทึม และการประยุกต์ใช้ในการหาค่าเหมาะที่สุดเชิงการจัดหมู่

ควรใช้เมื่อใด

การโปรแกรมเชิงข้อจำกัดเหมาะสมที่สุดสำหรับปัญหาเชิงการจัดหมู่ที่มีข้อจำกัดที่ซับซ้อนและหลากหลาย เช่น การจัดตารางเวลา การจัดตารางเรียน การกำหนดค่า และการกำหนดเส้นทาง ซึ่งความเป็นไปได้มีความสำคัญพอๆ กับความเป็นค่าเหมาะที่สุด โดยสมมติว่าปัญหาสามารถจำลองได้ด้วยโดเมนตัวแปรแบบไม่ต่อเนื่องหรือนับได้ CP มีประสิทธิภาพน้อยกว่าสำหรับการหาค่าเหมาะที่สุดแบบต่อเนื่อง หรือโปรแกรมเชิงเส้นขนาดใหญ่ ซึ่งตัวแก้ปัญหาการโปรแกรมเชิงเส้น (Linear Programming) หรือการโปรแกรมเชิงจำนวนเต็มผสม (Mixed-Integer Programming) มักจะเหนือกว่า เมื่อข้อจำกัดมีโครงสร้างสูงและการแพร่กระจายสามารถตัดทอนพื้นที่การค้นหาส่วนใหญ่ได้ CP จะมีประสิทธิภาพเหนือกว่าเมตาฮิวริสติกส์ทั่วไป

ข้อจำกัดและข้อควรพิจารณา

  • ความสามารถในการปรับขนาด: การค้นหาแบบเอ็กซ์โพเนนเชียลในกรณีที่เลวร้ายที่สุดทำให้ CP ช้าในกรณีขนาดใหญ่มากที่มีการแพร่กระจายที่อ่อนแอ
  • ต้องมีการสร้างแบบจำลองที่ดี: ฮิวริสติกส์การจัดลำดับตัวแปร/ค่าที่ไม่ดี หรือข้อจำกัดทั่วโลกที่ขาดหายไป นำไปสู่ต้นไม้การค้นหาที่ใหญ่เกินความจำเป็น
  • โดเมนต่อเนื่อง: CP ได้รับการออกแบบมาสำหรับโดเมนที่ไม่ต่อเนื่องโดยกำเนิด ปัญหาต่อเนื่องต้องใช้ส่วนขยายเฉพาะทางหรือแนวทางแบบผสมผสาน
  • ความเชี่ยวชาญของตัวแก้ปัญหา: การใช้งานที่มีประสิทธิภาพต้องอาศัยความคุ้นเคยกับเทคนิคการสร้างแบบจำลองข้อจำกัดและไลบรารีข้อจำกัดทั่วโลกเฉพาะตัวแก้ปัญหา

เงื่อนไขจากแหล่งที่มาไม่สามารถใช้แทนการทบทวนทางวิทยาศาสตร์ที่เป็นอิสระหรือการตรวจสอบโดยเอนจินวิเคราะห์ได้

จุดแข็ง

  • การสร้างแบบจำลองเชิงประกาศ: กฎที่ซับซ้อนในโลกแห่งความเป็นจริงจะถูกแสดงออกโดยตรงเป็นข้อจำกัด โดยไม่ต้องระบุขั้นตอนการค้นหา
  • การตัดทอนที่มีประสิทธิภาพ: การแพร่กระจายข้อจำกัดช่วยกำจัดพื้นที่ที่ไม่สามารถทำได้ตั้งแต่เนิ่นๆ ซึ่งมักจะลดการค้นหาลงหลายเท่าตัว
  • จัดการกับข้อจำกัดที่หลากหลาย: ข้อจำกัดเชิงตรรกะ, เลขคณิต, ทั่วโลก และที่ผู้ใช้กำหนด สามารถอยู่ร่วมกันได้อย่างเป็นธรรมชาติในแบบจำลองเดียว
  • รับประกันความสมบูรณ์: ตัวแก้ปัญหาจะพบคำตอบที่เหมาะสมที่สุดหรือพิสูจน์ความเป็นไปไม่ได้ ซึ่งแตกต่างจากวิธีการฮิวริสติกส์

การประยุกต์ใช้

  • การจัดตารางพนักงานและพยาบาล: การมอบหมายพนักงานเข้ากะโดยคำนึงถึงความพร้อม กฎหมายแรงงาน และข้อจำกัดด้านทักษะ
  • การจัดตารางเรียน: การสร้างตารางเรียนของมหาวิทยาลัยหรือโรงเรียนภายใต้ข้อจำกัดด้านความจุห้องเรียน ความพร้อมของอาจารย์ และหลักสูตร
  • การกำหนดค่า: การประกอบการกำหนดค่าผลิตภัณฑ์ (คอมพิวเตอร์ ยานพาหนะ) จากแคตตาล็อกส่วนประกอบภายใต้ข้อจำกัดด้านความเข้ากันได้และทรัพยากร
  • การกำหนดเส้นทางยานพาหนะและโลจิสติกส์: การวางแผนเส้นทางการจัดส่งภายใต้ข้อจำกัดด้านช่วงเวลา ความจุยานพาหนะ และกฎระเบียบของคนขับ
  • การประมูลเชิงการจัดหมู่และการจัดสรรทรัพยากร: การจัดสรรทรัพยากรให้กับผู้ประมูลหรืองานภายใต้ข้อจำกัดด้านการผูกขาดและงบประมาณ

วิธีการทำงาน

วิธีการทำงาน

1

ปัญหาจะถูกเข้ารหัสเป็นชุดสามของปัญหาการสอดคล้องข้อจำกัด (Constraint Satisfaction Problem) ซึ่งประกอบด้วยตัวแปร X โดเมนจำกัด D และชุดของข้อจำกัด C ตัวแปร x_i แต่ละตัวสามารถกำหนดค่าใดก็ได้จากโดเมน D_i ข้อจำกัดจะกำหนดชุดค่าผสมที่อนุญาตของค่าต่างๆ ในกลุ่มย่อยของตัวแปร โดยแปลกฎในโลกแห่งความเป็นจริง เช่น ข้อจำกัดด้านความจุ ความสัมพันธ์เชิงลำดับ ความขัดแย้งของทรัพยากร ให้เป็นโครงสร้างทางคณิตศาสตร์ที่ตัวแก้ปัญหาสามารถใช้เหตุผลได้

สูตร
\text{CSP} = \langle X, D, C \rangle \quad X = \{x_1, x_2, \ldots, x_n\},\; D = \{D_1, D_2, \ldots, D_n\}
2

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

สูตร
\text{AC}(x_i, x_j): \forall a \in D_i,\; \exists b \in D_j \text{ s.t. } c_{ij}(a, b) \text{ holds}
3

ตัวแก้ปัญหาจะเลือกตัวแปรที่ยังไม่ได้กำหนดค่า ซึ่งโดยทั่วไปจะใช้ฮิวริสติกส์ เช่น ค่าที่เหลือต่ำสุด (minimum remaining values) หรือดีกรี (degree) และกำหนดค่าชั่วคราวจากโดเมนที่ถูกตัดทอน การแพร่กระจายจะทำงานอีกครั้ง หากตรวจพบความขัดแย้ง (โดเมนว่างเปล่า) ตัวแก้ปัญหาจะย้อนรอยไปยังจุดตัดสินใจล่าสุดและลองค่าอื่น การย้อนกลับแบบกระโดด (backjumping) และการบันทึกค่าที่ไม่ดี (nogood recording) สามารถช่วยเร่งการกู้คืนจากความล้มเหลวได้อีก

สูตร
x_i \leftarrow a_i \in D_i,\quad \text{propagate},\quad \text{if fail: backtrack and reassign}
4

เมื่อตัวแปรทั้งหมดได้รับการกำหนดค่าที่สอดคล้องกับข้อจำกัดทุกข้อ การกำหนดค่าที่สมบูรณ์ S* จะถือเป็นคำตอบ สำหรับปัญหาการหาค่าเหมาะที่สุด ฟังก์ชันวัตถุประสงค์จะนำทางการค้นหาไปสู่คำตอบที่เป็นไปได้ที่ดีที่สุด และกลยุทธ์ branch-and-bound จะค่อยๆ กระชับขอบเขตเมื่อพบคำตอบที่ดีขึ้น จนกว่าจะได้รับการรับรองค่าเหมาะที่สุดทั่วโลก (global optimum) หรือถึงขีดจำกัดเวลา

สูตร
S^* = \{(x_1, a_1^*), \ldots, (x_n, a_n^*)\} : \forall c \in C,\; c(a_1^*, \ldots, a_n^*) = \text{true}

ข้อผิดพลาดที่พบบ่อย

  • การกำหนดข้อจำกัดมากเกินไปในแบบจำลองด้วยข้อจำกัดที่ซ้ำซ้อนหรือขัดแย้งกัน ทำให้ตัวแก้ปัญหารายงานความเป็นไปไม่ได้อย่างไม่ถูกต้อง
  • การละเลยข้อจำกัดทั่วโลก (เช่น alldifferent, cumulative) ทำให้พลาดโอกาสในการแพร่กระจายที่อัลกอริทึมเฉพาะทางจัดหาให้โดยไม่เสียค่าใช้จ่าย
  • การละเลยฮิวริสติกส์การค้นหาและการพึ่งพาการจัดลำดับตัวแปร/ค่าเริ่มต้น อาจทำให้เสียเวลาแบบเอ็กซ์โพเนนเชียลไปกับการจัดลำดับที่ผิดปกติ
  • การสับสนระหว่างการสอดคล้องข้อจำกัดกับการหาค่าเหมาะที่สุด: การลืมเพิ่มฟังก์ชันวัตถุประสงค์และการกระชับขอบเขตจะให้เพียงคำตอบที่เป็นไปได้แรกเท่านั้น ไม่ใช่คำตอบที่ดีที่สุด

คำถามที่พบบ่อย

การโปรแกรมเชิงข้อจำกัดแตกต่างจากการโปรแกรมเชิงเส้นจำนวนเต็มอย่างไร?

แม้ว่าทั้งสองจะแก้ปัญหาเชิงการจัดหมู่ได้ แต่ ILP กำหนดให้ข้อจำกัดและวัตถุประสงค์ทั้งหมดเป็นเชิงเส้น ซึ่งช่วยให้สามารถใช้ขอบเขตการผ่อนปรน LP ได้อย่างมีประสิทธิภาพ CP ไม่มีข้อกำหนดเชิงเส้นดังกล่าว และอาศัยการแพร่กระจายข้อจำกัดและการค้นหาอย่างเป็นระบบ CP จัดการกับข้อจำกัดเชิงตรรกะและทั่วโลกที่ซับซ้อนได้อย่างเป็นธรรมชาติมากกว่า ในขณะที่ ILP มักจะปรับขนาดได้ดีกว่าในปัญหาที่มีโครงสร้างเชิงเส้นที่แข็งแกร่งและจำนวนตัวแปรมาก

ข้อจำกัดทั่วโลกคืออะไร และทำไมจึงสำคัญ?

ข้อจำกัดทั่วโลกคือข้อจำกัดระดับสูงที่ครอบคลุมตัวแปรจำนวนมาก เช่น alldifferent (ตัวแปรทั้งหมดมีค่าที่แตกต่างกัน) หรือ cumulative (การใช้ทรัพยากร ณ เวลาใดๆ ไม่เกินความจุ) สิ่งเหล่านี้มีความสำคัญเนื่องจากตัวแก้ปัญหาใช้อัลกอริทึมการแพร่กระจายเฉพาะทางที่มีประสิทธิภาพสูงสำหรับแต่ละข้อจำกัด ซึ่งช่วยให้สามารถตัดทอนพื้นที่ค้นหาได้ดีกว่าการแยกเงื่อนไขเดียวกันออกเป็นข้อจำกัดไบนารีหลายข้อ ซึ่งจะทำให้พื้นที่การค้นหาส่วนใหญ่ยังไม่ถูกสำรวจ

การโปรแกรมเชิงข้อจำกัดสามารถหาคำตอบที่เหมาะสมที่สุดได้หรือไม่ หรือได้เพียงคำตอบที่เป็นไปได้เท่านั้น?

CP สามารถหาคำตอบที่เหมาะสมที่สุดได้โดยการรวมการค้นหาความเป็นไปได้เข้ากับฟังก์ชันวัตถุประสงค์ ตัวแก้ปัญหาใช้ branch-and-bound: เมื่อพบคำตอบที่เป็นไปได้แล้ว จะเพิ่มข้อจำกัดที่กำหนดให้คำตอบถัดไปต้องดีกว่าอย่างเคร่งครัด โดยดำเนินการต่อไปจนกว่าจะไม่มีการปรับปรุงใดๆ อีก ซึ่งเป็นการรับรองความเป็นค่าเหมาะที่สุด หากจำกัดเวลา คำตอบที่ดีที่สุดที่พบจนถึงปัจจุบันจะถูกส่งคืนเป็นค่าประมาณ

วิธีการที่เกี่ยวข้อง

แหล่งอ้างอิง

  1. Rossi, F., van Beek, P., & Walsh, T. (Eds.). (2006). Handbook of Constraint Programming. Elsevier.

    ISBN: 978-0-444-52726-4
    คัดลอกแล้ว