Branch and bound — วิธีแบ่งและกำหนดขอบเขต

วิธีแบ่งและกำหนดขอบเขต (อังกฤษ: Branch and Bound ย่อว่า B&B หรือ BnB) คือกระบวนทัศน์ทั่วไปสำหรับการสร้างอัลกอริทึมแม่นยำในการแก้ปัญหาการหาค่าเหมาะสมแบบไม่ต่อเนื่องและแบบผสม โดยเฉพาะปัญหาที่เป็น NP-hard วิธีนี้เป็นกลยุทธ์การค้นหาแบบมีทิศทาง ซึ่งแบ่งเซตของคำตอบที่ยอมรับได้ทั้งหมดออกเป็นเซตย่อยอย่างต่อเนื่อง (การแตกกิ่ง) และสำหรับแต่ละเซตย่อยจะคำนวณค่าประมาณ (ขอบเขต) ของฟังก์ชันวัตถุประสงค์ ค่าประมาณเหล่านี้ช่วยให้ตัดทิ้งเซตย่อยที่ไม่มีทางมีคำตอบที่เหมาะสมอยู่แน่นอน ซึ่งช่วยลดขนาดของพื้นที่การค้นหาได้อย่างมีนัยสำคัญ

วิธีนี้ถูกเสนอครั้งแรกโดย A. Land และ A. Doig ในปี ค.ศ. 1960 เพื่อแก้ปัญหาการโปรแกรมเชิงเส้นแบบจำนวนเต็ม นับแต่นั้นมา วิธีนี้ได้กลายเป็นหนึ่งในแนวทางพื้นฐานที่สำคัญที่สุดในการวิจัยเชิงปฏิบัติการและวิทยาการคอมพิวเตอร์ คุณลักษณะสำคัญของวิธีนี้คือความยืดหยุ่น เนื่องจากมันไม่ใช่อัลกอริทึมเฉพาะเจาะจง แต่เป็นกรอบกลยุทธ์ระดับสูง (framework) ที่ปรับให้เข้ากับโครงสร้างของปัญหาที่ต้องการแก้ได้

ส่วนประกอบหลักของวิธี

พื้นฐานของวิธีนี้ประกอบด้วยการดำเนินการพื้นฐานสามอย่างที่ใช้กับเซตย่อยของพื้นที่คำตอบซึ่งจัดระเบียบในรูปแบบของต้นไม้การค้นหา

• การแตกกิ่ง (อังกฤษ: Branching) คือกระบวนการแบ่งเซตของคำตอบที่ยอมรับได้ในปัจจุบัน $S_i$ ออกเป็นเซตย่อยที่เล็กกว่าหลายเซต ซึ่งโดยทั่วไปจะไม่ทับซ้อนกัน $S_{i1},S_{i2},\dots ,S_{ik}$ แบบเวียนซ้ำ เซตย่อยแต่ละเซตสอดคล้องกับปัญหาย่อยใหม่และแสดงเป็นโหนดลูกในต้นไม้การค้นหา ตัวอย่างเช่น ในปัญหาการโปรแกรมเชิงเส้นแบบจำนวนเต็ม การแตกกิ่งมักทำบนตัวแปรที่มีค่าเป็นเศษส่วนในคำตอบของ LP-relaxation

• การกำหนดขอบเขต (อังกฤษ: Bounding) — สำหรับแต่ละโหนดในต้นไม้การค้นหา (กล่าวคือสำหรับแต่ละปัญหาย่อย) จะมีการคำนวณค่าประมาณของฟังก์ชันวัตถุประสงค์ สำหรับปัญหาการหาค่าต่ำสุด ค่านี้คือขอบเขตล่าง (lower bound) ซึ่งเป็นการประมาณที่รับประกันจากด้านล่างสำหรับคำตอบใด ๆ ในเซตย่อยนั้น โดยส่วนใหญ่ค่าประมาณนี้ได้มาจากการแก้ relaxation ของปัญหาย่อยต้นฉบับ ซึ่งเป็นเวอร์ชันที่ง่ายกว่าโดยละเว้นข้อจำกัดบางส่วนชั่วคราว (เช่น ข้อจำกัดความเป็นจำนวนเต็ม) ที่พบบ่อยที่สุดคือ LP-relaxation

• การตัดทิ้ง (อังกฤษ: Pruning) คือกระบวนการคัดออกโหนด (และต้นไม้ย่อยทั้งหมดที่สอดคล้องกัน) ที่ไม่มีทางมีคำตอบที่เหมาะสมอยู่ โดยโหนดจะถูกตัดทิ้งในกรณีใดกรณีหนึ่งดังต่อไปนี้:

