Skip to content
กลับไปยังผลการค้นหา

การโปรแกรมเชิงจำนวนเต็มผสมเชิงสุ่ม — การหาค่าเหมาะที่สุดภายใต้ความไม่แน่นอนด้วยการตัดสินใจแบบไม่ต่อเนื่องและต่อเนื่อง

ผู้เสนอ
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)

การประยุกต์ใช้

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

วิธีการทำงาน

วิธีการทำงาน

1

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

2

สร้างชุดสถานการณ์จำลองจำกัด {xi_1, ..., xi_S} ที่มีความน่าจะเป็นที่เกี่ยวข้อง {p_1, ..., p_S} ซึ่งประมาณการการแจกแจงพื้นฐาน สถานการณ์จำลองสามารถได้มาจากข้อมูลในอดีต การสอบถามผู้เชี่ยวชาญ การสุ่มตัวอย่างแบบ Latin hypercube หรือวิธีการจับคู่โมเมนต์ คุณภาพของสถานการณ์จำลองส่งผลโดยตรงต่อคุณภาพของผลลัพธ์

3

กำหนดรูปแบบสมมูลเชิงกำหนด: ลด 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}
4

แก้ไขโดยใช้ขั้นตอนวิธีแบบแยกส่วน — วิธี L-shaped (การแยกส่วนของ Benders) สำหรับระยะที่สองที่เป็นนูน, branch-and-cut ที่มีปัญหาย่อยสถานการณ์จำลอง, หรือ progressive hedging สำหรับการแยกส่วนแบบขนานสถานการณ์จำลอง ข้อจำกัดจำนวนเต็มในระยะที่สองต้องการ cuts เพิ่มเติม (integer L-shaped cuts, lift-and-project) โปรแกรมแก้ปัญหาที่ทันสมัย (CPLEX, Gurobi ที่มี callbacks, หรือไลบรารีเฉพาะ SMIP) ใช้รูทีนเหล่านี้

5

ประเมินผลลัพธ์ผ่านค่าของผลลัพธ์เชิงสุ่ม (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 หรือการรวมกลุ่ม

วิธีการที่เกี่ยวข้อง

แหล่งอ้างอิง

  1. Birge, J. R., & Louveaux, F. (1997). Introduction to Stochastic Programming. Springer Series in Operations Research. New York: Springer.

    ISBN: 9780387982175
    คัดลอกแล้ว
  2. 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
    คัดลอกแล้ว