Robust Mixed-Integer Programming — การหาค่าเหมาะสมที่สุดด้วยตัวแปรจำนวนเต็มภายใต้ความไม่แน่นอน
- ผู้เสนอ
- Ben-Tal & Nemirovski; Bertsimas & Sim
- ปี
- 1998–2004
- ประเภท
- Deterministic robust reformulation of MIP under uncertainty
- กลุ่มวิธี
- Simulation / optimization
ข้อความนี้เป็นการแปลด้วยเครื่องและยังไม่ได้รับการตรวจทาน อ่านต้นฉบับภาษาอังกฤษ
ใช้ทำอะไร?
Robust Mixed-Integer Programming (RMIP) เป็นการผสมผสานระหว่าง mixed-integer programming กับ robust optimization เพื่อหาคำตอบที่ยังคงความเป็นไปได้และใกล้เคียงค่าเหมาะสมที่สุด แม้ว่าพารามิเตอร์จะมีความไม่แน่นอน แทนที่จะสมมติว่าข้อมูลคงที่ RMIP จะปกป้องการตัดสินใจจากการรับรู้ในกรณีที่เลวร้ายที่สุดหรือจากผู้โจมตีของอินพุตที่ไม่แน่นอน โดยใช้ชุดความไม่แน่นอนที่ชัดเจนเพื่อควบคุมระดับของการระมัดระวัง ในขณะที่ยังคงโครงสร้างแบบผสมของตัวแปรตัดสินใจที่เป็นจำนวนเต็ม
แนวคิดเบื้องหลังวิธีการ
โปรแกรม mixed-integer แบบดั้งเดิมสมมติว่าข้อมูลทั้งหมดทราบอย่างแม่นยำ แต่ในทางปฏิบัติ ต้นทุน ความต้องการ และเวลาในการประมวลผลมีความผันผวน RMIP ถามว่า: การตัดสินใจที่เป็นจำนวนเต็มและต่อเนื่องแบบใดดีที่สุด หากพารามิเตอร์ที่ไม่แน่นอนมีค่าที่เป็นไปได้เลวร้ายที่สุดภายในช่วงที่กำหนด? โดยการฝังความไม่แน่นอนลงในแบบจำลองการหาค่าเหมาะสมที่สุดโดยตรง RMIP จะสร้างแผนที่ได้รับการป้องกันจากการเปลี่ยนแปลงของข้อมูลโดยไม่ต้องใช้วิธีการจำลองสถานการณ์แบบหลายความน่าจะเป็น แนวทางงบประมาณความไม่แน่นอน (budget-of-uncertainty) ของ Bertsimas-Sim ช่วยให้นักปฏิบัติสามารถปรับเปลี่ยนระหว่างความทนทานเต็มที่กับประสิทธิภาพในกรณีเฉลี่ย ทำให้การแลกเปลี่ยนระหว่างการป้องกันและต้นทุนมีความชัดเจน
ประวัติศาสตร์
Robust optimization ในฐานะกระบวนทัศน์ที่สามารถจัดการได้ถูกก่อตั้งขึ้นโดย Ben-Tal และ Nemirovski ในช่วงปลายทศวรรษ 1990 สำหรับปัญหาต่อเนื่อง Bertsimas และ Sim (2004) ได้ขยายแนวคิดนี้ไปยัง linear programs ด้วยชุดงบประมาณความไม่แน่นอนที่รักษาความสามารถในการจัดการแบบเชิงเส้น งานวิจัยต่อมาได้รวมกรอบการทำงานนี้เข้ากับ integer programming ทำให้เกิด RMIP ซึ่งได้รับการยอมรับอย่างกว้างขวางในการวิจัยด้านอุปทาน พลังงาน และการขนส่งในช่วงทศวรรษ 2010
ควรใช้เมื่อใด
ขั้นตอนที่ 6 — การใช้งาน RMIP เมื่อการตัดสินใจเกี่ยวข้องกับการเลือกแบบจำนวนเต็มหรือไบนารี (การจัดตำแหน่งสถานที่, การกำหนดขนาดล็อต, การออกแบบเครือข่าย, การจัดตารางเวลา) และพารามิเตอร์อินพุตบางอย่างไม่แน่นอน แต่ไม่สามารถหาการแจกแจงความน่าจะเป็นได้ หรือไม่น่าเชื่อถือ เหมาะสมเมื่อการละเมิดข้อจำกัดเป็นสิ่งที่ยอมรับไม่ได้ (ข้อกำหนดความเป็นไปได้ที่เข้มงวด) และต้องการการรับประกันแบบกำหนดที่ระมัดระวัง แทนที่จะเป็นการหาค่าเหมาะสมที่สุดโดยคาดหวังค่าเฉลี่ย *ไม่ควร* ใช้เมื่อการแจกแจงความไม่แน่นอนมีลักษณะที่ชัดเจนและสามารถใช้วิธีการ sample-average approximation หรือ stochastic MIP ได้; เมื่อตัวแปรตัดสินใจทั้งหมดเป็นแบบต่อเนื่อง (ใช้ robust LP แทน); หรือเมื่อชุดความไม่แน่นอนมีขนาดใหญ่มากจนแบบจำลองไม่สามารถจัดการได้หากไม่มีกลยุทธ์การแยกส่วน
ข้อจำกัดและข้อควรพิจารณา
- มีความระมัดระวังโดยเนื้อแท้ — วัตถุประสงค์ในกรณีเลวร้ายที่สุดมักจะแย่กว่าวัตถุประสงค์ที่คาดหวังของ stochastic programming
- การเลือกชุดความไม่แน่นอนที่เหมาะสมต้องอาศัยความรู้เฉพาะทาง; ชุดที่เลือกไม่ถูกต้องจะนำไปสู่การป้องกันมากเกินไปหรือน้อยเกินไป
- การปรับรูปแบบที่ทนทานสามารถเพิ่มขนาดแบบจำลองได้อย่างมาก (ตัวแปรและข้อจำกัดเพิ่มเติม) เพิ่มภาระการคำนวณสำหรับกรณีขนาดใหญ่
- ไม่ให้ข้อมูลเกี่ยวกับความน่าจะเป็นของประสิทธิภาพของคำตอบ; stochastic MIP เหมาะสมกว่าเมื่อต้องการการวัดความเสี่ยงเชิงความน่าจะเป็น
เงื่อนไขจากแหล่งที่มาไม่สามารถใช้แทนการทบทวนทางวิทยาศาสตร์ที่เป็นอิสระหรือการตรวจสอบโดยเอนจินวิเคราะห์ได้
จุดแข็ง
- ให้การรับประกันความเป็นไปได้ในกรณีเลวร้ายที่สุดแบบกำหนด โดยไม่ต้องใช้การแจกแจงความน่าจะเป็นสำหรับพารามิเตอร์ที่ไม่แน่นอน
- พารามิเตอร์งบประมาณความไม่แน่นอน (Gamma) ให้การควบคุมที่เข้าใจง่ายและปรับได้สำหรับการแลกเปลี่ยนระหว่างความทนทานและค่าเหมาะสมที่สุด
- การปรับรูปแบบยังคงโครงสร้าง MIP ไว้ ทำให้สามารถใช้ตัวแก้ปัญหาเชิงพาณิชย์ที่มีอยู่และเทคโนโลยี branch-and-cut ได้
- สามารถนำไปใช้กับปัญหาเชิงการจัด (combinatorial problems) ที่เข้มงวด เช่น การออกแบบเครือข่าย การจัดตำแหน่งสถานที่ และการจัดตารางการผลิต
- มีความสามารถในการคำนวณได้มากกว่า stochastic MIP ที่มีหลายสถานการณ์
การประยุกต์ใช้
- การออกแบบเครือข่ายห่วงโซ่อุปทานภายใต้ความไม่แน่นอนของอุปสงค์และระยะเวลารอคอย
- การวางแผนขยายกำลังการผลิตระบบพลังงานด้วยการผลิตพลังงานหมุนเวียนที่ไม่แน่นอน
- การจัดตำแหน่งสถานพยาบาลภายใต้ความไม่แน่นอนของอุปสงค์ผู้ป่วย
- การจัดตารางลูกเรือสายการบินด้วยความล่าช้าของเที่ยวบินที่ไม่แน่นอน
- การกำหนดขนาดล็อตการผลิตภายใต้ความไม่แน่นอนของต้นทุนและเวลาในการประมวลผล
- การกำหนดเส้นทางการจัดเส้นทางเครือข่ายโทรคมนาคมด้วยปริมาณการรับส่งข้อมูลที่ไม่แน่นอน
วิธีการทำงาน
วิธีการทำงาน
ขั้นตอนที่ 1 — การกำหนดรูปแบบ MIP แบบปกติ: ระบุตัวแปรตัดสินใจ (ไบนารีหรือจำนวนเต็ม y, ต่อเนื่อง x), ฟังก์ชันวัตถุประสงค์ และข้อจำกัด ระบุพารามิเตอร์ (สัมประสิทธิ์ต้นทุน, ค่าด้านขวา, รายการเมทริกซ์เทคโนโลยี) ที่ไม่แน่นอนและต้องได้รับการปกป้อง
ขั้นตอนที่ 2 — การกำหนดชุดความไม่แน่นอน U สำหรับพารามิเตอร์ที่ไม่แน่นอน ตัวเลือกทั่วไป ได้แก่ เซตกล่อง (ช่วงของแต่ละพารามิเตอร์), เซตวงรี (ความไม่แน่นอนที่สัมพันธ์กัน), หรือเซตงบประมาณ Bertsimas-Sim (พารามิเตอร์อย่างมากที่สุด Gamma ตัวแปรเบี่ยงเบนพร้อมกัน) โดยที่ Gamma ควบคุมระดับความระมัดระวัง
ขั้นตอนที่ 3 — การแทนที่ข้อจำกัดที่ไม่แน่นอนแต่ละรายการด้วยคู่ที่ทนทาน (robust counterpart) ซึ่งต้องเป็นจริงสำหรับทุกการรับรู้ใน U สำหรับความไม่แน่นอนของงบประมาณ จะได้การปรับรูปแบบที่สามารถจัดการได้: ข้อจำกัดเดิมจะถูกเสริมด้วยพจน์ลงโทษที่ควบคุมผลรวมของการเบี่ยงเบนในกรณีที่เลวร้ายที่สุด ผลลัพธ์คือแบบจำลองที่ใหญ่ขึ้นแต่ยังคงสามารถจัดการได้ด้วย MIP
ขั้นตอนที่ 4 — การแก้ปัญหา RMIP ที่ปรับรูปแบบแล้วด้วยตัวแก้ปัญหาแบบ branch-and-bound หรือ branch-and-cut มาตรฐาน (เช่น CPLEX, Gurobi, SCIP) การปรับรูปแบบยังคงรักษาข้อกำหนดความเป็นจำนวนเต็มบน y สำหรับกรณีขนาดใหญ่ วิธีการแยกส่วนแบบ Benders decomposition หรือ cutting-plane สามารถแยกปัญหาได้
ขั้นตอนที่ 5 — การประเมินผลลัพธ์ที่ทนทานโดย: (a) การคำนวณค่าวัตถุประสงค์ภายใต้พารามิเตอร์ปกติและกรณีเลวร้ายที่สุด (b) การเปรียบเทียบกับผลลัพธ์ stochastic programming โดยใช้การจำลองแบบ Monte Carlo และ (c) การรายงานราคาของความทนทาน (price of robustness) — ต้นทุนเพิ่มเติมที่จ่ายไปเพื่อการป้องกันความไม่แน่นอน
ข้อผิดพลาดที่พบบ่อย
- การเลือก Gamma=0 (ไม่มีงบประมาณความไม่แน่นอน) จะให้ผลลัพธ์เหมือนกับ MIP ปกติและไม่ให้การป้องกันใดๆ; Gamma ที่ใหญ่เกินไปจะนำไปสู่คำตอบที่ระมัดระวังเกินไปและไม่สามารถนำไปปฏิบัติได้จริง
- การพิจารณาพารามิเตอร์ทั้งหมดว่าไม่แน่นอนพร้อมกันอาจทำให้การปรับรูปแบบไม่สามารถจัดการได้ — ระบุพารามิเตอร์ที่ไม่แน่นอนที่สำคัญเพื่อปกป้องอย่างเลือกสรร
- การละเลยโครงสร้างความสัมพันธ์ของความไม่แน่นอนอาจส่งผลให้ชุดความไม่แน่นอนที่มองโลกในแง่ร้ายเกินไป; เซตวงรีจะเหมาะสมกว่าเมื่อทราบความสัมพันธ์
- การรายงานเฉพาะวัตถุประสงค์ในกรณีเลวร้ายที่สุดโดยไม่เปรียบเทียบกับค่าปกติหรือค่าอ้างอิงแบบสุ่ม จะให้ภาพคุณภาพของคำตอบที่ไม่สมบูรณ์
คำถามที่พบบ่อย
RMIP แตกต่างจาก stochastic mixed-integer programming อย่างไร?
Stochastic MIP ใช้การแจกแจงความน่าจะเป็นและหาค่าเหมาะสมที่สุดของประสิทธิภาพโดยเฉลี่ยจากสถานการณ์ที่สุ่มตัวอย่าง ในขณะที่ RMIP ป้องกันกรณีที่เลวร้ายที่สุดภายในชุดความไม่แน่นอนโดยไม่ต้องใช้ข้อมูลการแจกแจง RMIP ให้คำตอบแบบกำหนดที่ทนทานเพียงคำตอบเดียว; stochastic MIP ให้ นโยบาย ที่ดีโดยเฉลี่ย
อะไรคือ 'ราคาของความทนทาน' และโดยทั่วไปมีขนาดเท่าใด?
ราคาของความทนทานคือเปอร์เซ็นต์การเพิ่มขึ้นของค่าวัตถุประสงค์เมื่อเทียบกับค่าเหมาะสมที่สุดปกติ (ไม่มีความไม่แน่นอน) Bertsimas และ Sim แสดงให้เห็นว่ามันเพิ่มขึ้นเป็นสัดส่วนโดยตรงกับ Gamma แต่ยังคงไม่มากนักสำหรับค่าแกมมาทั่วไป บ่อยครั้งอยู่ที่ 5–15% ในการใช้งานจริง
RMIP สามารถจัดการกับค่าด้านขวาที่ไม่แน่นอนได้เช่นเดียวกับสัมประสิทธิ์ต้นทุนที่ไม่แน่นอนหรือไม่?
ใช่ ความไม่แน่นอนในค่าด้านขวาของข้อจำกัดนำไปสู่ข้อจำกัดความเป็นไปได้ที่ทนทาน ในขณะที่ความไม่แน่นอนในสัมประสิทธิ์วัตถุประสงค์ส่งผลต่อความเป็นค่าเหมาะสมที่สุดที่ทนทาน ทั้งสองสามารถจัดการได้พร้อมกันภายในกรอบงบประมาณความไม่แน่นอน แม้ว่าโครงสร้างการปรับรูปแบบจะแตกต่างกัน
RMIP สามารถแก้ปัญหาได้ด้วยตัวแก้ปัญหา MIP มาตรฐานหรือไม่?
สำหรับชุดงบประมาณ Bertsimas-Sim การปรับรูปแบบที่ทนทานยังคงเป็น MIP และสามารถแก้ปัญหาได้โดยตรงด้วยตัวแก้ปัญหาเช่น CPLEX หรือ Gurobi ชุดความไม่แน่นอนแบบวงรีจะสร้าง mixed-integer second-order cone programs (MISOCP) ซึ่งได้รับการสนับสนุนโดยตัวแก้ปัญหาที่ทันสมัยเช่นกัน
เมื่อใดที่ควรเลือกชุดความไม่แน่นอนแบบกล่อง (box uncertainty set) แทนชุดงบประมาณความไม่แน่นอน (budget-of-uncertainty set)?
ชุดกล่องป้องกันทุกพารามิเตอร์ที่เบี่ยงเบนพร้อมกันไปยังค่าสุดขั้ว ซึ่งมักจะระมัดระวังเกินไป ชุดงบประมาณ (Gamma) จะเหมาะสมกว่าเมื่อการเบี่ยงเบนในกรณีเลวร้ายที่สุดพร้อมกันของทุกพารามิเตอร์ไม่น่าเป็นไปได้ เนื่องจากให้ผลลัพธ์ที่ระมัดระวังน้อยกว่าและคุ้มค่ากว่า
วิธีการที่เกี่ยวข้อง
แหล่งอ้างอิง
Bertsimas, D., Sim, M. (2004). The price of robustness. Operations Research, 52(1), 35–53.
เปิดเอกสารอ้างอิง DOIคัดลอกแล้วBen-Tal, A., El Ghaoui, L., Nemirovski, A. (2009). Robust Optimization. Princeton University Press, Princeton, NJ.
ISBN: 9780691143682คัดลอกแล้ว