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

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

ผู้เสนอ
Ben-Tal, A. and Nemirovski, A.; further developed by Bertsimas, D. and Sim, M.
ปี
1999–2004
ประเภท
Uncertainty-robust linear optimization
กลุ่มวิธี
Simulation / optimization

ข้อความนี้เป็นการแปลด้วยเครื่องและยังไม่ได้รับการตรวจทาน อ่านต้นฉบับภาษาอังกฤษ

ขนาดตัวอักษร

ใช้ทำอะไร?

การโปรแกรมเชิงเส้นแบบทนทาน (Robust Linear Programming - RLP) เป็นการขยายการโปรแกรมเชิงเส้นแบบดั้งเดิมเพื่อจัดการกับความไม่แน่นอนในข้อมูลของปัญหา — สัมประสิทธิ์ต้นทุน, สัมประสิทธิ์ข้อจำกัด, หรือค่าทางขวามือ — โดยกำหนดให้ผลลัพธ์ยังคงมีความเป็นไปได้และใกล้เคียงค่าเหมาะสมที่สุดตลอดทุกการเกิดขึ้นของพารามิเตอร์ที่ไม่แน่นอนภายในชุดความไม่แน่นอนที่กำหนด RLP ใช้การรับประกันกรณีที่เลวร้ายที่สุด (worst-case guarantees) แทนข้อสมมติฐานเชิงความน่าจะเป็น ทำให้มีประโยชน์เมื่อความรู้เกี่ยวกับลักษณะการกระจายตัวมีจำกัด

แนวคิดเบื้องหลังวิธีการ

การโปรแกรมเชิงเส้นแบบธรรมดาจะหาผลลัพธ์ที่ดีที่สุดโดยสมมติว่าข้อมูลทั้งหมดเป็นที่ทราบแน่ชัด ในทางปฏิบัติ สัมประสิทธิ์ต่างๆ จะถูกประมาณค่า คาดการณ์ หรือวัดด้วยข้อผิดพลาด RLP จะถามว่า: การตัดสินใจที่ดีที่สุดคืออะไรที่จะยังคงมีความเป็นไปได้ไม่ว่าพารามิเตอร์ที่ไม่แน่นอนจะเปลี่ยนแปลงไปอย่างไรในช่วงที่สมเหตุสมผล? นักวิเคราะห์จะระบุชุดความไม่แน่นอน — เช่น กล่อง (box), ทรงรี (ellipsoid), หรือบริเวณโพลีฮีดรา (polyhedral region) — และตัวแก้ปัญหาจะหาแผนการที่เหมาะสมที่สุดสำหรับกรณีที่เลวร้ายที่สุดภายในชุดนั้น การกำหนดรูปแบบงบประมาณของความไม่แน่นอน (budget-of-uncertainty formulation) ของ Bertsimas และ Sim ช่วยให้นักวิเคราะห์สามารถปรับระดับการระมัดระวังได้: พารามิเตอร์ Gamma จะควบคุมจำนวนสัมประสิทธิ์ที่สามารถเปลี่ยนแปลงค่าพร้อมกันได้ โดยเป็นการประมาณค่าระหว่าง LP แบบปกติ (nominal LP) และกรณีที่เลวร้ายที่สุดแบบระมัดระวังเต็มที่

ประวัติศาสตร์

การหาค่าเหมาะสมที่สุดแบบทนทาน (Robust optimization) ได้รับการวางรากฐานทางทฤษฎีที่มั่นคงโดย Ben-Tal และ Nemirovski (1999) ซึ่งแสดงให้เห็นว่าโปรแกรมเชิงเส้นที่ไม่แน่นอนที่มีชุดความไม่แน่นอนแบบทรงรีสามารถแปลงเป็นโปรแกรมเชิงลำดับที่สอง (second-order cone programs) ที่สามารถจัดการได้ Bertsimas และ Sim (2004) ได้นำเสนอแนวคิดเรื่องงบประมาณของความไม่แน่นอน (budget-of-uncertainty) ซึ่งทำให้การแปลงรูปแบบยังคงเป็นโปรแกรมเชิงเส้นและสามารถปรับระดับความทนทานได้ผ่านพารามิเตอร์เดียว ซึ่งช่วยขยายการนำไปใช้ในทางปฏิบัติในสาขาวิจัยดำเนินงานและวิศวกรรมอย่างมาก