1. การตัดทิ้งตามขอบเขต: ขอบเขตล่างของโหนดนั้นไม่ดีกว่า (กล่าวคือมากกว่าหรือเท่ากับสำหรับปัญหาการหาค่าต่ำสุด) ค่าของคำตอบที่ดีที่สุดที่พบในขณะนั้น ซึ่งเรียกว่าค่าบันทึก (incumbent)
2. การตัดทิ้งตามความยอมรับได้: คำตอบของ relaxation ของโหนดนั้นยอมรับได้สำหรับปัญหาต้นฉบับ (เช่น ตัวแปรทั้งหมดเป็นจำนวนเต็ม) คำตอบนี้จะถูกเปรียบเทียบกับค่าบันทึกปัจจุบัน และหากดีกว่าก็จะอัปเดตค่าบันทึก ไม่จำเป็นต้องแตกกิ่งจากโหนดนี้อีกต่อไป
3. การตัดทิ้งตามการไม่มีคำตอบ: ปัญหาย่อยที่สอดคล้องกับโหนดนั้นไม่มีคำตอบที่ยอมรับได้

อัลกอริทึมทั่วไป

อัลกอริทึมทั่วไปของวิธีแบ่งและกำหนดขอบเขตสำหรับปัญหาการหาค่าต่ำสุดสามารถอธิบายได้ด้วยขั้นตอนดังต่อไปนี้:

1. การเริ่มต้น: หาคำตอบที่ยอมรับได้เริ่มต้น (เช่น โดยใช้ heuristic) และกำหนดค่าของมันเป็นขอบเขตบนเริ่มต้น (ค่าบันทึก) $U$ สร้างคิวของโหนดที่ยังดำเนินการอยู่ $Q$ ซึ่งบรรจุโหนดราก (ปัญหาต้นฉบับ)
2. วงวนหลัก: ตราบใดที่คิว $Q$ ไม่ว่างเปล่า:
   • เลือกโหนดจาก $Q$ ตามกลยุทธ์การค้นหา (เช่น การค้นหาเชิงลึกหรือตามค่าประมาณที่ดีที่สุด)
   • แก้ relaxation สำหรับโหนดนั้น โดยได้ขอบเขตล่าง $L$
   • ตัดทิ้งโหนด หาก $L\ge U$
   • หากคำตอบของ relaxation ยอมรับได้สำหรับปัญหาต้นฉบับ ให้อัปเดตค่าบันทึก: $U\leftarrow L$
   • หากโหนดไม่ถูกตัดทิ้งและคำตอบไม่ยอมรับได้ ให้ดำเนินการแตกกิ่ง โดยแบ่งออกเป็นโหนดลูกและเพิ่มเข้าไปในคิว $Q$
3. การสิ้นสุด: เมื่อคิว $Q$ ว่างเปล่า อัลกอริทึมจะสิ้นสุด คำตอบที่พบซึ่งสอดคล้องกับค่าบันทึก $U$ คือคำตอบที่เหมาะสมที่สุดในระดับโลก

คุณสมบัติและทฤษฎีบทสำคัญ

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

ตัวอย่าง

• ปัญหาการโปรแกรมเชิงเส้นแบบจำนวนเต็ม: การประยุกต์ใช้คลาสสิกของวิธีนี้ โดยใช้การโปรแกรมเชิงเส้นเป็น relaxation การแตกกิ่งเกิดขึ้นบนตัวแปรที่มีค่าเป็นเศษส่วน $x_j$ โดยสร้างปัญหาย่อยสองปัญหาที่มีข้อจำกัดเพิ่มเติม $x_j\le \lfloor x_j^{\ast }\rfloor$ และ $x_j\ge \lceil x_j^{\ast }\rceil$
• ปัญหาพนักงานขายเดินทาง: พื้นที่คำตอบคือวงจรแฮมิลตันที่เป็นไปได้ทั้งหมดในกราฟ การแตกกิ่งสามารถทำได้บนเส้นเชื่อม (รวมหรือตัดออกจากเส้นทาง) ขอบเขตล่างอาจได้จากการแก้ปัญหาที่ง่ายกว่า เช่น ปัญหาการมอบหมายงานหรือการสร้างต้นไม้ครอบคลุมขั้นต่ำ

แนวคิดที่เกี่ยวข้องและการประยุกต์ใช้

• วิธีแบ่งกิ่งและตัด (Branch-and-Cut): วิธีผสมที่รวม B&B กับวิธีระนาบตัด ในแต่ละโหนดของต้นไม้การค้นหา นอกเหนือจากการแก้ relaxation ยังมีการสร้างอสมการเพิ่มเติม (การตัด) ที่ช่วยเสริมขอบเขตล่าง ซึ่งนำไปสู่การตัดกิ่งที่มีประสิทธิภาพมากขึ้น
• การค้นหาแบบย้อนกลับ (Backtracking): วิธีแบ่งและกำหนดขอบเขตสามารถมองได้ว่าเป็นการขยายทั่วไปของอัลกอริทึมนี้สำหรับปัญหาการหาค่าเหมาะสม
• Alpha-beta pruning: การเปรียบเทียบเชิงแนวคิดที่ใช้ในต้นไม้เกมสำหรับการตัดกิ่งที่เสียเปรียบอย่างแน่นอน

ดูเพิ่มเติม

• การโปรแกรมเชิงเส้นแบบจำนวนเต็ม
• การหาค่าเหมาะสมแบบผสม
• ปัญหาพนักงานขายเดินทาง
• ปัญหา NP-hard
• วิธี Simplex

หมายเหตุ

</references>