การโปรแกรมเชิงจำนวนเต็มผสมเชิงสุ่ม — การหาค่าเหมาะที่สุดภายใต้ความไม่แน่นอนด้วยการตัดสินใจแบบไม่ต่อเนื่องและต่อเนื่อง
- ผู้เสนอ
- Birge, J. R.; Louveaux, F.; Sen, S.
- ปี
- 1990s–2000s
- ประเภท
- Stochastic optimization model
- กลุ่มวิธี
- Simulation / optimization
ข้อความนี้เป็นการแปลด้วยเครื่องและยังไม่ได้รับการตรวจทาน อ่านต้นฉบับภาษาอังกฤษ
ใช้ทำอะไร?
การโปรแกรมเชิงจำนวนเต็มผสมเชิงสุ่ม (Stochastic Mixed-Integer Programming หรือ SMIP) เป็นกรอบการทำงานสำหรับการหาค่าเหมาะที่สุดที่ค้นหาการผสมผสานที่ดีที่สุดของการตัดสินใจแบบไบนารี จำนวนเต็ม และต่อเนื่อง เมื่อพารามิเตอร์หลัก เช่น ต้นทุน ความต้องการ และขีดความสามารถ ไม่แน่นอนและถูกจำลองเป็นฟังก์ชันการแจกแจงความน่าจะเป็นบนชุดของสถานการณ์จำลอง โดยเป็นการขยาย MIP แบบดั้งเดิมด้วยการฝังโครงสร้างต้นไม้สถานการณ์จำลอง (scenario trees) หรือวัตถุประสงค์แบบค่าคาดหวังที่ป้องกันความเสี่ยงจากความไม่แน่นอนในขณะที่ยังคงเคารพข้อจำกัดเชิงการจัดหมู่
แนวคิดเบื้องหลังวิธีการ
ปัญหาการวางแผนในโลกแห่งความเป็นจริงจำนวนมากจำเป็นต้องมีการเลือกแบบใช่/ไม่ใช่ หรือจำนวนเต็ม เช่น การสร้างโรงงานหรือไม่ การกำหนดจำนวนยานพาหนะที่เป็นจำนวนเต็ม แต่ในขณะเดียวกันอนาคตก็ยังคงไม่แน่นอน SMIP ทำให้ปัญหานี้เป็นทางการโดยการพิจารณาชุดของสถานการณ์จำลองในอนาคตที่เป็นไปได้ และเลือกการตัดสินใจในระยะแรก (ก่อนที่จะทราบความไม่แน่นอน) ที่ลดต้นทุนที่คาดหวัง หรือเพิ่มผลประโยชน์ที่คาดหวังในทุกสถานการณ์จำลอง ข้อจำกัดจำนวนเต็มทำให้ปัญหาเป็นเรื่องยากในเชิงการจัดหมู่ แต่ขั้นตอนวิธีแบบแยกส่วน (decomposition algorithms) ใช้ประโยชน์จากโครงสร้างสถานการณ์จำลองเพื่อทำให้ปัญหาขนาดใหญ่สามารถแก้ไขได้
ประวัติศาสตร์
การโปรแกรมเชิงสุ่มมีต้นกำเนิดมาจาก Dantzig (1955) และ Beale (1955) ในฐานะ LP สองขั้นตอน การขยายเชิงจำนวนเต็มผสมปรากฏเด่นชัดในช่วงทศวรรษ 1990 ด้วยการปรับวิธี L-shaped สำหรับการแก้ไขจำนวนเต็มโดย Laporte และ Louveaux (1993) และการนำเสนอที่ครอบคลุมในตำราของ Birge และ Louveaux ในปี 1997 ขั้นตอนวิธี C3/D2 ของ Sen และ Higle (2005) ได้พัฒนาโปรแกรมแก้ปัญหา SMIP ที่ปรับขนาดได้ ทำให้สาขาวิชานี้เป็นสาขาวิชาที่สมบูรณ์ภายในสาขาวิชาวิจัยดำเนินงาน
ควรใช้เมื่อใด
ใช้ SMIP เมื่อการตัดสินใจเกี่ยวข้องกับการเลือกแบบไม่ต่อเนื่องหรือไบนารี (ลงทุน/ไม่ลงทุน, จำนวนหน่วยที่จะเปิด) และพารามิเตอร์นำเข้าหลักมีความไม่แน่นอนอย่างแท้จริงพร้อมการแจกแจงความน่าจะเป็นที่สามารถวัดปริมาณได้ เหมาะอย่างยิ่งสำหรับการออกแบบเครือข่ายห่วงโซ่อุปทานภายใต้ความไม่แน่นอนของอุปสงค์, การขยายกำลังการผลิตพลังงาน, การวางแผนสิ่งอำนวยความสะดวกด้านสุขภาพ, และการจัดเตรียมล่วงหน้าเพื่อรับมือภัยพิบัติ ไม่ควรใช้เมื่อการตัดสินใจทั้งหมดเป็นแบบต่อเนื่อง (ใช้ stochastic LP แทน), เมื่อความไม่แน่นอนไม่สามารถวัดปริมาณได้อย่างมีความหมายในรูปของการแจกแจง, เมื่อจำนวนสถานการณ์จำลองที่จำเป็นในการแสดงความไม่แน่นอนนำไปสู่ขนาดแบบจำลองที่ไม่สามารถจัดการได้และไม่มีการแยกส่วน, หรือเมื่อฮิวริสติกส์ที่อิงการจำลองเพียงพอสำหรับคุณภาพการตัดสินใจที่ต้องการ
ข้อจำกัดและข้อควรพิจารณา
- ความซับซ้อนในการคำนวณเพิ่มขึ้นในเชิงการจัดหมู่ตามจำนวนสถานการณ์จำลองและตัวแปรจำนวนเต็ม; ปัญหาขนาดใหญ่อาจไม่สามารถจัดการได้หากไม่มีการแยกส่วนที่มีประสิทธิภาพ
- ต้องมีการแจกแจงความน่าจะเป็นหรือชุดสถานการณ์จำลองที่ชัดเจน — แบบจำลองความไม่แน่นอนที่ระบุผิดพลาดนำไปสู่ผลลัพธ์ที่มีประสิทธิภาพไม่ดีเมื่อนำไปใช้จริง
- การกำหนดรูปแบบสองขั้นตอนอาจทำให้การตัดสินใจหลายช่วงเวลาซับซ้อนน้อยเกินไป; SMIP แบบหลายขั้นตอนยากขึ้นอย่างมาก
- การแก้ไขจำนวนเต็มในระยะที่สองทำลายความเป็นนูนที่ใช้ประโยชน์จาก Benders cuts มาตรฐาน ซึ่งต้องใช้ integer L-shaped cuts เฉพาะทาง
เงื่อนไขจากแหล่งที่มาไม่สามารถใช้แทนการทบทวนทางวิทยาศาสตร์ที่เป็นอิสระหรือการตรวจสอบโดยเอนจินวิเคราะห์ได้
จุดแข็ง
- จัดการการตัดสินใจแบบไม่ต่อเนื่องเชิงการจัดหมู่ภายใต้ความไม่แน่นอนในแบบจำลองการหาค่าเหมาะที่สุดที่สอดคล้องกันเพียงแบบจำลองเดียว
- สร้างแผนระยะแรกที่ป้องกันความเสี่ยงซึ่งสร้างสมดุลระหว่างประสิทธิภาพที่คาดหวังในทุกสถานการณ์จำลอง
- ตัวชี้วัด VSS และ EVPI ให้เหตุผลที่โปร่งใสสำหรับคุณค่าของการสร้างแบบจำลองเชิงสุ่ม
- ขั้นตอนวิธีแบบแยกส่วน (L-shaped, progressive hedging) สามารถปรับขนาดได้สำหรับชุดสถานการณ์จำลองขนาดใหญ่
- ได้รับการสนับสนุนอย่างกว้างขวางในโปรแกรมแก้ปัญหาเชิงพาณิชย์ (CPLEX, Gurobi) และภาษาการสร้างแบบจำลอง (AMPL, Pyomo)
การประยุกต์ใช้
- การออกแบบเครือข่ายห่วงโซ่อุปทานที่มีความต้องการของลูกค้าที่ไม่แน่นอนและการตัดสินใจเลือกที่ตั้งโรงงานแบบไบนารี
- การวางแผนการขยายกำลังการผลิตไฟฟ้าภายใต้การผลิตพลังงานหมุนเวียนที่ไม่แน่นอนและการเติบโตของโหลด
- การจัดสรรทรัพยากรระบบสุขภาพ (จำนวนพนักงานที่เป็นจำนวนเต็ม, การเปิดคลินิกแบบไบนารี) ภายใต้ความไม่แน่นอนทางระบาดวิทยา
- การจัดเตรียมล่วงหน้าของเสบียงบรรเทาทุกข์แบบไม่ต่อเนื่องสำหรับโลจิสติกส์ด้านมนุษยธรรมก่อนสถานการณ์ภัยพิบัติ
- การหาค่าเหมาะที่สุดของพอร์ตการลงทุนทางการเงินที่มีต้นทุนการทำธุรกรรมและข้อจำกัดขนาดล็อตที่เป็นจำนวนเต็มภายใต้ความไม่แน่นอนของตลาด
- การจัดตารางการบินของลูกเรือภายใต้ความล่าช้าของเที่ยวบินที่ไม่แน่นอนด้วยตัวแปรการมอบหมายแบบไบนารี
วิธีการทำงาน
วิธีการทำงาน
ระบุตัวแปรการตัดสินใจ: การตัดสินใจในระยะแรก x ที่ทำขึ้นก่อนที่จะทราบความไม่แน่นอน (มีตัวแปรจำนวนเต็มและ/หรือไบนารีรวมอยู่ด้วย) และตัวแปรการแก้ไขในระยะที่สอง y(xi) ที่ทำขึ้นหลังจากสถานการณ์จำลอง xi เกิดขึ้นจริง ระบุสัมประสิทธิ์วัตถุประสงค์ เมทริกซ์ข้อจำกัด และการแจกแจงความน่าจะเป็น หรือชุดสถานการณ์จำลองแบบไม่ต่อเนื่องสำหรับพารามิเตอร์ที่ไม่แน่นอน
สร้างชุดสถานการณ์จำลองจำกัด {xi_1, ..., xi_S} ที่มีความน่าจะเป็นที่เกี่ยวข้อง {p_1, ..., p_S} ซึ่งประมาณการการแจกแจงพื้นฐาน สถานการณ์จำลองสามารถได้มาจากข้อมูลในอดีต การสอบถามผู้เชี่ยวชาญ การสุ่มตัวอย่างแบบ Latin hypercube หรือวิธีการจับคู่โมเมนต์ คุณภาพของสถานการณ์จำลองส่งผลโดยตรงต่อคุณภาพของผลลัพธ์
กำหนดรูปแบบสมมูลเชิงกำหนด: ลด c'x + sum_s p_s Q(x, xi_s) ภายใต้ข้อจำกัดระยะแรกและข้อจำกัดจำนวนเต็ม Q(x, xi_s) คือฟังก์ชันค่าระยะที่สอง — ต้นทุนที่เหมาะสมที่สุดของการดำเนินการแก้ไขที่กำหนด x และสถานการณ์จำลอง xi_s โปรแกรมรวมเป็น MIP ขนาดใหญ่ซึ่งขนาดจะเพิ่มขึ้นตามจำนวนสถานการณ์จำลอง
สูตร
\min_{x \in X} c^T x + \mathbb{E}_\xi[Q(x,\xi)] \quad \text{s.t. } Ax = b,\; x \in \mathbb{Z}^p \times \mathbb{R}^{n-p}แก้ไขโดยใช้ขั้นตอนวิธีแบบแยกส่วน — วิธี L-shaped (การแยกส่วนของ Benders) สำหรับระยะที่สองที่เป็นนูน, branch-and-cut ที่มีปัญหาย่อยสถานการณ์จำลอง, หรือ progressive hedging สำหรับการแยกส่วนแบบขนานสถานการณ์จำลอง ข้อจำกัดจำนวนเต็มในระยะที่สองต้องการ cuts เพิ่มเติม (integer L-shaped cuts, lift-and-project) โปรแกรมแก้ปัญหาที่ทันสมัย (CPLEX, Gurobi ที่มี callbacks, หรือไลบรารีเฉพาะ SMIP) ใช้รูทีนเหล่านี้
ประเมินผลลัพธ์ผ่านค่าของผลลัพธ์เชิงสุ่ม (Value of Stochastic Solution หรือ VSS = EEV - RP) และค่าคาดหวังของข้อมูลที่สมบูรณ์แบบ (Expected Value of Perfect Information หรือ EVPI = RP - WS) โดยที่ RP คือค่าที่เหมาะสมที่สุดของปัญหาการแก้ไข, EEV คือต้นทุนที่คาดหวังของการใช้ผลลัพธ์ค่าเฉลี่ยเชิงกำหนด, และ WS คือค่ารอและดู (wait-and-see value) ตัวชี้วัดเหล่านี้จะวัดประโยชน์ของการสร้างแบบจำลองความไม่แน่นอนอย่างชัดเจน
ข้อผิดพลาดที่พบบ่อย
- การใช้สถานการณ์จำลองน้อยเกินไปทำให้ความไม่แน่นอนถูกนำเสนอไม่เพียงพอ ส่งผลให้ได้ผลลัพธ์ที่มั่นใจเกินไป; มากเกินไปทำให้แบบจำลองไม่สามารถคำนวณได้
- การสับสนบทบาทของตัวแปรระยะแรกและระยะที่สองนำไปสู่การกำหนดรูปแบบที่ไม่เคารพเวลาของการเปิดเผยข้อมูล
- การพึ่งพาผลลัพธ์ค่าคาดหวัง (การละเลยความเป็นสุ่ม) อาจทำให้ได้ผลลัพธ์ที่ไม่เหมาะสมอย่างมาก — ควรคำนวณ VSS เสมอเพื่อยืนยันความพยายามในการใช้ SMIP
- การละเลยข้อจำกัดจำนวนเต็มในขั้นตอนการแก้ไขเมื่อมีอยู่จริงจะทำให้ได้ผลลัพธ์ที่ผ่อนปรนซึ่งอาจไม่สามารถนำไปใช้ได้จริง
- การตั้งค่าเริ่มต้นของโปรแกรมแก้ปัญหาสำหรับ MIP มักจะต้องมีการปรับแต่ง (ลำดับความสำคัญของการแตกกิ่ง, กลยุทธ์การตัด) ในกรอบการทำงานการแยกส่วนของ SMIP
คำถามที่พบบ่อย
SMIP แตกต่างจาก Mixed-Integer Programming ทั่วไปอย่างไร?
MIP ทั่วไปจะหาค่าเหมาะที่สุดภายใต้พารามิเตอร์ที่กำหนดและทราบแล้ว SMIP สร้างแบบจำลองพารามิเตอร์ที่ไม่แน่นอนอย่างชัดเจนเป็นชุดของสถานการณ์จำลองที่มีความน่าจะเป็น โดยหาค่าเหมาะที่สุดของประสิทธิภาพที่คาดหวังในทุกสถานการณ์จำลอง ในขณะที่รับประกันว่าการตัดสินใจในระยะแรกจะทำขึ้นก่อนที่จะทราบความไม่แน่นอน
ฉันต้องใช้สถานการณ์จำลองกี่สถานการณ์?
ไม่มีกฎสากลตายตัว สถานการณ์จำลองเพียง 10–50 สถานการณ์อาจเพียงพอสำหรับการตัดสินใจระยะแรกที่มั่นคงในบางปัญหา; ปัญหาอื่น ๆ อาจต้องใช้หลายพันสถานการณ์จำลอง เทคนิคการลดสถานการณ์จำลองและการทดสอบความเสถียร (การตรวจสอบว่าผลลัพธ์ที่เหมาะสมที่สุดไม่เปลี่ยนแปลงเมื่อคุณเพิ่มสถานการณ์จำลองมากขึ้น) ช่วยในการพิจารณาความเพียงพอ
วิธี L-shaped คืออะไร?
วิธี L-shaped คือการแยกส่วนของ Benders ที่ปรับใช้สำหรับโปรแกรมเชิงสุ่ม โดยจะแก้ปัญหา MIP หลักซ้ำ ๆ บนตัวแปรระยะแรกและปัญหาย่อยสถานการณ์จำลอง โดยเพิ่ม cuts ที่เหมาะสมที่สุดและความเป็นไปได้ให้กับปัญหาหลักจนกว่าจะบรรจบกัน สำหรับการแก้ไขจำนวนเต็ม integer L-shaped cuts จะมาแทนที่ Benders cuts มาตรฐาน
ฉันควรใช้ progressive hedging แทน L-shaped เมื่อใด?
Progressive hedging แยกส่วนตามสถานการณ์จำลองแทนที่จะเป็นโครงสร้างปัญหาย่อย ทำให้เหมาะสำหรับการประมวลผลแบบขนาน เป็นที่นิยมเมื่อมีสถานการณ์จำลองจำนวนมากและปัญหาย่อยมีขนาดใหญ่ และเมื่อขั้นตอนวิธีสามารถทำงานบนคลัสเตอร์ได้ โดยทั่วไป L-shaped เป็นที่นิยมสำหรับสถานการณ์จำลองที่มีจำนวนน้อยกว่าและมีโครงสร้างที่ดี
SMIP สามารถจัดการได้มากกว่าสองขั้นตอนหรือไม่?
ได้ แต่ SMIP แบบหลายขั้นตอนต้องใช้โครงสร้างต้นไม้สถานการณ์จำลองที่เติบโตแบบทวีคูณตามจำนวนขั้นตอน และการแยกส่วนจะซับซ้อนขึ้นอย่างมาก ในทางปฏิบัติ แบบจำลอง SMIP ที่นำไปใช้ส่วนใหญ่ใช้สองขั้นตอน โดยประมาณพลวัตหลายช่วงเวลาผ่าน rolling horizon หรือการรวมกลุ่ม
วิธีการที่เกี่ยวข้อง
แหล่งอ้างอิง
Birge, J. R., & Louveaux, F. (1997). Introduction to Stochastic Programming. Springer Series in Operations Research. New York: Springer.
ISBN: 9780387982175คัดลอกแล้วSen, S., & Higle, J. L. (2005). The C3 theorem and a D2 algorithm for large scale stochastic mixed-integer programming: Set convexification. Mathematical Programming, 104(1), 1–20.
เปิดเอกสารอ้างอิง DOIคัดลอกแล้ว