ควรใช้เมื่อใด

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

ข้อจำกัดและข้อควรพิจารณา

  • การมุ่งเน้นที่กรณีที่เลวร้ายที่สุดอาจให้ผลลัพธ์ที่ระมัดระวังเกินไปเมื่อสถานการณ์สุดขั้วมีโอกาสเกิดขึ้นน้อยมาก
  • ชุดความไม่แน่นอนแบบทรงรี (Ellipsoidal uncertainty sets) ทำให้เกิดโปรแกรมเชิงลำดับที่สอง (second-order cone programs) ที่สามารถจัดการได้ แต่ไม่ใช่ LP บริสุทธิ์ ทำให้ต้องการตัวแก้ปัญหาที่ซับซ้อนขึ้น
  • กำหนดให้นักวิเคราะห์ต้องระบุชุดความไม่แน่นอน ซึ่งเป็นทางเลือกในการสร้างแบบจำลองที่ส่งผลกระทบอย่างมีนัยสำคัญต่อผลลัพธ์
  • ไม่ได้ให้การระบุความน่าจะเป็นของการละเมิดโดยตรง; stochastic programming จะเหมาะสมกว่าหากความน่าจะเป็นหาง (tail probabilities) มีความสำคัญ
  • จะลดรูปกลายเป็น LP แบบปกติเมื่อ Gamma = 0 ซึ่งไม่ให้การป้องกันความไม่แน่นอนใดๆ

เงื่อนไขจากแหล่งที่มาไม่สามารถใช้แทนการทบทวนทางวิทยาศาสตร์ที่เป็นอิสระหรือการตรวจสอบโดยเอนจินวิเคราะห์ได้

จุดแข็ง

  • ให้การรับประกันความเป็นไปได้ในกรณีที่เลวร้ายที่สุดโดยไม่ต้องอาศัยข้อสมมติฐานเกี่ยวกับการแจกแจง
  • การกำหนดรูปแบบงบประมาณของความไม่แน่นอน (budget-of-uncertainty) ของ Bertsimas-Sim สร้างคู่ LP ที่สามารถจัดการได้ ซึ่งสามารถแก้ได้ด้วยตัวแก้ปัญหาที่มีอยู่ทั่วไป
  • พารามิเตอร์งบประมาณความทนทาน Gamma ช่วยให้นักวิเคราะห์สามารถปรับเปลี่ยนคุณภาพของผลลัพธ์กับการระมัดระวังได้อย่างเข้าใจง่าย
  • มีประสิทธิภาพในการคำนวณ — คู่ที่ทนทานสำหรับชุดความไม่แน่นอนแบบงบประมาณมีความซับซ้อนใกล้เคียงกับ LP เดิม
  • เหมาะสมอย่างยิ่งสำหรับปัญหาที่การละเมิดข้อจำกัดมีค่าใช้จ่ายสูงหรือเป็นอันตราย

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

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

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

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

1

กำหนดรูปแบบการโปรแกรมเชิงเส้นแบบปกติ (nominal linear program): หาค่าต่ำสุดของฟังก์ชันวัตถุประสงค์เชิงเส้น c^T x ภายใต้ข้อจำกัดอสมการเชิงเส้น Ax <= b และเงื่อนไขไม่เป็นลบ ระบุว่าสัมประสิทธิ์ใด — โดยทั่วไปคือสมาชิกของเมทริกซ์ข้อจำกัด a_ij — เป็นค่าที่ไม่แน่นอน ขั้นตอนนี้จะเหมือนกับการสร้างแบบจำลอง LP มาตรฐาน แต่จะมีการระบุพารามิเตอร์ที่ไม่แน่นอนแต่ละตัว

สูตร
\min c^T x \text{ s.t. } Ax \leq b, \; x \geq 0
2

