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

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

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

2

ขั้นตอนที่ 2 — การกำหนดชุดความไม่แน่นอน U สำหรับพารามิเตอร์ที่ไม่แน่นอน ตัวเลือกทั่วไป ได้แก่ เซตกล่อง (ช่วงของแต่ละพารามิเตอร์), เซตวงรี (ความไม่แน่นอนที่สัมพันธ์กัน), หรือเซตงบประมาณ Bertsimas-Sim (พารามิเตอร์อย่างมากที่สุด Gamma ตัวแปรเบี่ยงเบนพร้อมกัน) โดยที่ Gamma ควบคุมระดับความระมัดระวัง

3

ขั้นตอนที่ 3 — การแทนที่ข้อจำกัดที่ไม่แน่นอนแต่ละรายการด้วยคู่ที่ทนทาน (robust counterpart) ซึ่งต้องเป็นจริงสำหรับทุกการรับรู้ใน U สำหรับความไม่แน่นอนของงบประมาณ จะได้การปรับรูปแบบที่สามารถจัดการได้: ข้อจำกัดเดิมจะถูกเสริมด้วยพจน์ลงโทษที่ควบคุมผลรวมของการเบี่ยงเบนในกรณีที่เลวร้ายที่สุด ผลลัพธ์คือแบบจำลองที่ใหญ่ขึ้นแต่ยังคงสามารถจัดการได้ด้วย MIP

4

ขั้นตอนที่ 4 — การแก้ปัญหา RMIP ที่ปรับรูปแบบแล้วด้วยตัวแก้ปัญหาแบบ branch-and-bound หรือ branch-and-cut มาตรฐาน (เช่น CPLEX, Gurobi, SCIP) การปรับรูปแบบยังคงรักษาข้อกำหนดความเป็นจำนวนเต็มบน y สำหรับกรณีขนาดใหญ่ วิธีการแยกส่วนแบบ Benders decomposition หรือ cutting-plane สามารถแยกปัญหาได้

5

ขั้นตอนที่ 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) จะเหมาะสมกว่าเมื่อการเบี่ยงเบนในกรณีเลวร้ายที่สุดพร้อมกันของทุกพารามิเตอร์ไม่น่าเป็นไปได้ เนื่องจากให้ผลลัพธ์ที่ระมัดระวังน้อยกว่าและคุ้มค่ากว่า

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

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

  1. Bertsimas, D., Sim, M. (2004). The price of robustness. Operations Research, 52(1), 35–53.

    เปิดเอกสารอ้างอิง DOI
    คัดลอกแล้ว
  2. Ben-Tal, A., El Ghaoui, L., Nemirovski, A. (2009). Robust Optimization. Princeton University Press, Princeton, NJ.

    ISBN: 9780691143682
    คัดลอกแล้ว