การโปรแกรมจำนวนเต็มแบบสุ่ม — การหาค่าเหมาะสมที่สุดของการตัดสินใจแบบไม่ต่อเนื่องภายใต้ความไม่แน่นอน
- ผู้เสนอ
- Dantzig, G. B.; Beale, E. M. L.
- ปี
- 1955
- ประเภท
- Optimization under uncertainty with discrete decisions
- กลุ่มวิธี
- Simulation / optimization
ข้อความนี้เป็นการแปลด้วยเครื่องและยังไม่ได้รับการตรวจทาน อ่านต้นฉบับภาษาอังกฤษ
ใช้ทำอะไร?
การโปรแกรมจำนวนเต็มแบบสุ่ม (Stochastic Integer Programming - SIP) เป็นกรอบการหาค่าเหมาะสมที่สุดที่รวมตัวแปรตัดสินใจแบบจำนวนเต็ม (ไม่ต่อเนื่อง) เข้ากับการสร้างแบบจำลองความไม่แน่นอนเชิงความน่าจะเป็นอย่างชัดเจน โดยมีเป้าหมายเพื่อหาการตัดสินใจที่ดีที่สุดในปัจจุบัน (here-and-now decision) ที่ทำให้ต้นทุนคาดหวังต่ำที่สุด (หรือผลประโยชน์คาดหวังสูงสุด) ตลอดการกระจายของสถานการณ์ในอนาคต โดยคำนึงถึงข้อเท็จจริงที่ว่าการตัดสินใจบางอย่างต้องทำก่อนที่ความไม่แน่นอนจะคลี่คลาย
แนวคิดเบื้องหลังวิธีการ
การตัดสินใจจริงจำนวนมากมีความไม่ต่อเนื่อง (สร้างโรงงานหรือไม่สร้าง; มอบหมายพนักงานหรือไม่มอบหมาย) และไม่แน่นอน (อุปสงค์ ต้นทุน และข้อจำกัดไม่เป็นที่ทราบ ณ เวลาตัดสินใจ) SIP จัดการกับความท้าทายทั้งสองประการนี้พร้อมกัน โดยสร้างแบบจำลองอนาคตที่ไม่แน่นอนเป็นชุดของสถานการณ์ที่มีความน่าจะเป็นที่เกี่ยวข้อง จากนั้นจึงหาผลเฉลยจำนวนเต็มที่ให้ผลลัพธ์ดีที่สุดโดยเฉลี่ย — หรือที่ป้องกันความเสี่ยงต่อผลลัพธ์ที่แย่ที่สุด แตกต่างจากการโปรแกรมเชิงเส้นแบบสุ่ม โครงสร้างแบบไม่ต่อเนื่องทำให้ปัญหายากขึ้นในเชิงการจัดหมู่ (combinatorially harder) แต่การตัดสินใจที่ได้สามารถนำไปปฏิบัติได้โดยตรงโดยไม่ต้องปัดเศษหรือประมาณค่า
ประวัติศาสตร์
การโปรแกรมแบบสุ่มมีต้นกำเนิดมาจาก Dantzig (1955) และ Beale (1955) ซึ่งเสนอแบบจำลองการแก้ไขปัญหาแบบสองขั้นสำหรับโปรแกรมเชิงเส้นภายใต้ความไม่แน่นอนโดยอิสระ การขยายผลไปสู่การโปรแกรมจำนวนเต็มเกิดขึ้นเมื่อการโปรแกรมจำนวนเต็มมีความสมบูรณ์ในช่วงทศวรรษ 1960–1980 หนังสือเรียนของ Birge และ Louveaux ในปี 1997 ได้รวบรวมสาขาวิชานี้ และ Kleywegt และคณะ (2002) ได้กำหนด Sample Average Approximation ให้เป็นแนวทางคำนวณมาตรฐานสำหรับการหาค่าเหมาะสมที่สุดแบบไม่ต่อเนื่องขนาดใหญ่
ควรใช้เมื่อใด
ใช้การโปรแกรมจำนวนเต็มแบบสุ่มเมื่อการตัดสินใจนั้นไม่ต่อเนื่องโดยเนื้อแท้ (การเลือกแบบไบนารี การจัดสรรหน่วยเต็ม การกำหนดเส้นทาง) และพารามิเตอร์สำคัญไม่แน่นอน ณ เวลาตัดสินใจ เหมาะสำหรับ การวางแผนกำลังการผลิต การออกแบบเครือข่ายห่วงโซ่อุปทาน การจัดตารางการผลิตภายใต้ความไม่แน่นอนของอุปสงค์ การจัดส่งพลังงาน และการจัดสรรทรัพยากรที่มีผลผลิตแบบสุ่ม อย่าใช้เมื่อตัวแปรทั้งหมดเป็นแบบต่อเนื่อง (การโปรแกรมเชิงเส้นแบบสุ่มเพียงพอ) เมื่อความไม่แน่นอนน้อยมากหรือสังเกตได้ทั้งหมดก่อนตัดสินใจ เมื่อขนาดของปัญหาทำให้การแจงนับสถานการณ์ไม่สามารถคำนวณได้โดยปราศจากโครงสร้างพื้นฐานการแยกส่วน หรือเมื่อมีสถานการณ์ที่กำหนดเพียงสถานการณ์เดียวที่เกี่ยวข้อง
ข้อจำกัดและข้อควรพิจารณา
- ความซับซ้อนในการคำนวณเพิ่มขึ้นอย่างรวดเร็วตามจำนวนสถานการณ์และตัวแปรจำนวนเต็ม กรณีขนาดใหญ่เป็นปัญหา NP-hard
- การสร้างสถานการณ์ต้องใช้การกระจายความน่าจะเป็นที่น่าเชื่อถือ ซึ่งอาจเป็นเรื่องยากที่จะระบุหรือประมาณค่าจากข้อมูลที่มีจำกัด
- ส่วนขยายแบบหลายขั้น (มากกว่าสองขั้น) เผชิญกับการเติบโตแบบทวีคูณของแผนผังสถานการณ์ และแทบจะไม่สามารถแก้ปัญหาได้เกินกว่าสามขั้น
- ต้องใช้ทักษะในการสร้างแบบจำลองเพื่อระบุความเป็นไปได้ของการแก้ไขปัญหา ข้อจำกัดที่ไม่สามารถคาดการณ์ล่วงหน้า (non-anticipativity constraints) และโครงสร้างค่าปรับได้อย่างถูกต้อง
เงื่อนไขจากแหล่งที่มาไม่สามารถใช้แทนการทบทวนทางวิทยาศาสตร์ที่เป็นอิสระหรือการตรวจสอบโดยเอนจินวิเคราะห์ได้
จุดแข็ง
- สร้างแบบจำลองความไม่แน่นอนอย่างชัดเจน แทนที่จะใช้ค่าประมาณ ณ จุดเดียว (point estimates) ทำให้ได้ผลเฉลยที่ทนทานต่อสถานการณ์ที่เกิดขึ้นจริง
- จัดการกับการตัดสินใจแบบไม่ต่อเนื่องและแบบไบนารีโดยธรรมชาติ ดังนั้นผลเฉลยจึงสามารถนำไปปฏิบัติได้โดยตรงโดยไม่ต้องมีการปัดเศษหลังการคำนวณ
- กรอบการทำงานแบบสองขั้นแยกการตัดสินใจเชิงกลยุทธ์ขั้นแรกออกจากการดำเนินการแก้ไขปัญหาขั้นที่สองอย่างชัดเจน
- รองรับโครงสร้างการแก้ไขปัญหาที่หลากหลาย รวมถึงการจัดหาทรัพยากร ต้นทุนค่าปรับ และการจัดตารางการแก้ไขปัญหา
- ขอบเขตคุณภาพทางสถิติ (ผ่าน SAA) ช่วยให้ผู้ปฏิบัติงานสามารถรับรองความเป็นค่าเหมาะสมที่สุดโดยประมาณด้วยความเชื่อมั่นที่วัดปริมาณได้
การประยุกต์ใช้
- การออกแบบเครือข่ายห่วงโซ่อุปทานภายใต้อุปสงค์และเวลานำแบบสุ่ม
- การวางแผนขยายกำลังการผลิตไฟฟ้าด้วยผลผลิตพลังงานหมุนเวียนที่ไม่แน่นอน
- การจัดตารางห้องผ่าตัดในโรงพยาบาลภายใต้ระยะเวลาหัตถการที่แปรผัน
- การจัดตารางลูกเรือสายการบินด้วยความล่าช้าของเที่ยวบินแบบสุ่ม
- การจัดวางตำแหน่งโลจิสติกส์ด้านมนุษยธรรมของเวชภัณฑ์บรรเทาทุกข์ก่อนเกิดภัยพิบัติ
- การหาค่าเหมาะสมที่สุดของพอร์ตการลงทุนทางการเงินด้วยการเลือกสินทรัพย์แบบไม่ต่อเนื่องและผลตอบแทนตามสถานการณ์
วิธีการทำงาน
วิธีการทำงาน
สร้างแบบจำลองปัญหาขั้นแรก (first-stage problem): เลือกตัวแปรตัดสินใจแบบจำนวนเต็ม (หรือแบบผสมจำนวนเต็ม) x ก่อนที่จะเปิดเผยความไม่แน่นอน กำหนดวัตถุประสงค์ที่รวมทั้งต้นทุนทันทีและต้นทุนการแก้ไขปัญหา (recourse cost) ที่คาดหวังตลอดทุกสถานการณ์ ข้อจำกัดที่เชื่อมโยง x กับเงื่อนไขความเป็นไปได้จะถูกระบุไว้ที่นี่
สูตร
\min_{x \in \mathbb{Z}^n} c^T x + \mathbb{E}_\xi[Q(x, \xi)]แสดงความไม่แน่นอนผ่านชุดสถานการณ์ที่จำกัด แต่ละสถานการณ์กำหนดค่าเฉพาะให้กับพารามิเตอร์สุ่ม (ระดับอุปสงค์ ต้นทุน ความพร้อมของทรัพยากร) สถานการณ์สามารถสร้างขึ้นผ่านการสุ่มตัวอย่างจากข้อมูลในอดีต การสุ่มตัวอย่างแบบ Monte Carlo จากการกระจายที่ปรับค่า หรือกรณีที่เป็นตัวแทนที่กำหนดโดยผู้เชี่ยวชาญ แต่ละสถานการณ์มีน้ำหนักความน่าจะเป็นที่รวมกันได้เท่ากับหนึ่ง
ในสูตรแบบสองขั้น (two-stage formulation) มาตรฐาน หลังจากที่ x ถูกกำหนดค่าแล้วและสถานการณ์ xi เกิดขึ้น ปัญหาการแก้ไขปัญหา (recourse problem) ขั้นที่สองจะกำหนดการดำเนินการแก้ไข y ปัญหาการแก้ไขมักจะเป็นการโปรแกรมเชิงเส้นหรือการโปรแกรมจำนวนเต็ม แบบจำลองเต็มจะทำให้ต้นทุน c^T x บวกกับต้นทุนการแก้ไขปัญหาที่คาดหวัง E[Q(x, xi)] ต่ำที่สุด
สูตร
Q(x, \xi) = \min_{y \geq 0} q(\xi)^T y \;\text{ s.t. } W(\xi)y = h(\xi) - T(\xi)xแก้ปัญหาย่อยของสถานการณ์เพื่อประเมินต้นทุนการแก้ไขปัญหาสำหรับแต่ละสถานการณ์ที่กำหนด x เทคนิคที่ใช้ ได้แก่ branch-and-bound, Benders decomposition, Lagrangian relaxation และวิธี Sample Average Approximation (SAA) สำหรับแผนผังสถานการณ์ขนาดใหญ่ อัลกอริทึมการแยกส่วน (decomposition algorithms) ใช้ประโยชน์จากโครงสร้างแบบบล็อกข้ามสถานการณ์
รวบรวมผลลัพธ์จากปัญหาย่อยเพื่อประมาณต้นทุนการแก้ไขปัญหาที่คาดหวัง ใน SAA นี่คือค่าเฉลี่ยจาก S สถานการณ์ที่สุ่ม การประมาณค่าที่ได้จะลู่เข้าสู่ค่าคาดหวังที่แท้จริงเมื่อ S เพิ่มขึ้น สามารถคำนวณขอบเขตทางสถิติของคุณภาพผลเฉลยจากความแปรปรวนของตัวอย่างได้
สูตร
\mathbb{E}_\xi[Q(x,\xi)] \approx \frac{1}{S} \sum_{s=1}^{S} Q(x, \xi_s)ตรวจสอบความเป็นค่าเหมาะสมที่สุดหรือใกล้เคียงค่าเหมาะสมที่สุดผ่านช่องว่างค่าเหมาะสมที่สุด (optimality gaps) เกณฑ์การลู่เข้า หรือช่วงความเชื่อมั่นทางสถิติจาก SAA หากช่องว่างไม่เป็นที่ยอมรับ ให้ปรับปรุงชุดสถานการณ์ เพิ่มขนาดตัวอย่าง หรือกระชับการผ่อนคลาย (tighten relaxations) รายงานผลเฉลยขั้นแรก x* และต้นทุนรวมที่คาดหวัง
ข้อผิดพลาดที่พบบ่อย
- การใช้สถานการณ์น้อยเกินไปทำให้ได้ผลเฉลยที่มั่นใจเกินไป การใช้มากเกินไปทำให้ปัญหามีความซับซ้อนในการคำนวณไม่สามารถแก้ปัญหาได้ — สร้างสมดุลผ่านการวินิจฉัยการลู่เข้าของ SAA
- การละเลยความเป็นจำนวนเต็มในขั้นที่สองเมื่อจำเป็นจริง ๆ จะนำไปสู่การประมาณต้นทุนที่มองโลกในแง่ดีและการดำเนินการแก้ไขปัญหาที่ไม่สามารถทำได้
- การสมมติว่าสถานการณ์เป็นอิสระต่อกันเมื่อพารามิเตอร์มีความสัมพันธ์กัน (เช่น อุปสงค์และราคาที่สัมพันธ์กัน) จะนำไปสู่ความเอนเอียงที่เป็นระบบในการประมาณต้นทุนคาดหวัง
- การลืมข้อจำกัดที่ไม่สามารถคาดการณ์ล่วงหน้าในปัญหาหลายขั้นทำให้แบบจำลองสามารถใช้ประโยชน์จากข้อมูลในอนาคตที่จะไม่มีให้ในทางปฏิบัติ
คำถามที่พบบ่อย
การโปรแกรมจำนวนเต็มแบบสุ่มแตกต่างจากการหาค่าเหมาะสมที่สุดแบบทนทาน (robust optimization) อย่างไร?
SIP ทำให้ต้นทุนคาดหวังต่ำที่สุดในชุดสถานการณ์ที่มีน้ำหนักความน่าจะเป็น โดยยอมรับว่าบางสถานการณ์อาจมีต้นทุนสูงหากไม่น่าจะเป็นไปได้ การหาค่าเหมาะสมที่สุดแบบทนทานทำให้ต้นทุนที่แย่ที่สุดต่ำที่สุดในชุดความไม่แน่นอน โดยไม่มีข้อสมมติฐานเชิงความน่าจะเป็น SIP ต้องการการกระจายความน่าจะเป็น ในขณะที่การหาค่าเหมาะสมที่สุดแบบทนทานต้องการเพียงชุดความไม่แน่นอน โดยทั่วไป SIP จะอนุรักษ์น้อยกว่าแต่ต้องการข้อมูลมากกว่า
ต้องใช้สถานการณ์กี่สถานการณ์ในทางปฏิบัติ?
ขึ้นอยู่กับมิติของปัญหาและความแม่นยำที่ต้องการ แนวทาง Sample Average Approximation (SAA) ให้ช่วงความเชื่อมั่นทางสถิติเกี่ยวกับช่องว่างค่าเหมาะสมที่สุด การศึกษาประยุกต์ทั่วไปใช้สถานการณ์หลายสิบถึงหลายพันสถานการณ์ การวินิจฉัยการลู่เข้า (ความแปรปรวนของตัวประมาณค่าขอบเขต) จะนำทางการเลือก สำหรับปัญหาที่มีโครงสร้าง เทคนิคการลดจำนวนสถานการณ์ (เช่น Heitsch-Romisch) สามารถลดจำนวนสถานการณ์ลงได้อย่างมาก
การโปรแกรมจำนวนเต็มแบบสุ่มสามารถจัดการกับมากกว่าสองขั้นได้หรือไม่?
ได้ แต่ SIP แบบหลายขั้นนั้นยากกว่าอย่างมาก แผนผังสถานการณ์เติบโตแบบทวีคูณตามจำนวนขั้น และต้องบังคับใช้ข้อจำกัดที่ไม่สามารถคาดการณ์ล่วงหน้าได้ที่แต่ละโหนด ในทางปฏิบัติ แบบจำลองสามขั้นเป็นเรื่องปกติสำหรับการประยุกต์ที่แก้ปัญหาได้ เกินกว่านั้น มักจะต้องใช้การประมาณค่า เช่น rolling-horizon หรือการลดรูปแผนผังสถานการณ์
ซอฟต์แวร์ใดสามารถแก้แบบจำลองการโปรแกรมจำนวนเต็มแบบสุ่มได้?
ตัวแก้ทั่วไป ได้แก่ CPLEX และ Gurobi (ผ่านภาษาแบบจำลองเชิงพีชคณิต เช่น AMPL, JuMP ใน Julia หรือ PuLP/Pyomo ใน Python) ซึ่งรองรับการแยกส่วนสถานการณ์ กรอบการทำงานการโปรแกรมแบบสุ่มเฉพาะทาง ได้แก่ PySP (Python), ตัวแก้รูปแบบ SMPS และแพ็กเกจ Julia StochasticPrograms.jl ซึ่งใช้ SAA และ progressive hedging
การโปรแกรมจำนวนเต็มแบบสุ่มเหมือนกับการโปรแกรมจำนวนเต็มผสมแบบสุ่ม (Stochastic Mixed-Integer Programming) หรือไม่?
การโปรแกรมจำนวนเต็มแบบสุ่มเป็นกลุ่มที่กว้างกว่า การโปรแกรมจำนวนเต็มผสมแบบสุ่ม (SMIP) หมายถึงแบบจำลองที่ตัวแปรบางตัวเป็นแบบต่อเนื่องและตัวแปรอื่น ๆ เป็นแบบจำนวนเต็มในขั้นใดขั้นหนึ่งหรือทั้งสองขั้น SMIP เป็นรูปแบบที่ทั่วไปที่สุดและพบได้บ่อยที่สุดในทางปฏิบัติ
วิธีการที่เกี่ยวข้อง
แหล่งอ้างอิง
Birge, J. R., & Louveaux, F. (1997). Introduction to Stochastic Programming. Springer, New York.
ISBN: 978-1-4614-0237-4คัดลอกแล้วKleywegt, A. J., Shapiro, A., & Homem-de-Mello, T. (2002). The sample average approximation method for stochastic discrete optimization. SIAM Journal on Optimization, 12(2), 479-502.
เปิดเอกสารอ้างอิง DOIคัดลอกแล้ว