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

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

ผู้เสนอ
Bertsimas, D. and Sim, M.
ปี
2003
ประเภท
Deterministic robust optimization with integer variables
กลุ่มวิธี
Simulation / optimization

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

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

ใช้ทำอะไร?

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

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

การตัดสินใจในโลกแห่งความเป็นจริงหลายอย่าง เช่น ตารางการผลิต การออกแบบเครือข่าย การจัดสรรทรัพยากร มักเกี่ยวข้องกับจำนวนเต็ม (คุณไม่สามารถผลิตครึ่งหน่วยหรือสร้างครึ่งโรงงานได้) และข้อมูลที่ไม่แน่นอน (ต้นทุน ความต้องการ เวลาเดินทางที่ผันผวน) การโปรแกรมจำนวนเต็มแบบดั้งเดิมละเลยความไม่แน่นอนและอาจให้ผลลัพธ์ที่ล้มเหลวอย่างมากเมื่อข้อมูลนำเข้าแตกต่างจากค่าประมาณ การโปรแกรมจำนวนเต็มแบบคงทนจะจำลองความไม่แน่นอนนี้อย่างชัดเจนผ่านชุดความไม่แน่นอนและค้นหาผลลัพธ์จำนวนเต็มที่ทำงานได้ดีที่สุดในกรณีที่เลวร้ายที่สุด แนวทางของ Bertsimas-Sim ใช้พารามิเตอร์งบประมาณความไม่แน่นอนเพื่อควบคุมการอนุรักษ์นิยม: หากงบประมาณเป็นศูนย์ ปัญหาจะลดลงเป็นการโปรแกรมจำนวนเต็มเชิงกำหนด (deterministic IP); เมื่องบประมาณเพิ่มขึ้น ผลลัพธ์จะได้รับการป้องกันจากการรบกวนของข้อมูลมากขึ้น โดยมีค่าใช้จ่ายของค่าวัตถุประสงค์

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

การศึกษาอย่างเป็นระบบของการหาค่าเหมาะสมที่สุดแบบไม่ต่อเนื่องที่คงทนได้รับการพัฒนาโดย Bertsimas และ Sim ในบทความปี 2003 ของพวกเขาที่นำเสนอแบบจำลองงบประมาณความไม่แน่นอนสำหรับปัญหาแบบไม่ต่อเนื่อง โดยต่อยอดจากงาน LP แบบคงทนก่อนหน้านี้โดย Ben-Tal และ Nemirovski (1998) และ El Ghaoui และ Lebret (1997) Bertsimas และ Sim แสดงให้เห็นว่าคู่คงทนของการโปรแกรมจำนวนเต็มภายใต้ความไม่แน่นอนของงบประมาณยังคงเป็น MIP ที่สามารถจัดการได้ ซึ่งกระตุ้นให้เกิดการประยุกต์ใช้อย่างกว้างขวางในด้านโลจิสติกส์ การออกแบบเครือข่าย และการจัดตารางเวลา เอกสารวิชาการปี 2009 โดย Ben-Tal, El Ghaoui และ Nemirovski ได้รวบรวมรากฐานทางทฤษฎีของการหาค่าเหมาะสมที่สุดแบบคงทนในบริบทต่อเนื่องและไม่ต่อเนื่อง

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

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

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

  • การมุ่งเน้นกรณีที่เลวร้ายที่สุดอาจอนุรักษ์นิยมเกินไป ทำให้ได้ผลลัพธ์ที่มีค่าวัตถุประสงค์สูงกว่าค่าเหมาะสมที่สุดเชิงกำหนดอย่างมีนัยสำคัญ แม้ว่าสถานการณ์ที่เป็นปฏิปักษ์จะไม่น่าจะเกิดขึ้นก็ตาม
  • ความสามารถในการจัดการขึ้นอยู่กับการเลือกชุดความไม่แน่นอน; ชุดนูนทั่วไปหรือไม่นูนอาจทำให้คู่คงทนยากต่อการคำนวณ
  • ไม่สามารถรวมข้อมูลความน่าจะเป็นได้อย่างเป็นธรรมชาติ; เหตุการณ์ที่หายากแต่มีผลกระทบสูงได้รับการปฏิบัติเช่นเดียวกับการรบกวนที่น่าจะเกิดขึ้น
  • การโปรแกรมจำนวนเต็มแบบคงทนขนาดใหญ่อาจยังคงมีค่าใช้จ่ายในการคำนวณสูง โดยเฉพาะอย่างยิ่งสำหรับปัญหาที่มีพารามิเตอร์ที่ไม่แน่นอนจำนวนมาก
  • การเลือกชุดความไม่แน่นอนและระดับงบประมาณที่เหมาะสมต้องอาศัยความเชี่ยวชาญเฉพาะด้านและอาจส่งผลกระทบอย่างมีนัยสำคัญต่อผลลัพธ์

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

