Branch and Bound
- ผู้เสนอ
- Ailsa Land & Alison Doig
- ปี
- 1960
- ประเภท
- Exact combinatorial optimization algorithm
- กลุ่มวิธี
- Mathematical programming
ข้อความนี้เป็นการแปลด้วยเครื่องและยังไม่ได้รับการตรวจทาน อ่านต้นฉบับภาษาอังกฤษ
ใช้ทำอะไร?
Branch and Bound เป็นอัลกอริทึมแบบแม่นตรง (exact algorithm) ที่เป็นระบบสำหรับการแก้ปัญหาการหาค่าเหมาะสมที่สุดเชิงการจัด (combinatorial optimization) และปัญหาจำนวนเต็ม (integer optimization) ซึ่งถูกนำเสนอโดย Ailsa Land และ Alison Doig ในปี 1960 อัลกอริทึมนี้จัดระเบียบปริภูมิการค้นหา (search space) ให้เป็นโครงสร้างแบบต้นไม้ (tree) ของปัญหาย่อย (subproblems) โดยใช้ค่าขอบบน (upper bounds) ที่ได้จากการผ่อนคลายเงื่อนไข (relaxation) เพื่อตัดกิ่งก้าน (prune branches) ที่ไม่สามารถปรับปรุงผลเฉลยที่ดีที่สุดที่ทราบได้ให้ดีขึ้น และรับประกันว่าจะได้ผลเฉลยจำนวนเต็มที่เหมาะสมที่สุดในระดับโลก (globally optimal integer solution) อัลกอริทึมนี้เป็นแกนหลักของตัวแก้ปัญหาการหาค่าเหมาะสมที่สุดเชิงจำนวนเต็มแบบผสม (mixed-integer programming solvers) ที่ทันสมัย ซึ่งใช้ในสาขาการวิจัยดำเนินงาน (operations research), โลจิสติกส์ (logistics), การจัดตารางเวลา (scheduling), และการออกแบบทางวิศวกรรม (engineering design)
แนวคิดเบื้องหลังวิธีการ
ลองจินตนาการถึงการค้นหาสิ่งของที่มีมูลค่าสูงสุดซึ่งซ่อนอยู่ในเขาวงกตขนาดใหญ่ที่มีห้องมากมาย แทนที่จะตรวจสอบทุกห้อง คุณจะประมาณค่าสูงสุดที่เป็นไปได้ที่จะได้รับจากแต่ละทางเดินก่อนที่จะเข้าไป หากค่าสูงสุดที่เป็นไปได้นั้นต่ำกว่าสิ่งของที่ดีที่สุดที่คุณมีอยู่แล้ว คุณก็จะข้ามทางเดินทั้งหมดนั้นไปโดยไม่ต้องเข้าไปดู Branch and Bound ทำงานในลักษณะเดียวกัน คือ แบ่งปัญหาออกเป็นส่วนย่อยๆ คำนวณค่าขอบบนที่มองโลกในแง่ดี (optimistic upper bounds) สำหรับแต่ละส่วน และทิ้งส่วนใดๆ ที่พิสูจน์ได้ว่าไม่สามารถดีกว่าผลเฉลยที่ดีที่สุดในปัจจุบันได้ทันที
ประวัติศาสตร์
Land และ Doig ได้ตีพิมพ์บทความพื้นฐานเกี่ยวกับ Branch and Bound ในวารสาร Econometrica ในปี 1960 โดยนำเสนอในฐานะวิธีการอัตโนมัติสำหรับการหาค่าเหมาะสมที่สุดแบบไม่ต่อเนื่อง (discrete programming) Little และคณะ (1963) ได้นำเทคนิคนี้ไปใช้กับปัญหาพนักงานขายเดินทาง (traveling salesman problem) ซึ่งตอกย้ำบทบาทของมันในการหาค่าเหมาะสมที่สุดเชิงการจัด (combinatorial optimization) Dakin (1965) ได้นำเสนอการแตกกิ่งด้วย LP-relaxation ซึ่งเป็นรูปแบบที่ใช้กันทั่วไปในปัจจุบัน ในทศวรรษต่อๆ มา ได้มีการบูรณาการระนาบตัด (branch-and-cut) และการสร้างคอลัมน์ (column generation) (branch-and-price) ทำให้ Branch and Bound กลายเป็นกลไกหลักของตัวแก้ปัญหาการหาค่าเหมาะสมที่สุดเชิงจำนวนเต็มเชิงพาณิชย์ทั้งหมด
ควรใช้เมื่อใด
ควรใช้ Branch and Bound เมื่อคุณต้องการผลเฉลัพธ์ที่พิสูจน์ได้ว่าเหมาะสมที่สุดสำหรับปัญหา linear program แบบจำนวนเต็มหรือจำนวนเต็มแบบผสม (mixed-integer or pure-integer linear program) และไม่สามารถยอมรับคำตอบโดยประมาณได้ อัลกอริทึมนี้ตั้งสมมติฐานว่าปัญหาสามารถสร้างแบบจำลองได้ด้วยการผ่อนคลายเชิงเส้น (linear relaxations) หรือเชิงนูน (convex relaxations) ที่ให้ค่าขอบบนที่มีประโยชน์ อัลกอริทึมนี้ไม่เหมาะสำหรับปัญหาที่มีขนาดใหญ่มากซึ่งต้นไม้การแจงนับ (enumeration tree) ขยายตัวมากเกินไป, สำหรับปัญหาจำนวนเต็มที่ไม่ใช่เชิงเส้น (nonlinear integer programs) ที่ไม่มีการผ่อนคลายที่แม่นยำ, หรือสำหรับสถานการณ์แบบเรียลไทม์ที่เวลาในการคำนวณมีจำกัดอย่างเข้มงวด ในกรณีดังกล่าว อาจนิยมใช้วิธีการประมาณ (heuristics) หรือวิธีการประมาณขั้นสูง (metaheuristics)
ข้อจำกัดและข้อควรพิจารณา
- ความซับซ้อนในกรณีที่แย่ที่สุด (worst-case complexity) เป็นแบบเลขชี้กำลัง (exponential); ในกรณีที่โครงสร้างไม่ดี ต้นไม้อาจเติบโตใหญ่จนไม่สามารถจัดการได้
- ประสิทธิภาพมีความไวสูงต่อการเลือกตัวแปรที่จะแตกกิ่ง (branching variable) และกลยุทธ์การเลือกโหนด (node selection strategy)
- ต้องการการผ่อนคลายที่สามารถจัดการได้ซึ่งให้ค่าขอบบนที่มีความหมาย; ค่าขอบบนที่อ่อนแอจะนำไปสู่การตัดกิ่งน้อย
- ข้อกำหนดหน่วยความจำอาจมีจำนวนมากเมื่อต้องจัดเก็บโหนดที่เปิดอยู่จำนวนมากพร้อมกัน
เงื่อนไขจากแหล่งที่มาไม่สามารถใช้แทนการทบทวนทางวิทยาศาสตร์ที่เป็นอิสระหรือการตรวจสอบโดยเอนจินวิเคราะห์ได้
จุดแข็ง
- รับประกันความเป็นเหมาะสมที่สุดในระดับโลกสำหรับปัญหาเชิงการจัดและปัญหาจำนวนเต็ม
- ลดการค้นหาลงอย่างมากด้วยการตัดกิ่งตามค่าขอบบน — บ่อยครั้งสำรวจเพียงเศษเสี้ยวเล็กๆ ของต้นไม้การแจงนับทั้งหมด
- มีความยืดหยุ่น: สามารถรวมระนาบตัด (cutting planes) (branch-and-cut) หรือค่าขอบบนโดยใช้การประมาณ (heuristic bounds) (branch-and-price) เพื่อเพิ่มประสิทธิภาพ
- ถูกนำไปใช้อย่างกว้างขวางในตัวแก้ปัญหาเชิงพาณิชย์ที่พัฒนาแล้ว (CPLEX, Gurobi) และเครื่องมือโอเพนซอร์ส (GLPK, CBC)
การประยุกต์ใช้
- การจัดตารางลูกเรือสายการบินและการมอบหมายฝูงบินในการวิจัยดำเนินงาน
- การออกแบบเครือข่ายห่วงโซ่อุปทานและปัญหาการกำหนดที่ตั้งของโรงงาน
- การจัดวางวงจรรวม VLSI และการจัดสรรรีจิสเตอร์ในวิศวกรรมคอมพิวเตอร์
- การทำนายโครงสร้างโปรตีนและการประกอบจีโนมในชีววิทยาเชิงคำนวณ
- การหาค่าเหมาะสมที่สุดของพอร์ตการลงทุนทางการเงินพร้อมข้อจำกัดด้านจำนวนรายการ (cardinality constraints)
วิธีการทำงาน
วิธีการทำงาน
อัลกอริทึมเริ่มต้นด้วยการแก้ปัญหาในรูปแบบที่ผ่อนคลาย (relaxed version) ซึ่งโดยทั่วไปคือ LP relaxation ที่ละเลยข้อจำกัดเรื่องความเป็นจำนวนเต็ม (integrality constraints) การผ่อนคลายนี้จะให้ค่าขอบบนของค่าที่เหมาะสมที่สุดที่แท้จริง เนื่องจากทุกผลเฉลยจำนวนเต็มที่เป็นไปได้ (feasible integer solution) ก็เป็นผลเฉลยที่ทำได้ในการผ่อนคลายนั้นด้วย หากผลเฉลยที่ผ่อนคลายนั้นมีค่าเป็นจำนวนเต็ม ปัญหาก็จะถูกแก้ไขทันที
สูตร
\text{Solve LP relaxation: } z^* = \max\{\mathbf{c}^\top \mathbf{x} \mid A\mathbf{x} \leq \mathbf{b},\, \mathbf{x} \geq 0\}เมื่อผลเฉลยที่ผ่อนคลายมีตัวแปรที่มีค่าเป็นเศษส่วน (fractional variable) อัลกอริทึมจะแบ่งปริภูมิที่เป็นไปได้ (feasible region) โดยการเพิ่มข้อจำกัดที่เสริมกัน (complementary constraints) ซึ่งบังคับให้ตัวแปรนั้นมีค่าเป็นจำนวนเต็มที่ปัดลง (floor) หรือปัดขึ้น (ceiling) การแบ่งแต่ละครั้งจะสร้างโหนดลูก (child node) ใหม่ในต้นไม้การค้นหา ซึ่งเป็นการแบ่งปัญหาย่อยหนึ่งออกเป็นสองปัญหาย่อยที่เล็กลงพร้อมกับขอบเขตที่จำกัดมากขึ้น
สูตร
\text{Select fractional variable } x_j \notin \mathbb{Z}\text{; create sub-problems: } x_j \leq \lfloor x_j^* \rfloor \text{ and } x_j \geq \lceil x_j^* \rceilแต่ละโหนดที่ยังทำงานอยู่ (active node) จะได้รับค่าขอบบนจากการผ่อนคลายของตนเอง โหนดที่มีค่าขอบบนไม่เกินผลเฉลยจำนวนเต็มที่ดีที่สุดที่พบจนถึงขณะนั้น ซึ่งเรียกว่า incumbent (ผลเฉลยที่ดีที่สุดปัจจุบัน) จะไม่สามารถมีผลเฉลยที่ดีกว่าได้ ดังนั้นจึงถูกตัดออก (pruned) ค่าขอบบนที่แม่นยำมีความสำคัญอย่างยิ่ง: ยิ่งค่าขอบบนแม่นยำเท่าใด ก็ยิ่งต้องสำรวจโหนดน้อยลงเท่านั้น
สูตร
\text{Compute bound } UB_k \text{ for node } k\text{; prune if } UB_k \leq z_{\text{inc}}โหนดจะถูกพิจารณาว่าสิ้นสุด (fathomed) (ปิดถาวร) ภายใต้เงื่อนไขสามประการ: การผ่อนคลายของโหนดนั้นไม่สามารถทำได้ (infeasible), ค่าขอบบนของโหนดนั้นไม่ดีไปกว่า incumbent, หรือผลเฉลยที่ผ่อนคลายของโหนดนั้นเป็นจำนวนเต็มที่ทำได้แล้ว (integer-feasible) ในกรณีสุดท้าย incumbent จะได้รับการปรับปรุงหากผลเฉลยใหม่ทำให้ดีขึ้น อัลกอริทึมจะสิ้นสุดเมื่อโหนดทั้งหมดสิ้นสุดลง ณ จุดนั้น incumbent คือค่าที่เหมาะสมที่สุดในระดับโลก
สูตร
\text{Fathom node } k \text{ if infeasible, or } UB_k \leq z_{\text{inc}}, \text{ or } \mathbf{x}^*_k \in \mathbb{Z}^n\text{; update } z_{\text{inc}} \leftarrow \max(z_{\text{inc}}, z_k)ข้อผิดพลาดที่พบบ่อย
- การเลือกตัวแปรที่จะแตกกิ่งไม่ดี (เช่น การแตกกิ่งที่ตัวแปรเศษส่วนตัวแรกเสมอ) มักนำไปสู่ต้นไม้ที่ลึก ไม่สมดุล และการลู่เข้าช้า
- การละเลยอสมการที่ถูกต้อง (valid inequalities) (ระนาบตัด) หมายถึงการพลาดโอกาสในการทำให้ค่าขอบบนของการผ่อนคลายแม่นยำขึ้นอย่างมาก
- การสิ้นสุดก่อนกำหนดโดยมีช่องว่างของความไม่เหมาะสมที่สุด (suboptimality gap) ที่ไม่ได้รายงานว่าเป็นเช่นนั้น อาจทำให้ผู้ปฏิบัติงานเข้าใจผิดว่าผลเฉลยที่ใกล้เคียงที่สุด (near-optimal solution) เป็นผลเฉลยที่แม่นยำ
- การใช้ Branch and Bound กับการผ่อนคลายที่ไม่ใช่เชิงเส้นหรือไม่ใช่เชิงนูน (nonlinear or non-convex relaxations) โดยไม่มีการทำให้เป็นเชิงนูนแบบพิเศษ อาจให้ค่าขอบบนที่ไม่ถูกต้องและผลลัพธ์ที่ไม่ถูกต้อง
คำถามที่พบบ่อย
Branch and Bound แตกต่างจากการแจงนับแบบครบถ้วน (exhaustive enumeration) อย่างไร?
การแจงนับแบบครบถ้วนจะประเมินผลเฉลยจำนวนเต็มที่เป็นไปได้ทุกผลเฉลยอย่างชัดเจน ซึ่งไม่สามารถคำนวณได้ในทางปฏิบัติสำหรับปัญหาขนาดใหญ่ Branch and Bound หลีกเลี่ยงปัญหานี้โดยการคำนวณค่าขอบบนที่อิงจากการผ่อนคลายที่แต่ละโหนดของต้นไม้การค้นหา และตัดกิ่งของต้นไม้ทั้งหมดเมื่อค่าขอบบนไม่สามารถเกินผลเฉลยที่ดีที่สุดที่พบแล้ว ในทางปฏิบัติ มีเพียงส่วนเล็กๆ ของต้นไม้เท่านั้นที่จะถูกตรวจสอบ
บทบาทของการผ่อนคลาย LP (LP relaxation) ใน Branch and Bound คืออะไร?
การผ่อนคลาย LP จะละทิ้งข้อจำกัดเรื่องความเป็นจำนวนเต็ม ทำให้ปัญหาสามารถแก้ไขได้ในเวลาพหุนาม (polynomial time) ด้วยวิธี simplex หรือ interior-point ค่าที่เหมาะสมที่สุดของการผ่อนคลายนี้ทำหน้าที่เป็นค่าขอบบนสำหรับปัญหาย่อยจำนวนเต็มที่สอดคล้องกัน เมื่อค่าขอบบนนี้แม่นยำ — ใกล้เคียงกับค่าที่เหมาะสมที่สุดของจำนวนเต็มที่แท้จริง — จะต้องสำรวจกิ่งน้อยลง การผ่อนคลายที่แม่นยำยิ่งขึ้น ซึ่งมักจะทำได้โดยการเพิ่มอสมการที่ถูกต้อง จะช่วยเร่งอัลกอริทึมโดยรวมได้อย่างมาก
เมื่อใดที่ฉันควรใช้ Branch and Bound แทน metaheuristic เช่น genetic algorithms?
เลือก Branch and Bound เมื่อคุณต้องการใบรับรองความเป็นเหมาะสมที่สุด (certificate of optimality) และสามารถยอมรับเวลาในการคำนวณได้ เหมาะสำหรับปัญหาขนาดกลางที่มีการผ่อนคลาย LP ที่มีโครงสร้างดี Metaheuristics จะเหมาะสมกว่าเมื่อปัญหามีขนาดใหญ่มาก ขาดการผ่อนคลายที่มีประโยชน์ หรือต้องแก้ไขภายในกรอบเวลาที่จำกัด ซึ่งผลเฉลยที่ใกล้เคียงที่สุดเป็นที่ยอมรับได้ ผู้ปฏิบัติงานจำนวนมากรวมทั้งสองวิธีเข้าด้วยกัน: ใช้ Branch and Bound โดยมีการยอมรับค่าความคลาดเคลื่อนเมื่อสิ้นสุดก่อนกำหนด (early-termination gap tolerance)
วิธีการที่เกี่ยวข้อง
แหล่งอ้างอิง
Land, A. H., & Doig, A. G. (1960). An automatic method of solving discrete programming problems. Econometrica, 28(3), 497–520.
เปิดเอกสารอ้างอิง DOIคัดลอกแล้ว