สร้างชุดความไม่แน่นอน U ที่ครอบคลุมช่วงค่าที่เป็นไปได้ของพารามิเตอร์โดยไม่ต้องใช้การแจกแจงความน่าจะเป็น ตัวเลือกทั่วไป ได้แก่ ชุดแบบกล่อง (box sets) (แต่ละพารามิเตอร์เปลี่ยนแปลงอย่างอิสระในช่วง [a_bar - a_hat, a_bar + a_hat]), ชุดแบบทรงรี (ellipsoidal sets) (Ben-Tal and Nemirovski, 1999), และชุดแบบงบประมาณ (budget sets) (Bertsimas and Sim, 2004) พารามิเตอร์งบประมาณ Gamma จะจำกัดจำนวนพารามิเตอร์ที่สามารถมีค่าในกรณีที่เลวร้ายที่สุดพร้อมกันได้

สูตร
\mathcal{U} = \{ a_i : a_i = \bar{a}_i + \hat{a}_i \xi_i, \; \|\xi\|_\infty \leq 1 \}
3

แทนที่ข้อจำกัดที่ไม่แน่นอนแต่ละรายการด้วยคู่ที่ทนทาน (robust counterpart): กำหนดให้มีความเป็นไปได้สำหรับทุกการเกิดขึ้นใน U การดำเนินการนี้จะแปลงปัญหาเดิมให้เป็นโปรแกรมแบบกึ่งอนันต์ (semi-infinite program) — ซึ่งมีข้อจำกัดจำนวนอนันต์ โดยแต่ละข้อจำกัดจะสอดคล้องกับสมาชิกแต่ละตัวของ U

สูตร
\max_{a_i \in \mathcal{U}} a_i^T x \leq b_i \quad \forall i
4

หาค่าสมมูลเชิงกำหนด (deterministic equivalent) ที่สามารถจัดการได้ สำหรับชุดความไม่แน่นอนแบบงบประมาณ คู่ที่ทนทานจะถูกแปลงรูปแบบ (reformulate) ให้เป็น LP มาตรฐาน หรือ mixed-integer LP ที่มีขนาดใกล้เคียงกัน ซึ่งสามารถแก้ได้ด้วยตัวแก้ปัญหาทั่วไป หัวใจสำคัญของการแปลงรูปแบบคือการเพิ่มตัวแปรเสริม (auxiliary variables) เพื่อทำให้การหาค่าสูงสุดภายในชุดความไม่แน่นอนเป็นเชิงเส้น

สูตร
\bar{a}_i^T x + \Gamma_i \max_{\{S: |S| \leq \Gamma_i\}} \sum_{j \in S} \hat{a}_{ij} |x_j| \leq b_i
5

แก้ปัญหา LP ที่แปลงรูปแบบแล้วโดยใช้ตัวแก้ปัญหามาตรฐาน (simplex หรือ interior-point) ประเมินผลลัพธ์: ตรวจสอบการละเมิดข้อจำกัดในกรณีที่เลวร้ายที่สุดตลอดชุดความไม่แน่นอน รายงานราคาของความทนทาน (price of robustness) (การเพิ่มขึ้นของค่าฟังก์ชันวัตถุประสงค์เมื่อเทียบกับ LP แบบปกติ) และทำการวิเคราะห์ความไว (sensitivity analysis) ต่อพารามิเตอร์งบประมาณความทนทาน Gamma

ข้อผิดพลาดที่พบบ่อย

  • การตั้งค่า Gamma สูงเกินไปจะทำให้ข้อจำกัดทุกข้อเปลี่ยนแปลงค่าในกรณีที่เลวร้ายที่สุดพร้อมกัน ส่งผลให้ได้ผลลัพธ์ที่ระมัดระวังเกินไปและมีค่าใช้จ่ายสูง
  • การระบุชุดความไม่แน่นอนผิดพลาด (เช่น ไม่คำนึงถึงโครงสร้างความสัมพันธ์) อาจนำไปสู่การป้องกันที่มากเกินไปหรือน้อยเกินไป
  • ความสับสนระหว่าง robust LP กับ stochastic LP: RLP หาค่าเหมาะสมที่สุดในกรณีที่เลวร้ายที่สุด ไม่ใช่ค่าคาดหวัง
  • การละเลยรายงานราคาของความทนทาน — ควรเปรียบเทียบค่าฟังก์ชันวัตถุประสงค์ของผลลัพธ์แบบทนทานกับผลลัพธ์ของ LP แบบปกติเสมอ เพื่อประเมินต้นทุนของการระมัดระวัง
  • การนำ RLP ไปใช้กับปัญหาที่มีตัวแปรจำนวนเต็มโดยไม่ได้เปลี่ยนไปใช้สูตร Robust Mixed-Integer ซึ่งต้องการการแปลงรูปแบบที่แตกต่างออกไป