จุดแข็ง

  • ให้การรับประกันกรณีที่เลวร้ายที่สุดเชิงกำหนดโดยไม่ต้องอาศัยความรู้เกี่ยวกับการแจกแจงความน่าจะเป็นของพารามิเตอร์ที่ไม่แน่นอน
  • กรอบงานงบประมาณความไม่แน่นอนของ Bertsimas-Sim ทำให้คู่คงทนสามารถจัดการได้ — มักจะเป็น MIP มาตรฐานที่มีขนาดใกล้เคียงกับปัญหาที่ระบุ
  • ระดับการอนุรักษ์นิยมสามารถควบคุมได้ง่ายผ่านพารามิเตอร์งบประมาณเดียว Gamma ทำให้สามารถวิเคราะห์การแลกเปลี่ยนระหว่างการป้องกันและต้นทุนได้อย่างชัดเจน
  • สามารถนำไปใช้ได้ในหลากหลายสาขา: โลจิสติกส์, พลังงาน, การเงิน, โทรคมนาคม, การจัดตารางเวลา
  • ผลลัพธ์สามารถนำไปปฏิบัติได้จริง เนื่องจากสถานการณ์กรณีที่เลวร้ายที่สุดมีขอบเขตและตรวจสอบได้

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

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

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

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

1

กำหนดการโปรแกรมจำนวนเต็มด้วยพารามิเตอร์ที่ไม่แน่นอน: ลด (หรือเพิ่ม) วัตถุประสงค์กรณีที่เลวร้ายที่สุดภายใต้ข้อจำกัดที่ต้องเป็นจริงสำหรับทุกการรับรู้ในชุดความไม่แน่นอน ตัวแปรตัดสินใจ x ต้องเป็นจำนวนเต็มหรือเลขฐานสอง และปัญหาถูกกำหนดเป็นโครงสร้างสองระดับแบบ min-max (หรือ max-min) โดยที่ปัญหาภายในจะเลือกสถานการณ์กรณีที่เลวร้ายที่สุด

สูตร
\min_{x \in \mathcal{X}} \max_{\xi \in \mathcal{U}} c(\xi)^\top x \quad \text{s.t.} \quad A(\xi)x \leq b,\; x \in \mathbb{Z}^n
2

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

สูตร
\mathcal{U} = \{\xi : \|\xi - \hat{\xi}\|_\infty \leq \Gamma\} \quad (\text{budget-of-uncertainty, Bertsimas-Sim})
3

ใช้ทฤษฎีคู่ (dualize) หรือปรับรูปแบบการหาค่าสูงสุดกรณีที่เลวร้ายที่สุดภายใน เพื่อให้ได้โปรแกรมจำนวนเต็มผสมระดับเดียว ภายใต้แบบจำลองงบประมาณความไม่แน่นอน คู่คงทนจะแนะนำตัวแปรต่อเนื่องเสริมและข้อจำกัดเชิงเส้น ซึ่งรักษาความสามารถในการจัดการของตัวแก้ปัญหาแบบ branch-and-bound หรือ branch-and-cut มาตรฐาน โดยไม่ต้องมีการแจกแจงสถานการณ์แบบเลขชี้กำลัง

4

แก้ปัญหาการโปรแกรมจำนวนเต็มแบบคงทนที่ปรับรูปแบบใหม่โดยใช้ตัวแก้ปัญหา MIP มาตรฐาน (CPLEX, Gurobi, SCIP) หรือ branch-and-bound เฉพาะทางพร้อมขั้นตอนการกำหนดขอบเขตแบบคงทน สำหรับกรณีขนาดใหญ่ สามารถใช้วิธีการแยกส่วน เช่น Benders decomposition หรือ column-and-constraint generation เพื่อแยกปัญหาจำนวนเต็มหลักออกจากปัญหาย่อยที่เป็นปฏิปักษ์

