---
title: "Branch and bound — วิธีแบ่งและกำหนดขอบเขต"
source: "https://systems-analysis.info/int/Branch_and_bound_%E2%80%94_%E0%B8%A7%E0%B8%B4%E0%B8%98%E0%B8%B5%E0%B9%81%E0%B8%9A%E0%B9%88%E0%B8%87%E0%B9%81%E0%B8%A5%E0%B8%B0%E0%B8%81%E0%B8%B3%E0%B8%AB%E0%B8%99%E0%B8%94%E0%B8%82%E0%B8%AD%E0%B8%9A%E0%B9%80%E0%B8%82%E0%B8%95"
wiki: "systems-analysis.info/int"
article: "Branch_and_bound_—_วิธีแบ่งและกำหนดขอบเขต"
language: "th"
categories:
  - "Category:Operations research"
  - "Category:Thai"
revision_id: 818
wiki_created_at: 2026-09-06T22:39:16Z
wiki_modified_at: 2026-09-06T22:39:16Z
downloaded_at: 2026-09-07T22:42:32Z
---

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

**วิธีแบ่งและกำหนดขอบเขต** (อังกฤษ: *Branch and Bound* ย่อว่า **B&B** หรือ **BnB**) คือกระบวนทัศน์ทั่วไปสำหรับการสร้างอัลกอริทึมแม่นยำในการแก้ปัญหาการหาค่าเหมาะสมแบบไม่ต่อเนื่องและแบบผสม โดยเฉพาะปัญหาที่เป็น NP-hard<sup>[\[1\]](https://systems-analysis.info/int/Branch_and_bound_%E2%80%94_%E0%B8%A7%E0%B8%B4%E0%B8%98%E0%B8%B5%E0%B9%81%E0%B8%9A%E0%B9%88%E0%B8%87%E0%B9%81%E0%B8%A5%E0%B8%B0%E0%B8%81%E0%B8%B3%E0%B8%AB%E0%B8%99%E0%B8%94%E0%B8%82%E0%B8%AD%E0%B8%9A%E0%B9%80%E0%B8%82%E0%B8%95#cite_note-en-wiki-bnb-1)</sup> วิธีนี้เป็นกลยุทธ์การค้นหาแบบมีทิศทาง ซึ่งแบ่งเซตของคำตอบที่ยอมรับได้ทั้งหมดออกเป็นเซตย่อยอย่างต่อเนื่อง (**การแตกกิ่ง**) และสำหรับแต่ละเซตย่อยจะคำนวณค่าประมาณ (**ขอบเขต**) ของฟังก์ชันวัตถุประสงค์ ค่าประมาณเหล่านี้ช่วยให้ตัดทิ้งเซตย่อยที่ไม่มีทางมีคำตอบที่เหมาะสมอยู่แน่นอน ซึ่งช่วยลดขนาดของพื้นที่การค้นหาได้อย่างมีนัยสำคัญ<sup>[\[2\]](https://systems-analysis.info/int/Branch_and_bound_%E2%80%94_%E0%B8%A7%E0%B8%B4%E0%B8%98%E0%B8%B5%E0%B9%81%E0%B8%9A%E0%B9%88%E0%B8%87%E0%B9%81%E0%B8%A5%E0%B8%B0%E0%B8%81%E0%B8%B3%E0%B8%AB%E0%B8%99%E0%B8%94%E0%B8%82%E0%B8%AD%E0%B8%9A%E0%B9%80%E0%B8%82%E0%B8%95#cite_note-ru-wiki-bnb-2)</sup>

วิธีนี้ถูกเสนอครั้งแรกโดย A. Land และ A. Doig ในปี ค.ศ. 1960 เพื่อแก้ปัญหาการโปรแกรมเชิงเส้นแบบจำนวนเต็ม<sup>[\[3\]](https://systems-analysis.info/int/Branch_and_bound_%E2%80%94_%E0%B8%A7%E0%B8%B4%E0%B8%98%E0%B8%B5%E0%B9%81%E0%B8%9A%E0%B9%88%E0%B8%87%E0%B9%81%E0%B8%A5%E0%B8%B0%E0%B8%81%E0%B8%B3%E0%B8%AB%E0%B8%99%E0%B8%94%E0%B8%82%E0%B8%AD%E0%B8%9A%E0%B9%80%E0%B8%82%E0%B8%95#cite_note-land-doig-1960-3)</sup> นับแต่นั้นมา วิธีนี้ได้กลายเป็นหนึ่งในแนวทางพื้นฐานที่สำคัญที่สุดในการวิจัยเชิงปฏิบัติการและวิทยาการคอมพิวเตอร์ คุณลักษณะสำคัญของวิธีนี้คือความยืดหยุ่น เนื่องจากมันไม่ใช่อัลกอริทึมเฉพาะเจาะจง แต่เป็นกรอบกลยุทธ์ระดับสูง (framework) ที่ปรับให้เข้ากับโครงสร้างของปัญหาที่ต้องการแก้ได้

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

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

- **การแตกกิ่ง** (อังกฤษ: *Branching*) คือกระบวนการแบ่งเซตของคำตอบที่ยอมรับได้ในปัจจุบัน $S_{i}$ ออกเป็นเซตย่อยที่เล็กกว่าหลายเซต ซึ่งโดยทั่วไปจะไม่ทับซ้อนกัน $S_{i1},S_{i2},\ldots,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 \geq U$
    - หากคำตอบของ relaxation ยอมรับได้สำหรับปัญหาต้นฉบับ ให้อัปเดตค่าบันทึก: $U\leftarrow L$
    - หากโหนดไม่ถูกตัดทิ้งและคำตอบไม่ยอมรับได้ ให้ดำเนินการ**แตกกิ่ง** โดยแบ่งออกเป็นโหนดลูกและเพิ่มเข้าไปในคิว $Q$
3.  **การสิ้นสุด:** เมื่อคิว $Q$ ว่างเปล่า อัลกอริทึมจะสิ้นสุด คำตอบที่พบซึ่งสอดคล้องกับค่าบันทึก $U$ คือคำตอบที่เหมาะสมที่สุดในระดับโลก

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

- **ความถูกต้องและการลู่เข้า:** อัลกอริทึมรับประกันการหาคำตอบที่เหมาะสมที่สุดในระดับโลกในจำนวนขั้นตอนจำกัด หากเซตของคำตอบที่ยอมรับได้มีจำนวนจำกัด และกระบวนการแตกกิ่งมีการลู่เข้า (กล่าวคือ เมื่อแบ่งซ้ำ เซตย่อยจะ "หดตัว" เข้าหาจุด)<sup>[\[4\]](https://systems-analysis.info/int/Branch_and_bound_%E2%80%94_%E0%B8%A7%E0%B8%B4%E0%B8%98%E0%B8%B5%E0%B9%81%E0%B8%9A%E0%B9%88%E0%B8%87%E0%B9%81%E0%B8%A5%E0%B8%B0%E0%B8%81%E0%B8%B3%E0%B8%AB%E0%B8%99%E0%B8%94%E0%B8%82%E0%B8%AD%E0%B8%9A%E0%B9%80%E0%B8%82%E0%B8%95#cite_note-conitzer-duke-4)</sup>
- **กลยุทธ์การค้นหา:** ประสิทธิภาพของอัลกอริทึมขึ้นอยู่อย่างมากกับกลยุทธ์การเลือกโหนดถัดไปสำหรับการแตกกิ่ง (เช่น การค้นหาเชิงลึก การค้นหาเชิงกว้าง การค้นหาตามค่าประมาณที่ดีที่สุด) และการเลือกตัวแปรสำหรับการแตกกิ่ง ตัวแก้ปัญหาสมัยใหม่มักใช้กลยุทธ์แบบผสม<sup>[\[5\]](https://systems-analysis.info/int/Branch_and_bound_%E2%80%94_%E0%B8%A7%E0%B8%B4%E0%B8%98%E0%B8%B5%E0%B9%81%E0%B8%9A%E0%B9%88%E0%B8%87%E0%B9%81%E0%B8%A5%E0%B8%B0%E0%B8%81%E0%B8%B3%E0%B8%AB%E0%B8%99%E0%B8%94%E0%B8%82%E0%B8%AD%E0%B8%9A%E0%B9%80%E0%B8%82%E0%B8%95#cite_note-maudet-danoy-2024-5)</sup>

## ตัวอย่าง

- **ปัญหาการโปรแกรมเชิงเส้นแบบจำนวนเต็ม**: การประยุกต์ใช้คลาสสิกของวิธีนี้ โดยใช้การโปรแกรมเชิงเส้นเป็น relaxation การแตกกิ่งเกิดขึ้นบนตัวแปรที่มีค่าเป็นเศษส่วน $x_{j}$ โดยสร้างปัญหาย่อยสองปัญหาที่มีข้อจำกัดเพิ่มเติม $x_{j} \leq \lfloor x_{j}^{\ast}\rfloor$ และ $x_{j} \geq \lceil x_{j}^{\ast}\rceil$
- **ปัญหาพนักงานขายเดินทาง**: พื้นที่คำตอบคือวงจรแฮมิลตันที่เป็นไปได้ทั้งหมดในกราฟ การแตกกิ่งสามารถทำได้บนเส้นเชื่อม (รวมหรือตัดออกจากเส้นทาง) ขอบเขตล่างอาจได้จากการแก้ปัญหาที่ง่ายกว่า เช่น ปัญหาการมอบหมายงานหรือการสร้างต้นไม้ครอบคลุมขั้นต่ำ<sup>[\[6\]](https://systems-analysis.info/int/Branch_and_bound_%E2%80%94_%E0%B8%A7%E0%B8%B4%E0%B8%98%E0%B8%B5%E0%B9%81%E0%B8%9A%E0%B9%88%E0%B8%87%E0%B9%81%E0%B8%A5%E0%B8%B0%E0%B8%81%E0%B8%B3%E0%B8%AB%E0%B8%99%E0%B8%94%E0%B8%82%E0%B8%AD%E0%B8%9A%E0%B9%80%E0%B8%82%E0%B8%95#cite_note-little-1963-6)</sup>

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

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

## ดูเพิ่มเติม

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

## หมายเหตุ

<sup>[\[1\]](https://systems-analysis.info/int/Branch_and_bound_%E2%80%94_%E0%B8%A7%E0%B8%B4%E0%B8%98%E0%B8%B5%E0%B9%81%E0%B8%9A%E0%B9%88%E0%B8%87%E0%B9%81%E0%B8%A5%E0%B8%B0%E0%B8%81%E0%B8%B3%E0%B8%AB%E0%B8%99%E0%B8%94%E0%B8%82%E0%B8%AD%E0%B8%9A%E0%B9%80%E0%B8%82%E0%B8%95#cite_note-en-wiki-bnb-1)</sup> <sup>[\[2\]](https://systems-analysis.info/int/Branch_and_bound_%E2%80%94_%E0%B8%A7%E0%B8%B4%E0%B8%98%E0%B8%B5%E0%B9%81%E0%B8%9A%E0%B9%88%E0%B8%87%E0%B9%81%E0%B8%A5%E0%B8%B0%E0%B8%81%E0%B8%B3%E0%B8%AB%E0%B8%99%E0%B8%94%E0%B8%82%E0%B8%AD%E0%B8%9A%E0%B9%80%E0%B8%82%E0%B8%95#cite_note-ru-wiki-bnb-2)</sup> <sup>[\[3\]](https://systems-analysis.info/int/Branch_and_bound_%E2%80%94_%E0%B8%A7%E0%B8%B4%E0%B8%98%E0%B8%B5%E0%B9%81%E0%B8%9A%E0%B9%88%E0%B8%87%E0%B9%81%E0%B8%A5%E0%B8%B0%E0%B8%81%E0%B8%B3%E0%B8%AB%E0%B8%99%E0%B8%94%E0%B8%82%E0%B8%AD%E0%B8%9A%E0%B9%80%E0%B8%82%E0%B8%95#cite_note-land-doig-1960-3)</sup> <sup>[\[4\]](https://systems-analysis.info/int/Branch_and_bound_%E2%80%94_%E0%B8%A7%E0%B8%B4%E0%B8%98%E0%B8%B5%E0%B9%81%E0%B8%9A%E0%B9%88%E0%B8%87%E0%B9%81%E0%B8%A5%E0%B8%B0%E0%B8%81%E0%B8%B3%E0%B8%AB%E0%B8%99%E0%B8%94%E0%B8%82%E0%B8%AD%E0%B8%9A%E0%B9%80%E0%B8%82%E0%B8%95#cite_note-conitzer-duke-4)</sup> <sup>[\[5\]](https://systems-analysis.info/int/Branch_and_bound_%E2%80%94_%E0%B8%A7%E0%B8%B4%E0%B8%98%E0%B8%B5%E0%B9%81%E0%B8%9A%E0%B9%88%E0%B8%87%E0%B9%81%E0%B8%A5%E0%B8%B0%E0%B8%81%E0%B8%B3%E0%B8%AB%E0%B8%99%E0%B8%94%E0%B8%82%E0%B8%AD%E0%B8%9A%E0%B9%80%E0%B8%82%E0%B8%95#cite_note-maudet-danoy-2024-5)</sup> <sup>[\[6\]](https://systems-analysis.info/int/Branch_and_bound_%E2%80%94_%E0%B8%A7%E0%B8%B4%E0%B8%98%E0%B8%B5%E0%B9%81%E0%B8%9A%E0%B9%88%E0%B8%87%E0%B9%81%E0%B8%A5%E0%B8%B0%E0%B8%81%E0%B8%B3%E0%B8%AB%E0%B8%99%E0%B8%94%E0%B8%82%E0%B8%AD%E0%B8%9A%E0%B9%80%E0%B8%82%E0%B8%95#cite_note-little-1963-6)</sup> \</references\>

1.  <span id="cite_note-en-wiki-bnb-1">↑ <sup>[1.0](https://systems-analysis.info/int/Branch_and_bound_%E2%80%94_%E0%B8%A7%E0%B8%B4%E0%B8%98%E0%B8%B5%E0%B9%81%E0%B8%9A%E0%B9%88%E0%B8%87%E0%B9%81%E0%B8%A5%E0%B8%B0%E0%B8%81%E0%B8%B3%E0%B8%AB%E0%B8%99%E0%B8%94%E0%B8%82%E0%B8%AD%E0%B8%9A%E0%B9%80%E0%B8%82%E0%B8%95#cite_ref-en-wiki-bnb_1-0)</sup> <sup>[1.1](https://systems-analysis.info/int/Branch_and_bound_%E2%80%94_%E0%B8%A7%E0%B8%B4%E0%B8%98%E0%B8%B5%E0%B9%81%E0%B8%9A%E0%B9%88%E0%B8%87%E0%B9%81%E0%B8%A5%E0%B8%B0%E0%B8%81%E0%B8%B3%E0%B8%AB%E0%B8%99%E0%B8%94%E0%B8%82%E0%B8%AD%E0%B8%9A%E0%B9%80%E0%B8%82%E0%B8%95#cite_ref-en-wiki-bnb_1-1)</sup> Wikipedia contributors. (2025). Branch and bound. In *Wikipedia, The Free Encyclopedia*. Retrieved 2025-10-26, from <a href="https://en.wikipedia.org/wiki/Branch_and_bound" class="external free" rel="nofollow">https://en.wikipedia.org/wiki/Branch_and_bound</a></span>
2.  <span id="cite_note-ru-wiki-bnb-2">↑ <sup>[2.0](https://systems-analysis.info/int/Branch_and_bound_%E2%80%94_%E0%B8%A7%E0%B8%B4%E0%B8%98%E0%B8%B5%E0%B9%81%E0%B8%9A%E0%B9%88%E0%B8%87%E0%B9%81%E0%B8%A5%E0%B8%B0%E0%B8%81%E0%B8%B3%E0%B8%AB%E0%B8%99%E0%B8%94%E0%B8%82%E0%B8%AD%E0%B8%9A%E0%B9%80%E0%B8%82%E0%B8%95#cite_ref-ru-wiki-bnb_2-0)</sup> <sup>[2.1](https://systems-analysis.info/int/Branch_and_bound_%E2%80%94_%E0%B8%A7%E0%B8%B4%E0%B8%98%E0%B8%B5%E0%B9%81%E0%B8%9A%E0%B9%88%E0%B8%87%E0%B9%81%E0%B8%A5%E0%B8%B0%E0%B8%81%E0%B8%B3%E0%B8%AB%E0%B8%99%E0%B8%94%E0%B8%82%E0%B8%AD%E0%B8%9A%E0%B9%80%E0%B8%82%E0%B8%95#cite_ref-ru-wiki-bnb_2-1)</sup> Wikipedia contributors. (2023). Метод ветвей и границ. In *Русская Википедия*. Retrieved 2025-10-26, from <a href="https://ru.wikipedia.org/wiki/Метод_ветвей_и_границ" class="external free" rel="nofollow">https://ru.wikipedia.org/wiki/Метод_ветвей_и_границ</a></span>
3.  <span id="cite_note-land-doig-1960-3">↑ <sup>[3.0](https://systems-analysis.info/int/Branch_and_bound_%E2%80%94_%E0%B8%A7%E0%B8%B4%E0%B8%98%E0%B8%B5%E0%B9%81%E0%B8%9A%E0%B9%88%E0%B8%87%E0%B9%81%E0%B8%A5%E0%B8%B0%E0%B8%81%E0%B8%B3%E0%B8%AB%E0%B8%99%E0%B8%94%E0%B8%82%E0%B8%AD%E0%B8%9A%E0%B9%80%E0%B8%82%E0%B8%95#cite_ref-land-doig-1960_3-0)</sup> <sup>[3.1](https://systems-analysis.info/int/Branch_and_bound_%E2%80%94_%E0%B8%A7%E0%B8%B4%E0%B8%98%E0%B8%B5%E0%B9%81%E0%B8%9A%E0%B9%88%E0%B8%87%E0%B9%81%E0%B8%A5%E0%B8%B0%E0%B8%81%E0%B8%B3%E0%B8%AB%E0%B8%99%E0%B8%94%E0%B8%82%E0%B8%AD%E0%B8%9A%E0%B9%80%E0%B8%82%E0%B8%95#cite_ref-land-doig-1960_3-1)</sup> Land, A. H.; Doig, A. G. (1960). An automatic method of solving discrete programming problems. *Econometrica*, 28(3), 497–520. DOI: 10.2307/1910129. URL: <a href="https://www.jstor.org/stable/1910129" class="external free" rel="nofollow">https://www.jstor.org/stable/1910129</a></span>
4.  <span id="cite_note-conitzer-duke-4">↑ <sup>[4.0](https://systems-analysis.info/int/Branch_and_bound_%E2%80%94_%E0%B8%A7%E0%B8%B4%E0%B8%98%E0%B8%B5%E0%B9%81%E0%B8%9A%E0%B9%88%E0%B8%87%E0%B9%81%E0%B8%A5%E0%B8%B0%E0%B8%81%E0%B8%B3%E0%B8%AB%E0%B8%99%E0%B8%94%E0%B8%82%E0%B8%AD%E0%B8%9A%E0%B9%80%E0%B8%82%E0%B8%95#cite_ref-conitzer-duke_4-0)</sup> <sup>[4.1](https://systems-analysis.info/int/Branch_and_bound_%E2%80%94_%E0%B8%A7%E0%B8%B4%E0%B8%98%E0%B8%B5%E0%B9%81%E0%B8%9A%E0%B9%88%E0%B8%87%E0%B9%81%E0%B8%A5%E0%B8%B0%E0%B8%81%E0%B8%B3%E0%B8%AB%E0%B8%99%E0%B8%94%E0%B8%82%E0%B8%AD%E0%B8%9A%E0%B9%80%E0%B8%82%E0%B8%95#cite_ref-conitzer-duke_4-1)</sup> Conitzer, V. (2008). *Solving (mixed) integer programs using branch and bound*. Duke University, Department of Computer Science. URL: <a href="https://courses.cs.duke.edu/spring08/cps296.2/branch_and_bound.pdf" class="external free" rel="nofollow">https://courses.cs.duke.edu/spring08/cps296.2/branch_and_bound.pdf</a></span>
5.  <span id="cite_note-maudet-danoy-2024-5">↑ <sup>[5.0](https://systems-analysis.info/int/Branch_and_bound_%E2%80%94_%E0%B8%A7%E0%B8%B4%E0%B8%98%E0%B8%B5%E0%B9%81%E0%B8%9A%E0%B9%88%E0%B8%87%E0%B9%81%E0%B8%A5%E0%B8%B0%E0%B8%81%E0%B8%B3%E0%B8%AB%E0%B8%99%E0%B8%94%E0%B8%82%E0%B8%AD%E0%B8%9A%E0%B9%80%E0%B8%82%E0%B8%95#cite_ref-maudet-danoy-2024_5-0)</sup> <sup>[5.1](https://systems-analysis.info/int/Branch_and_bound_%E2%80%94_%E0%B8%A7%E0%B8%B4%E0%B8%98%E0%B8%B5%E0%B9%81%E0%B8%9A%E0%B9%88%E0%B8%87%E0%B9%81%E0%B8%A5%E0%B8%B0%E0%B8%81%E0%B8%B3%E0%B8%AB%E0%B8%99%E0%B8%94%E0%B8%82%E0%B8%AD%E0%B8%9A%E0%B9%80%E0%B8%82%E0%B8%95#cite_ref-maudet-danoy-2024_5-1)</sup> Maudet, G.; Danoy, G. (2024). Search Strategy Generation for Branch and Bound Using Genetic Programming. *arXiv preprint arXiv:2412.09444*. DOI: 10.48550/arXiv.2412.09444. URL: <a href="https://arxiv.org/abs/2412.09444" class="external free" rel="nofollow">https://arxiv.org/abs/2412.09444</a></span>
6.  <span id="cite_note-little-1963-6">↑ <sup>[6.0](https://systems-analysis.info/int/Branch_and_bound_%E2%80%94_%E0%B8%A7%E0%B8%B4%E0%B8%98%E0%B8%B5%E0%B9%81%E0%B8%9A%E0%B9%88%E0%B8%87%E0%B9%81%E0%B8%A5%E0%B8%B0%E0%B8%81%E0%B8%B3%E0%B8%AB%E0%B8%99%E0%B8%94%E0%B8%82%E0%B8%AD%E0%B8%9A%E0%B9%80%E0%B8%82%E0%B8%95#cite_ref-little-1963_6-0)</sup> <sup>[6.1](https://systems-analysis.info/int/Branch_and_bound_%E2%80%94_%E0%B8%A7%E0%B8%B4%E0%B8%98%E0%B8%B5%E0%B9%81%E0%B8%9A%E0%B9%88%E0%B8%87%E0%B9%81%E0%B8%A5%E0%B8%B0%E0%B8%81%E0%B8%B3%E0%B8%AB%E0%B8%99%E0%B8%94%E0%B8%82%E0%B8%AD%E0%B8%9A%E0%B9%80%E0%B8%82%E0%B8%95#cite_ref-little-1963_6-1)</sup> Little, J. D. C.; Murty, K. G.; Sweeney, D. W.; Karel, C. (1963). An Algorithm for the Traveling Salesman Problem. *Operations Research*, 11(6), 972–989. DOI: 10.1287/opre.11.6.972. URL: <a href="https://dspace.mit.edu/bitstream/handle/1721.1/46907/branchboundmetho00litt.pdf" class="external free" rel="nofollow">https://dspace.mit.edu/bitstream/handle/1721.1/46907/branchboundmetho00litt.pdf</a></span>