การโปรแกรมจำนวนเต็มผสม — การหาค่าเหมาะสมที่สุดแบบแม่นยำสำหรับตัวแปรตัดสินใจแบบต่อเนื่องและจำนวนเต็ม
- ผู้เสนอ
- Ralph Gomory (branch-and-bound cuts, 1958); Land & Doig (branch-and-bound, 1960)
- ปี
- 1958–1960
- ประเภท
- Mathematical optimization
- กลุ่มวิธี
- Simulation / optimization
ข้อความนี้เป็นการแปลด้วยเครื่องและยังไม่ได้รับการตรวจทาน อ่านต้นฉบับภาษาอังกฤษ
ใช้ทำอะไร?
การโปรแกรมจำนวนเต็มผสม (Mixed-Integer Programming: MIP) เป็นกรอบการหาค่าเหมาะสมที่สุดทางคณิตศาสตร์ที่ตัวแปรตัดสินใจบางตัวต้องมีค่าเป็นจำนวนเต็ม ในขณะที่ตัวแปรอื่น ๆ อาจเป็นค่าต่อเนื่อง เป็นการขยายแนวคิดของการโปรแกรมเชิงเส้น และถูกนำมาใช้อย่างแพร่หลายในการวิจัยดำเนินงาน, โลจิสติกส์, การจัดตารางเวลา, การจัดสรรทรัพยากร และการออกแบบทางวิศวกรรม ซึ่งมักมีข้อจำกัดที่แบ่งแยกไม่ได้เกิดขึ้นตามธรรมชาติ เช่น การตัดสินใจแบบใช่/ไม่ใช่ หรือปริมาณที่เป็นหน่วยเต็ม
แนวคิดเบื้องหลังวิธีการ
ปัญหาการหาค่าเหมาะสมที่สุดในโลกแห่งความเป็นจริงจำนวนมากเกี่ยวข้องกับการตัดสินใจที่ไม่สามารถแบ่งแยกได้ เช่น คุณจะเปิดโรงงานหรือไม่เปิด, คุณจะมอบหมายพนักงานหนึ่งคนเข้ากะงานพอดี, คุณจะสั่งซื้อสินค้าเป็นหน่วยเต็ม การโปรแกรมเชิงเส้นแบบต่อเนื่องละเลยความเป็นจริงเหล่านี้และอาจให้คำตอบที่เป็นเศษส่วนซึ่งไม่สามารถนำไปปฏิบัติได้ MIP บังคับใช้ความเป็นจำนวนเต็มโดยตรงในแบบจำลอง ตัวแก้ปัญหาจะสำรวจพื้นที่ของคำตอบจำนวนเต็มที่เป็นไปได้อย่างเป็นระบบผ่านวิธีการ Branch-and-Bound: โดยจะแก้ปัญหาย่อยแบบต่อเนื่องที่ผ่อนคลาย (relaxed continuous subproblems) เพื่อกำหนดขอบเขตของคำตอบที่ดีที่สุดที่เป็นไปได้ในแต่ละภูมิภาค, ตัดทิ้งภูมิภาคที่ไม่สามารถปรับปรุงคำตอบจำนวนเต็มที่ดีที่สุดที่พบได้ และเพิ่ม Cutting Planes เพื่อกระชับการค้นหา ผลลัพธ์ที่ได้คือแผนงานที่พิสูจน์ได้ว่าเหมาะสมที่สุดหรือใกล้เคียงที่สุด
ประวัติศาสตร์
รากฐานของการโปรแกรมจำนวนเต็มถูกวางโดย Ralph Gomory ผู้แนะนำวิธีการ Cutting-Plane ในปี 1958 และโดย Land และ Doig ผู้กำหนดรูปแบบ Branch-and-Bound ในปี 1960 ทศวรรษต่อมาได้เห็นการพัฒนาทฤษฎี LP relaxation, Polyhedral Combinatorics (Edmonds, Padberg, Grötschel) และภายในทศวรรษ 1990 ตัวแก้ปัญหาเชิงพาณิชย์ทำให้ MIP ขนาดใหญ่สามารถนำไปใช้ได้จริง สาขาวิชานี้ได้รับการกล่าวถึงอย่างครอบคลุมใน Nemhauser and Wolsey (1988) และ Wolsey (1998)
ควรใช้เมื่อใด
ใช้ MIP เมื่อปัญหาของคุณมีฟังก์ชันวัตถุประสงค์และข้อจำกัดที่เป็นเชิงเส้นหรือสามารถทำให้เป็นเชิงเส้นได้ และรวมถึงการตัดสินใจที่ต้องมีค่าเป็นจำนวนเต็ม (การเลือกที่ตั้งโรงงาน, การจัดตารางเวลาพนักงาน, การจัดทำงบประมาณลงทุน, การออกแบบเครือข่าย, ปัญหาการตัดสต็อก) เป็นวิธีการที่เลือกใช้เมื่อคุณต้องการคำตอบที่พิสูจน์ได้ว่าเหมาะสมที่สุดหรือมีช่องว่างที่จำกัด และขนาดของปัญหาสามารถจัดการได้ (ตัวแปรหลายพันตัวด้วยตัวแก้ปัญหาสมัยใหม่) ห้ามใช้ MIP เมื่อฟังก์ชันวัตถุประสงค์หรือข้อจำกัดไม่เป็นเชิงเส้นอย่างมาก (ให้ใช้การโปรแกรมไม่เชิงเส้นหรือการโปรแกรมจำนวนเต็มผสมไม่เชิงเส้นแทน), เมื่อปัญหาใหญ่มากจนวิธีการที่แม่นยำไม่สามารถทำได้ (พิจารณา heuristics หรือ metaheuristics), หรือเมื่อการประมาณค่าต่อเนื่องมีความแม่นยำเพียงพอ (ใช้ LP เพื่อความเร็ว)
ข้อจำกัดและข้อควรพิจารณา
- ความซับซ้อนในกรณีที่เลวร้ายที่สุดคือ NP-hard; เวลาในการแก้ปัญหาอาจเพิ่มขึ้นแบบทวีคูณตามจำนวนตัวแปรจำนวนเต็ม
- ต้องมีการกำหนดสูตรทางคณิตศาสตร์ที่แม่นยำ; แบบจำลองที่กำหนดสูตรไม่ดีอาจไม่สามารถแก้ไขได้แม้ว่าปัญหาพื้นฐานจะจัดการได้ก็ตาม
- องค์ประกอบที่ไม่เป็นนูน (non-convex) หรือไม่เป็นเชิงเส้นต้องมีการทำให้เป็นเชิงเส้นเพิ่มเติมหรือใช้ตัวแก้ปัญหาเฉพาะทาง ซึ่งเพิ่มความซับซ้อนของแบบจำลอง
- ค่าใช้จ่ายในการอนุญาตใช้ซอฟต์แวร์ตัวแก้ปัญหาอาจสูงสำหรับเครื่องมือเชิงพาณิชย์ แม้ว่าจะมีทางเลือกโอเพนซอร์สคุณภาพสูงอยู่ก็ตาม
- ผลลัพธ์จะดีได้ก็ต่อเมื่อแบบจำลองดีเท่านั้น: การกำหนดข้อจำกัดที่ไม่ถูกต้องนำไปสู่ค่าเหมาะสมที่สุดที่ไม่มีความหมาย
เงื่อนไขจากแหล่งที่มาไม่สามารถใช้แทนการทบทวนทางวิทยาศาสตร์ที่เป็นอิสระหรือการตรวจสอบโดยเอนจินวิเคราะห์ได้
จุดแข็ง
- สร้างคำตอบที่พิสูจน์ได้ว่าเหมาะสมที่สุดพร้อมช่องว่างความเป็นค่าเหมาะสมที่สุดที่สามารถวัดปริมาณได้ ซึ่งช่วยให้การตัดสินใจมีความสมเหตุสมผลอย่างเข้มงวด
- จัดการกับตัวแปรไบนารีและตัวแปรจำนวนเต็มทั่วไปได้อย่างเป็นธรรมชาติ ซึ่งสะท้อนถึงการแบ่งแยกไม่ได้ในโลกแห่งความเป็นจริงและข้อจำกัดเชิงตรรกะ
- ตัวแก้ปัญหาสมัยใหม่ (Gurobi, CPLEX, SCIP) ใช้ประโยชน์จาก Branch-and-Bound ขั้นสูง, Cutting Planes และ Presolve เพื่อจัดการกับปัญหาขนาดใหญ่ได้อย่างมีประสิทธิภาพ
- การกำหนดแบบจำลองที่โปร่งใสทำให้ข้อสมมติฐานชัดเจนและตรวจสอบได้โดยผู้เชี่ยวชาญในสาขา
- รองรับการวิเคราะห์ความอ่อนไหวและการศึกษาพารามิเตอร์เพื่อทำความเข้าใจว่าคำตอบเปลี่ยนแปลงไปอย่างไรเมื่อข้อมูลนำเข้าเปลี่ยนไป
- ได้รับการสนับสนุนอย่างกว้างขวางจากภาษาการสร้างแบบจำลอง (AMPL, GAMS, Pyomo, JuMP) ซึ่งช่วยให้การสร้างต้นแบบทำได้อย่างรวดเร็ว
การประยุกต์ใช้
- ห่วงโซ่อุปทานและโลจิสติกส์: การจัดเส้นทางยานพาหนะ, การเลือกที่ตั้งโรงงาน, และการเพิ่มประสิทธิภาพสินค้าคงคลังด้วยปริมาณการขนส่งที่เป็นจำนวนเต็ม
- การจัดตารางเวลาพนักงาน: การจัดตารางเวรพยาบาล, การมอบหมายลูกเรือ, และการวางแผนกะงานด้วยตัวแปรการมอบหมายแบบไบนารี
- การจัดทำงบประมาณลงทุน: การเลือกกลุ่มโครงการลงทุนที่แบ่งแยกไม่ได้ภายใต้ข้อจำกัดงบประมาณ
- โทรคมนาคมและการออกแบบเครือข่าย: การขยายขีดความสามารถและการจัดเส้นทางด้วยการตัดสินใจเปิดใช้งานลิงก์แบบไบนารี
- ระบบพลังงาน: การจัดสรรหน่วยผลิตในโครงข่ายไฟฟ้าเพื่อตัดสินใจว่าจะเปิดหรือปิดเครื่องกำเนิดไฟฟ้าใดในแต่ละชั่วโมง
- การผลิต: การกำหนดขนาดล็อตการผลิต, การจัดตารางเครื่องจักร, และปัญหาการตัดสต็อกด้วยขนาดชุดการผลิตที่เป็นจำนวนเต็ม
วิธีการทำงาน
วิธีการทำงาน
กำหนดแบบจำลองการหาค่าเหมาะสมที่สุด: ฟังก์ชันวัตถุประสงค์ (การรวมเชิงเส้นของตัวแปรตัดสินใจที่ต้องการลดหรือเพิ่ม), ข้อจำกัดอสมการและสมการเชิงเส้น, และข้อกำหนดความเป็นจำนวนเต็ม ตัวแปรต่อเนื่องใช้จัดการปริมาณที่สามารถเป็นเศษส่วนได้; ตัวแปรไบนารี (0/1) หรือตัวแปรจำนวนเต็มทั่วไปใช้จัดการการตัดสินใจแบบไม่ต่อเนื่อง
สูตร
\min_{x,y}\; c^\top x + d^\top y \quad \text{s.t.}\; Ax + By \leq b,\; x \geq 0,\; y \in \mathbb{Z}^pแก้ปัญหา LP relaxation โดยการละทิ้งข้อจำกัดความเป็นจำนวนเต็มชั่วคราว ซึ่งจะให้ขอบเขตล่าง (สำหรับการหาค่าน้อยที่สุด) ของฟังก์ชันวัตถุประสงค์ MIP ที่เหมาะสมที่สุด และคำตอบที่เป็นไปได้ซึ่งอาจเป็นเศษส่วน
สูตร
\text{LP relaxation: replace } y \in \mathbb{Z}^p \text{ with } y \geq 0เลือกตัวแปรจำนวนเต็มที่เป็นเศษส่วนจากคำตอบของ LP relaxation สร้างปัญหาย่อยลูกสองปัญหาโดยการเพิ่มข้อจำกัดขอบเขตล่าง (floor constraint) ในปัญหาหนึ่งและข้อจำกัดขอบเขตบน (ceiling constraint) ในอีกปัญหาหนึ่ง ซึ่งเป็นการแบ่งพื้นที่ที่เป็นไปได้โดยไม่สูญเสียจุดที่เป็นไปได้ที่เป็นจำนวนเต็มใด ๆ
สูตร
\text{Select fractional } y_j^*; \text{ create subproblems: } y_j \leq \lfloor y_j^* \rfloor \text{ and } y_j \geq \lceil y_j^* \rceilแก้ปัญหา LP relaxation ของปัญหาย่อยแต่ละปัญหา หากขอบเขตที่ได้แย่กว่าคำตอบจำนวนเต็มที่ดีที่สุดที่พบ (incumbent) ให้ตัดกิ่งนั้นทิ้ง หากคำตอบ LP เป็นจำนวนเต็มที่ใช้ได้ ให้ปรับปรุง incumbent หากมันปรับปรุงฟังก์ชันวัตถุประสงค์
สูตร
\text{Prune node if LP bound} \geq \text{incumbent; update incumbent when integer-feasible solution found}เลือกเพิ่ม Cutting Planes — อสมการที่ถูกต้องซึ่งตัดคำตอบ LP ที่เป็นเศษส่วนออกไปโดยไม่ลบจุดที่เป็นไปได้ที่เป็นจำนวนเต็มใด ๆ Gomory cuts เป็นวิธีการคลาสสิก; ส่วน cuts ที่เฉพาะเจาะจงกับปัญหา (เช่น clique cuts, flow cuts) สามารถลดขนาดของต้นไม้ได้อย่างมาก
สูตร
\text{Add Gomory or problem-specific cutting planes to tighten LP relaxation before branching}หยุดเมื่อต้นไม้ Branch-and-Bound ได้รับการสำรวจทั้งหมด หรือเมื่อช่องว่างระหว่างคำตอบจำนวนเต็มที่ดีที่สุดกับขอบเขตล่างทั่วโลกอยู่ในค่าความคลาดเคลื่อนที่ผู้ใช้กำหนด (เช่น 0.01%) ส่งคืนคำตอบ incumbent พร้อมกับใบรับรองความเป็นค่าเหมาะสมที่สุด
สูตร
\text{Stop when all nodes pruned; return incumbent } x^*, y^* \text{ with optimality gap} \leq \epsilonข้อผิดพลาดที่พบบ่อย
- การเลือกค่าความคลาดเคลื่อนความเป็นค่าเหมาะสมที่สุดที่แคบเกินไปอาจทำให้ตัวแก้ปัญหาทำงานไปเรื่อย ๆ โดยไม่มีที่สิ้นสุด; ควรกำหนดค่าความคลาดเคลื่อนที่ใช้งานได้จริงเสมอ (เช่น 1%) สำหรับปัญหาขนาดใหญ่
- ความสมมาตรในแบบจำลอง (เช่น โรงงานที่สับเปลี่ยนกันได้) สร้างกิ่งที่ซ้ำซ้อนและทำให้ต้นไม้การค้นหาขยายใหญ่ขึ้น — ใช้ข้อจำกัดที่ทำลายความสมมาตร
- LP relaxations ที่อ่อนแอ (ช่องว่างความเป็นจำนวนเต็มขนาดใหญ่) นำไปสู่ต้นไม้ Branch-and-Bound ที่ใหญ่มาก; ลงทุนเวลาในการเพิ่มอสมการที่ถูกต้องหรือกระชับการกำหนดสูตร
- การถือว่าตัวแปรทั้งหมดเป็นจำนวนเต็มทั้งที่บางตัวไม่จำเป็นต้องเป็นนั้นมีค่าใช้จ่ายสูงเกินไป; ใช้ตัวแปรไบนารีเฉพาะในกรณีที่ข้อจำกัดเชิงตรรกะต้องการเท่านั้น
- การละเลยการเริ่มต้นแบบ Warm-starting ด้วยคำตอบที่เป็นไปได้เริ่มต้นที่ดีเป็นการสิ้นเปลืองเวลาของตัวแก้ปัญหาในการค้นหา incumbent ตัวแรก
คำถามที่พบบ่อย
MIP แตกต่างจากการโปรแกรมเชิงเส้น (LP) อย่างไร?
LP กำหนดให้ตัวแปรตัดสินใจทั้งหมดเป็นแบบต่อเนื่อง (ค่าจริง) ซึ่งอาจให้คำตอบที่เป็นเศษส่วนซึ่งไม่สามารถทำได้จริง (เช่น รถบรรทุก 2.7 คัน) MIP เพิ่มข้อจำกัดความเป็นจำนวนเต็มในตัวแปรบางตัวหรือทั้งหมด ซึ่งบังคับใช้คำตอบที่เป็นจำนวนเต็มหรือไบนารี โดยมีค่าใช้จ่ายด้านความซับซ้อนในการคำนวณที่สูงขึ้น
ฉันควรใช้ Heuristic แทน MIP เมื่อใด?
เมื่อปัญหามีตัวแปรหลายล้านตัว, โครงสร้างไม่เป็นเชิงเส้นอย่างมาก, หรือต้องการคำตอบแบบเกือบเรียลไทม์, MIP แบบแม่นยำอาจช้าเกินไป Metaheuristics (เช่น Genetic Algorithms, Simulated Annealing) สามารถสร้างคำตอบที่ดีได้อย่างรวดเร็ว แต่ไม่มีการรับประกันความเป็นค่าเหมาะสมที่สุด MIP เป็นที่นิยมเมื่อการรับรองคุณภาพของคำตอบมีความสำคัญ
Optimality Gap คืออะไร และควรเล็กแค่ไหน?
ช่องว่างคือ (incumbent objective - LP bound) / LP bound ซึ่งแสดงเป็นเปอร์เซ็นต์ เป็นการรับรองว่าคำตอบจำนวนเต็มที่ดีที่สุดที่ทราบอยู่นั้นห่างจากค่าเหมาะสมที่สุดที่แท้จริงได้มากแค่ไหน สำหรับการใช้งานจริงส่วนใหญ่ ช่องว่าง 0.1–1% ก็เพียงพอแล้ว; ช่องว่างที่แคบลงต้องใช้เวลาของตัวแก้ปัญหาเพิ่มขึ้นแบบทวีคูณ
MIP สามารถจัดการกับฟังก์ชันวัตถุประสงค์หรือข้อจำกัดที่ไม่เป็นเชิงเส้นได้หรือไม่?
MIP มาตรฐานถือว่ามีความเป็นเชิงเส้น ความสัมพันธ์ที่ไม่เป็นเชิงเส้นจะต้องถูกทำให้เป็นเชิงเส้น (เช่น การประมาณค่าเชิงเส้นแบบเป็นช่วง, การขยายไบนารีของผลคูณ) หรือจัดการโดยตัวแก้ปัญหาการโปรแกรมจำนวนเต็มผสมไม่เชิงเส้น (MINLP) ซึ่งแก้ไขได้ยากกว่ามาก
แนะนำตัวแก้ปัญหาใดสำหรับ MIP?
เชิงพาณิชย์: Gurobi และ CPLEX เป็นมาตรฐานอุตสาหกรรม โอเพนซอร์ส: SCIP, CBC (ผ่าน COIN-OR) และ HiGHS มีความสามารถในการแข่งขันสำหรับปัญหาขนาดปานกลาง ทั้งหมดรองรับอินเทอร์เฟซการสร้างแบบจำลองมาตรฐาน เช่น AMPL, Pyomo และ JuMP
วิธีการที่เกี่ยวข้อง
แหล่งอ้างอิง
Nemhauser, G. L., Wolsey, L. A. (1988). Integer and Combinatorial Optimization. Wiley-Interscience, New York.
ISBN: 9780471359432คัดลอกแล้วWolsey, L. A. (1998). Integer Programming. Wiley-Interscience, New York.
ISBN: 9780471283669คัดลอกแล้ว