การโปรแกรมจำนวนเต็มแบบคงทน — การหาค่าเหมาะสมที่สุดภายใต้ความไม่แน่นอนพร้อมข้อจำกัดจำนวนเต็ม
- ผู้เสนอ
- 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 ทำให้สามารถวิเคราะห์การแลกเปลี่ยนระหว่างการป้องกันและต้นทุนได้อย่างชัดเจน
- สามารถนำไปใช้ได้ในหลากหลายสาขา: โลจิสติกส์, พลังงาน, การเงิน, โทรคมนาคม, การจัดตารางเวลา
- ผลลัพธ์สามารถนำไปปฏิบัติได้จริง เนื่องจากสถานการณ์กรณีที่เลวร้ายที่สุดมีขอบเขตและตรวจสอบได้
การประยุกต์ใช้
- การกำหนดตำแหน่งสิ่งอำนวยความสะดวกและการออกแบบเครือข่ายที่คงทนภายใต้ความต้องการหรือเวลาเดินทางที่ไม่แน่นอน
- การกำหนดขนาดล็อตและการจัดตารางการผลิตด้วยเวลาการประมวลผลหรืออัตราผลผลิตที่ไม่แน่นอน
- การหาค่าเหมาะสมที่สุดของพอร์ตการลงทุนด้วยข้อจำกัดจำนวนและผลตอบแทนสินทรัพย์ที่ไม่แน่นอน
- การตอบสนองฉุกเฉินและโลจิสติกส์ด้านมนุษยธรรมภายใต้พารามิเตอร์ภัยพิบัติที่ไม่แน่นอน
- การวางแผนระบบพลังงาน (การจัดสรรหน่วยผลิต, การขยายกำลังการผลิต) ด้วยผลผลิตพลังงานหมุนเวียนที่ไม่แน่นอน
- การกำหนดเส้นทางเครือข่ายโทรคมนาคมภายใต้ความต้องการการจราจรที่ไม่แน่นอน
วิธีการทำงาน
วิธีการทำงาน
กำหนดการโปรแกรมจำนวนเต็มด้วยพารามิเตอร์ที่ไม่แน่นอน: ลด (หรือเพิ่ม) วัตถุประสงค์กรณีที่เลวร้ายที่สุดภายใต้ข้อจำกัดที่ต้องเป็นจริงสำหรับทุกการรับรู้ในชุดความไม่แน่นอน ตัวแปรตัดสินใจ 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กำหนดชุดความไม่แน่นอน U ที่ครอบคลุมช่วงที่เป็นไปได้ของการเปลี่ยนแปลงพารามิเตอร์ ตัวเลือกทั่วไปได้แก่ ชุดกล่อง (ขอบเขตช่วงอิสระต่อพารามิเตอร์), ชุดวงรี (ความไม่แน่นอนที่สัมพันธ์กัน) และชุดงบประมาณความไม่แน่นอนของ Bertsimas-Sim ซึ่งมีพารามิเตอร์อย่างมากที่สุด Gamma ที่เบี่ยงเบนจากค่าที่ระบุพร้อมกัน งบประมาณ Gamma เป็นตัวควบคุมการอนุรักษ์นิยมที่สำคัญ
สูตร
\mathcal{U} = \{\xi : \|\xi - \hat{\xi}\|_\infty \leq \Gamma\} \quad (\text{budget-of-uncertainty, Bertsimas-Sim})ใช้ทฤษฎีคู่ (dualize) หรือปรับรูปแบบการหาค่าสูงสุดกรณีที่เลวร้ายที่สุดภายใน เพื่อให้ได้โปรแกรมจำนวนเต็มผสมระดับเดียว ภายใต้แบบจำลองงบประมาณความไม่แน่นอน คู่คงทนจะแนะนำตัวแปรต่อเนื่องเสริมและข้อจำกัดเชิงเส้น ซึ่งรักษาความสามารถในการจัดการของตัวแก้ปัญหาแบบ branch-and-bound หรือ branch-and-cut มาตรฐาน โดยไม่ต้องมีการแจกแจงสถานการณ์แบบเลขชี้กำลัง
แก้ปัญหาการโปรแกรมจำนวนเต็มแบบคงทนที่ปรับรูปแบบใหม่โดยใช้ตัวแก้ปัญหา MIP มาตรฐาน (CPLEX, Gurobi, SCIP) หรือ branch-and-bound เฉพาะทางพร้อมขั้นตอนการกำหนดขอบเขตแบบคงทน สำหรับกรณีขนาดใหญ่ สามารถใช้วิธีการแยกส่วน เช่น Benders decomposition หรือ column-and-constraint generation เพื่อแยกปัญหาจำนวนเต็มหลักออกจากปัญหาย่อยที่เป็นปฏิปักษ์
ประเมินผลลัพธ์แบบคงทนเทียบกับค่าเหมาะสมที่สุดเชิงกำหนดและเทียบกับชุดสถานการณ์นอกตัวอย่าง รายงานราคาของความคงทน (ช่องว่างวัตถุประสงค์ระหว่างผลลัพธ์แบบคงทนและแบบระบุ) และตรวจสอบว่าผลลัพธ์แบบคงทนเป็นไปตามข้อจำกัดทั้งหมดภายใต้สถานการณ์กรณีที่เลวร้ายที่สุด การวิเคราะห์ความไวต่อ Gamma จะช่วยให้ผู้ปฏิบัติงานสามารถแลกเปลี่ยนระดับการป้องกันกับต้นทุนของผลลัพธ์ได้
ข้อผิดพลาดที่พบบ่อย
- การตั้งค่างบประมาณความไม่แน่นอน Gamma สูงเกินไปจะทำให้ได้ผลลัพธ์ที่อนุรักษ์นิยมอย่างยิ่งและไม่มีประโยชน์ในทางปฏิบัติ; แนะนำให้ปรับเทียบ Gamma กับความถี่การเบี่ยงเบนในอดีต
- การละเลยที่จะตรวจสอบว่าการปรับรูปแบบคู่คงทนนั้นถูกต้องสำหรับชุดความไม่แน่นอนที่เลือก — การปรับรูปแบบบางอย่างใช้ได้กับชุดประเภทเฉพาะเท่านั้น (เช่น ชุดงบประมาณ ไม่ใช่ชุดวงรี)
- การสับสนระหว่างการโปรแกรมจำนวนเต็มแบบคงทนกับการโปรแกรมจำนวนเต็มเชิงสุ่ม: RIP ไม่ได้หาค่าเหมาะสมที่สุดของค่าคาดหวังและไม่ต้องการแผนผังสถานการณ์หรือการแจกแจงความน่าจะเป็น
- การละเลยการวิเคราะห์ราคาของความคงทน — ผู้ปฏิบัติงานควรเปรียบเทียบค่าวัตถุประสงค์แบบคงทนและแบบระบุเสมอเพื่อตัดสินว่าการป้องกันนั้นคุ้มค่ากับต้นทุนหรือไม่
- การใช้ RIP กับปัญหาที่ความไม่แน่นอนส่งผลกระทบต่อด้านขวาแบบไม่เชิงเส้นโดยไม่ตรวจสอบว่าปัญหาย่อยที่เกิดขึ้นยังคงสามารถจัดการได้
คำถามที่พบบ่อย
การโปรแกรมจำนวนเต็มแบบคงทนแตกต่างจากการโปรแกรมจำนวนเต็มเชิงสุ่มอย่างไร?
การโปรแกรมจำนวนเต็มเชิงสุ่มจะหาค่าเหมาะสมที่สุดของประสิทธิภาพที่คาดหวังจากการแจกแจงความน่าจะเป็นของสถานการณ์ และโดยทั่วไปต้องใช้แผนผังสถานการณ์ การโปรแกรมจำนวนเต็มแบบคงทนจะหาค่าเหมาะสมที่สุดของประสิทธิภาพกรณีที่เลวร้ายที่สุดจากชุดความไม่แน่นอนและไม่ต้องการการแจกแจงความน่าจะเป็น — เพียงแค่ขอบเขตของความไม่แน่นอน RIP ให้การรับประกันความเป็นไปได้ที่เข้มงวด; IP เชิงสุ่มให้การรับประกันเชิงความน่าจะเป็น
งบประมาณความไม่แน่นอนคืออะไร และฉันจะเลือกได้อย่างไร?
งบประมาณ Gamma กำหนดขอบเขตว่าพารามิเตอร์ที่ไม่แน่นอนกี่ตัวที่เบี่ยงเบนจากค่าที่ระบุพร้อมกัน เมื่อ Gamma เท่ากับศูนย์ แบบจำลองจะลดลงเป็น IP เชิงกำหนด เมื่อ Gamma เพิ่มขึ้น ผลลัพธ์จะมีความคงทนมากขึ้นแต่มีต้นทุนสูงขึ้น กฎที่ใช้ได้จริงคือการตั้งค่า Gamma โดยใช้ข้อมูลในอดีต: หากพารามิเตอร์อย่างมากที่สุด k ตัวมักจะเบี่ยงเบนในช่วงเวลาหนึ่ง ให้ตั้งค่า Gamma เป็น k อีกทางหนึ่ง Bertsimas และ Sim ให้ขอบเขตเชิงความน่าจะเป็นของการละเมิดข้อจำกัดสำหรับ Gamma ที่กำหนด
คู่คงทนของการโปรแกรมจำนวนเต็มยังคงเป็นการโปรแกรมจำนวนเต็มหรือไม่?
ใช่ ภายใต้แบบจำลองงบประมาณความไม่แน่นอน คู่คงทนจะแนะนำตัวแปรเสริมต่อเนื่องเพิ่มเติมและข้อจำกัดเชิงเส้น แต่ยังคงรักษาความเป็นจำนวนเต็มของตัวแปรตัดสินใจเดิม ผลลัพธ์คือ MIP มาตรฐานที่สามารถแก้ไขได้ด้วยตัวแก้ปัญหาสำเร็จรูป
การโปรแกรมจำนวนเต็มแบบคงทนสามารถจัดการได้ด้วยการคำนวณเมื่อใด?
ความสามารถในการจัดการจะคงอยู่สำหรับชุดความไม่แน่นอนที่ปัญหาคู่มีรูปแบบปิดหรือสามารถแสดงเป็น LP ได้ เช่น ชุดกล่อง ชุดงบประมาณ และชุดพหุเหลี่ยม ความไม่แน่นอนแบบวงรีในการโปรแกรมจำนวนเต็มนำไปสู่ข้อจำกัดกรวยอันดับสองซึ่งโดยทั่วไปจะยากกว่า ปัญหาที่มีตัวแปรจำนวนเต็มจำนวนมากและชุดความไม่แน่นอนขนาดใหญ่อาจยังคงต้องใช้วิธีการแยกส่วน
การโปรแกรมจำนวนเต็มแบบคงทนสามารถจัดการกับวัตถุประสงค์หลายอย่างได้หรือไม่?
ได้ โดยการขยายไปสู่การโปรแกรมจำนวนเต็มหลายวัตถุประสงค์แบบคงทน ซึ่งแต่ละวัตถุประสงค์ได้รับการปฏิบัติอย่างคงทน สิ่งนี้นำไปสู่ขอบเขตพาเรโตที่คงทน อีกทางหนึ่ง ผู้ปฏิบัติงานสามารถปรับขนาดวัตถุประสงค์ (ผลรวมถ่วงน้ำหนักหรือข้อจำกัดเอปไซลอน) และใช้ RIP มาตรฐานกับปัญหาวัตถุประสงค์เดียวที่เกิดขึ้น
วิธีการที่เกี่ยวข้อง
แหล่งอ้างอิง
Bertsimas, D., Sim, M. (2003). Robust discrete optimization and network flows. Mathematical Programming, 98(1-3), 49-71.
เปิดเอกสารอ้างอิง DOIคัดลอกแล้วBen-Tal, A., El Ghaoui, L., Nemirovski, A. (2009). Robust Optimization. Princeton University Press, Princeton, NJ.
ISBN: 9780691143682คัดลอกแล้ว