คำถามที่พบบ่อย

Robust LP แตกต่างจาก Stochastic LP อย่างไร?

Stochastic LP หาค่าเหมาะสมที่สุดของประสิทธิภาพที่คาดหวังโดยพิจารณาจากการแจกแจงความน่าจะเป็นของสถานการณ์ต่างๆ ซึ่งต้องการความรู้เกี่ยวกับการแจกแจง Robust LP หาค่าเหมาะสมที่สุดของประสิทธิภาพในกรณีที่เลวร้ายที่สุดตลอดชุดความไม่แน่นอน ซึ่งต้องการเพียงขอบเขต — ไม่ต้องใช้การแจกแจงความน่าจะเป็น Robust LP เหมาะสมเมื่อการแจกแจงไม่น่าเชื่อถือ; stochastic LP เหมาะสมเมื่อมีการประมาณค่าได้ดี

ราคาของความทนทานคืออะไร?

ราคาของความทนทานคือการเพิ่มขึ้นของค่าฟังก์ชันวัตถุประสงค์ (ต้นทุน) ของผลลัพธ์แบบทนทานเมื่อเทียบกับผลลัพธ์ของ LP แบบปกติ Bertsimas และ Sim (2004) ได้พิสูจน์ว่าราคานี้จะเพิ่มขึ้นตามรากที่สองของจำนวนพารามิเตอร์ที่ไม่แน่นอนสำหรับชุดความไม่แน่นอนแบบงบประมาณ ทำให้ความทนทานมีราคาที่สมเหตุสมผลอย่างน่าประหลาดใจ

งบประมาณความทนทาน Gamma คืออะไร?

Gamma เป็นพารามิเตอร์ในแบบจำลองของ Bertsimas-Sim ที่ควบคุมจำนวนสัมประสิทธิ์ที่ไม่แน่นอนที่สามารถมีค่าในกรณีที่เลวร้ายที่สุดพร้อมกันได้ Gamma = 0 จะได้ผลลัพธ์เหมือน LP แบบปกติ; Gamma = n จะป้องกันพารามิเตอร์ทั้ง n ตัวที่เปลี่ยนแปลงค่าพร้อมกัน นักวิเคราะห์มักจะเลือก Gamma โดยพิจารณาจากขอบเขตความน่าจะเป็นของการละเมิดที่ยอมรับได้

Robust LP จำเป็นต้องใช้ตัวแก้ปัญหาพิเศษหรือไม่?

ไม่ สำหรับชุดความไม่แน่นอนแบบกล่องและแบบงบประมาณ คู่ที่ทนทานจะเป็นโปรแกรมเชิงเส้น (linear program) ซึ่งสามารถแก้ได้ด้วยตัวแก้ปัญหา LP มาตรฐานทั่วไป (CPLEX, Gurobi, HiGHS, เป็นต้น) ชุดความไม่แน่นอนแบบทรงรีต้องการตัวแก้ปัญหาโปรแกรมเชิงลำดับที่สอง (second-order cone program solver) ซึ่งก็ได้รับการสนับสนุนอย่างกว้างขวางเช่นกัน

เมื่อใดที่ควรใช้ Robust Mixed-Integer Programming แทน?

หากตัวแปรตัดสินใจต้องเป็นจำนวนเต็ม (เช่น การตัดสินใจแบบใช่/ไม่ใช่, ขนาดล็อต) คู่ที่ทนทานจะมีตัวแปรจำนวนเต็มและกลายเป็น Robust Mixed-Integer Program แนวทางชุดความไม่แน่นอนจะเหมือนกัน แต่การแปลงรูปแบบและข้อกำหนดของตัวแก้ปัญหาจะเปลี่ยนแปลงไปตามนั้น

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

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

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

    เปิดเอกสารอ้างอิง DOI
    คัดลอกแล้ว
  2. Ben-Tal, A., Nemirovski, A. (1999). Robust solutions of uncertain linear programs. Operations Research Letters, 25(1), 1–13.

    เปิดเอกสารอ้างอิง DOI
    คัดลอกแล้ว