5

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

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

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

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

การโปรแกรมจำนวนเต็มแบบคงทนแตกต่างจากการโปรแกรมจำนวนเต็มเชิงสุ่มอย่างไร?

การโปรแกรมจำนวนเต็มเชิงสุ่มจะหาค่าเหมาะสมที่สุดของประสิทธิภาพที่คาดหวังจากการแจกแจงความน่าจะเป็นของสถานการณ์ และโดยทั่วไปต้องใช้แผนผังสถานการณ์ การโปรแกรมจำนวนเต็มแบบคงทนจะหาค่าเหมาะสมที่สุดของประสิทธิภาพกรณีที่เลวร้ายที่สุดจากชุดความไม่แน่นอนและไม่ต้องการการแจกแจงความน่าจะเป็น — เพียงแค่ขอบเขตของความไม่แน่นอน RIP ให้การรับประกันความเป็นไปได้ที่เข้มงวด; IP เชิงสุ่มให้การรับประกันเชิงความน่าจะเป็น

งบประมาณความไม่แน่นอนคืออะไร และฉันจะเลือกได้อย่างไร?

งบประมาณ Gamma กำหนดขอบเขตว่าพารามิเตอร์ที่ไม่แน่นอนกี่ตัวที่เบี่ยงเบนจากค่าที่ระบุพร้อมกัน เมื่อ Gamma เท่ากับศูนย์ แบบจำลองจะลดลงเป็น IP เชิงกำหนด เมื่อ Gamma เพิ่มขึ้น ผลลัพธ์จะมีความคงทนมากขึ้นแต่มีต้นทุนสูงขึ้น กฎที่ใช้ได้จริงคือการตั้งค่า Gamma โดยใช้ข้อมูลในอดีต: หากพารามิเตอร์อย่างมากที่สุด k ตัวมักจะเบี่ยงเบนในช่วงเวลาหนึ่ง ให้ตั้งค่า Gamma เป็น k อีกทางหนึ่ง Bertsimas และ Sim ให้ขอบเขตเชิงความน่าจะเป็นของการละเมิดข้อจำกัดสำหรับ Gamma ที่กำหนด

คู่คงทนของการโปรแกรมจำนวนเต็มยังคงเป็นการโปรแกรมจำนวนเต็มหรือไม่?

ใช่ ภายใต้แบบจำลองงบประมาณความไม่แน่นอน คู่คงทนจะแนะนำตัวแปรเสริมต่อเนื่องเพิ่มเติมและข้อจำกัดเชิงเส้น แต่ยังคงรักษาความเป็นจำนวนเต็มของตัวแปรตัดสินใจเดิม ผลลัพธ์คือ MIP มาตรฐานที่สามารถแก้ไขได้ด้วยตัวแก้ปัญหาสำเร็จรูป

การโปรแกรมจำนวนเต็มแบบคงทนสามารถจัดการได้ด้วยการคำนวณเมื่อใด?

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

การโปรแกรมจำนวนเต็มแบบคงทนสามารถจัดการกับวัตถุประสงค์หลายอย่างได้หรือไม่?

ได้ โดยการขยายไปสู่การโปรแกรมจำนวนเต็มหลายวัตถุประสงค์แบบคงทน ซึ่งแต่ละวัตถุประสงค์ได้รับการปฏิบัติอย่างคงทน สิ่งนี้นำไปสู่ขอบเขตพาเรโตที่คงทน อีกทางหนึ่ง ผู้ปฏิบัติงานสามารถปรับขนาดวัตถุประสงค์ (ผลรวมถ่วงน้ำหนักหรือข้อจำกัดเอปไซลอน) และใช้ RIP มาตรฐานกับปัญหาวัตถุประสงค์เดียวที่เกิดขึ้น

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

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

  1. Bertsimas, D., Sim, M. (2003). Robust discrete optimization and network flows. Mathematical Programming, 98(1-3), 49-71.

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

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