การโปรแกรมเชิงเส้นจำนวนเต็มผสมหลายวัตถุประสงค์
- ผู้เสนอ
- Ehrgott, M.; Mavrotas, G. and others in multi-criteria optimization
- ปี
- 1980s–2000s
- ประเภท
- Mathematical optimization
- กลุ่มวิธี
- Simulation / optimization
ข้อความนี้เป็นการแปลด้วยเครื่องและยังไม่ได้รับการตรวจทาน อ่านต้นฉบับภาษาอังกฤษ
ใช้ทำอะไร?
การโปรแกรมเชิงเส้นจำนวนเต็มผสมหลายวัตถุประสงค์ (Multi-Objective Mixed-Integer Programming หรือ MO-MIP) เป็นกรอบการทำงานสำหรับการหาค่าเหมาะที่สุดที่ปรับปรุงฟังก์ชันวัตถุประสงค์สองฟังก์ชันขึ้นไปที่มีความขัดแย้งกันพร้อมกัน ภายใต้ข้อจำกัดเชิงเส้นหรือไม่เป็นเชิงเส้น โดยที่ตัวแปรตัดสินใจบางตัวถูกจำกัดให้เป็นค่าจำนวนเต็มและตัวแปรอื่น ๆ เป็นค่าต่อเนื่อง มีการประยุกต์ใช้อย่างกว้างขวางในการออกแบบทางวิศวกรรม การวางแผนห่วงโซ่อุปทาน การจัดสรรทรัพยากร และปัญหาการจัดตารางเวลาที่ต้องการการเลือกแบบไม่ต่อเนื่องควบคู่ไปกับปริมาณต่อเนื่อง
แนวคิดเบื้องหลังวิธีการ
การตัดสินใจในโลกแห่งความเป็นจริงจำนวนมากเกี่ยวข้องกับการเลือกแบบไม่ต่อเนื่อง (เช่น จำนวนโรงงานที่จะเปิด โครงการที่จะให้ทุน การซื้อเครื่องจักรหรือไม่) และการตัดสินใจแบบต่อเนื่อง (เช่น ปริมาณที่จะผลิต วิธีการจัดสรรงบประมาณ) เมื่อการเลือกเหล่านี้ส่งผลกระทบต่อเป้าหมายที่ขัดแย้งกันหลายอย่างพร้อมกัน เช่น การลดต้นทุนในขณะที่เพิ่มระดับการบริการให้สูงสุด จะไม่มีคำตอบที่เหมาะสมที่สุดเพียงคำตอบเดียว แต่ MO-MIP จะสำรวจขอบเขตการแลกเปลี่ยน (Pareto front) ของคำตอบที่ไม่ถูกครอบงำทั้งหมด ทำให้ผู้ตัดสินใจได้รับแผนที่ที่มีโครงสร้างของการประนีประนอมที่เป็นไปได้ แทนที่จะเป็นคำตอบที่ถูกบังคับเพียงคำตอบเดียว
ประวัติศาสตร์
การโปรแกรมเชิงเส้นจำนวนเต็มผสมได้รับการกำหนดอย่างเป็นทางการในช่วงทศวรรษ 1950-1960 จากผลงานของ Gomory และ Land และ Doig การขยายผลแบบหลายวัตถุประสงค์เกิดขึ้นในช่วงทศวรรษ 1970-1980 เมื่อนักวิจัยตระหนักว่าปัญหาทางวิศวกรรมและการวิจัยการดำเนินงานจำนวนมากเกี่ยวข้องกับเป้าหมายที่แข่งขันกัน การจัดการอย่างเป็นระบบได้รับการรวบรวมโดย Ehrgott (2005) และ Mavrotas (2009) ซึ่งการนำ epsilon-constraint ไปใช้ยังคงเป็นข้อมูลอ้างอิงที่อ้างถึงอย่างกว้างขวางสำหรับการใช้งาน MO-MIP ในทางปฏิบัติ
ควรใช้เมื่อใด
ใช้ MO-MIP เมื่อปัญหาการตัดสินใจเกี่ยวข้องกับตัวแปรจำนวนเต็มหรือไบนารีโดยธรรมชาติ (การเลือกที่ตั้งโรงงาน การเลือกโครงการ การจัดตารางเวลา) ควบคู่ไปกับปริมาณต่อเนื่อง และเมื่อต้องมีการแลกเปลี่ยนระหว่างวัตถุประสงค์ที่ขัดแย้งกันสองอย่างขึ้นไปอย่างชัดเจน เหมาะสมเมื่อต้องการคำตอบ Pareto ที่แม่นยำหรือใกล้เคียงความแม่นยำ และทรัพยากรการคำนวณเอื้ออำนวยต่อการค้นหาแบบ branch-and-bound ห้ามใช้เมื่อตัวแปรทั้งหมดเป็นแบบต่อเนื่อง (ให้ใช้ multi-objective LP หรือ nonlinear programming แทน) เมื่อขนาดของปัญหาทำให้การแก้ MIP แบบแม่นยำเป็นไปไม่ได้และ metaheuristics มีประโยชน์มากกว่า หรือเมื่อวัตถุประสงค์รวมเพียงอย่างเดียวเพียงพอและการวิเคราะห์หลายวัตถุประสงค์ไม่ได้เพิ่มคุณค่าในการตัดสินใจ
ข้อจำกัดและข้อควรพิจารณา
- ต้นทุนการคำนวณเพิ่มขึ้นแบบทวีคูณตามจำนวนตัวแปรจำนวนเต็มและขนาดของปัญหา; อินสแตนซ์ขนาดใหญ่อาจไม่สามารถจัดการได้ด้วยวิธีที่แม่นยำ
- ต้องมีการกำหนดวัตถุประสงค์และข้อจำกัดทั้งหมดในรูปแบบทางคณิตศาสตร์อย่างแม่นยำ ซึ่งอาจเป็นเรื่องยากสำหรับเป้าหมายในโลกแห่งความเป็นจริงที่เป็นเชิงคุณภาพหรือคลุมเครือ
- วิธีการปรับเป็นสเกลาร์ เช่น ผลรวมถ่วงน้ำหนัก ไม่สามารถค้นหาคำตอบในภูมิภาคที่ไม่นูนของ Pareto front ได้ ซึ่งอาจพลาดการแลกเปลี่ยนที่สำคัญ
- การสร้าง Pareto front ที่หนาแน่นต้องแก้ปัญหาย่อย MIP จำนวนมาก ซึ่งเพิ่มเวลาการคำนวณทั้งหมด
- ผลลัพธ์มีความอ่อนไหวต่อการกำหนดข้อจำกัดและความแม่นยำของข้อมูลปัญหา; แบบจำลองที่ไม่เป็นไปได้หรือมีขอบเขตไม่ดีจะไม่มีผลลัพธ์ที่เป็นประโยชน์
เงื่อนไขจากแหล่งที่มาไม่สามารถใช้แทนการทบทวนทางวิทยาศาสตร์ที่เป็นอิสระหรือการตรวจสอบโดยเอนจินวิเคราะห์ได้
จุดแข็ง
- ให้คำตอบที่เหมาะสมที่สุดหรือใกล้เคียงที่สุดที่พิสูจน์ได้สำหรับปัญหาย่อยที่ปรับเป็นสเกลาร์แต่ละปัญหา รับประกันคุณภาพของ Pareto front สำหรับขนาดปัญหาที่จัดการได้
- จัดการกับการเลือกแบบไม่ต่อเนื่องในโลกแห่งความเป็นจริงได้อย่างเป็นธรรมชาติ (การตัดสินใจแบบไบนารี ปริมาณจำนวนเต็ม) ซึ่งการผ่อนคลายแบบต่อเนื่องไม่สามารถแสดงได้อย่างถูกต้อง
- ให้ Pareto front ที่สมบูรณ์ ทำให้ผู้ตัดสินใจได้รับข้อมูลการแลกเปลี่ยนที่โปร่งใสและมีโครงสร้าง แทนที่จะเป็นการประนีประนอมที่ถูกบังคับเพียงครั้งเดียว
- วิธีข้อจำกัดเอปไซลอนและการปรับเป็นสเกลาร์แบบเป็นระบบอื่น ๆ ช่วยให้สามารถสำรวจชุดคำตอบที่ไม่ถูกครอบงำได้อย่างหนาแน่นและควบคุมได้
- เข้ากันได้กับตัวแก้ปัญหาเชิงพาณิชย์และโอเพนซอร์สที่หลากหลาย (CPLEX, Gurobi, GLPK, CBC) ที่จัดการปัญหา MIP ขนาดใหญ่ได้
การประยุกต์ใช้
- การเลือกที่ตั้งโรงงานและการออกแบบเครือข่ายห่วงโซ่อุปทาน: ลดต้นทุนและเพิ่มความครอบคลุมการบริการลูกค้าพร้อมกันด้วยตัวแปรไบนารีเปิด/ปิด
- การจัดทำงบประมาณลงทุนและการเลือกกลุ่มโครงการ: เพิ่มผลตอบแทนและลดความเสี่ยงภายใต้ข้อจำกัดด้านงบประมาณและทรัพยากรด้วยตัวแปรไบนารีการเลือกโครงการ
- การจัดตารางการผลิต: ลด makespan และ tardiness พร้อมกันด้วยขนาดล็อตจำนวนเต็มและการกำหนดเครื่องจักรแบบไบนารี
- การวางแผนระบบพลังงาน: ปรับต้นทุนและการปล่อย CO2 ให้เหมาะสมสำหรับส่วนผสมโรงไฟฟ้าด้วยการตัดสินใจลงทุนแบบไม่ต่อเนื่องและตัวแปรการจัดส่งแบบต่อเนื่อง
- การจัดสรรทรัพยากรด้านการดูแลสุขภาพ: เพิ่มความครอบคลุมของผู้ป่วยและความเท่าเทียมกันในขณะที่ลดค่าใช้จ่ายโดยใช้จำนวนพนักงานที่เป็นจำนวนเต็มและการตัดสินใจเกี่ยวกับสิ่งอำนวยความสะดวกแบบไบนารี
- การขนส่งและโลจิสติกส์: ลดเวลาเดินทางและการปล่อยมลพิษพร้อมกันด้วยจำนวนยานพาหนะที่เป็นจำนวนเต็มและการตัดสินใจเส้นทาง
วิธีการทำงาน
วิธีการทำงาน
กำหนดปัญหาโดยระบุฟังก์ชันวัตถุประสงค์ k ฟังก์ชัน f_1(x), ..., f_k(x) ที่จะลดหรือเพิ่มให้มากที่สุด ชุดของข้อจำกัดเชิงเส้นหรือไม่เป็นเชิงเส้น Ax <= b และโดเมนตัวแปรที่ตัวแปรบางตัวเป็นค่าจำนวนเต็ม (เช่น ไบนารี 0/1) และตัวแปรอื่น ๆ เป็นค่าต่อเนื่อง กำหนดขอบเขตและข้อมูลให้ชัดเจนก่อนการแก้ปัญหา
ใช้กลยุทธ์การปรับเป็นสเกลาร์ (scalarization) หรือการแยกส่วน (decomposition) เพื่อแปลงปัญหาหลายวัตถุประสงค์ให้เป็นลำดับของปัญหาย่อย MIP แบบวัตถุประสงค์เดียว กลยุทธ์ทั่วไปได้แก่ วิธีผลรวมถ่วงน้ำหนัก (minimize sum of w_i * f_i) วิธีข้อจำกัดเอปไซลอน (optimize one objective while constraining others to threshold levels) และฟังก์ชันปรับเป็นสเกลาร์แบบบรรลุเป้าหมาย (achievement scalarizing functions)
แก้ปัญหาย่อย MIP ที่ปรับเป็นสเกลาร์แต่ละปัญหาโดยใช้วิธี branch-and-bound, branch-and-cut หรือตัวแก้ปัญหาที่แม่นยำอื่น ๆ (เช่น CPLEX, Gurobi, GLPK) สำหรับปัญหาย่อยแต่ละปัญหา ตัวแก้ปัญหาจะสำรวจพื้นที่คำตอบที่เป็นไปได้สำหรับจำนวนเต็ม โดยใช้การผ่อนคลาย LP ที่แต่ละโหนดและตัดกิ่งที่ไม่เป็นไปได้หรือถูกครอบงำออก
รวบรวมคำตอบที่ไม่ถูกครอบงำทั้งหมดจากการรันปัญหาย่อยเพื่อประมาณค่าหรือสร้าง Pareto front อย่างแม่นยำ คำตอบสองคำตอบจะไม่ถูกครอบงำเมื่อไม่มีคำตอบใดดีกว่าอีกคำตอบหนึ่งอย่างเคร่งครัดในทุกวัตถุประสงค์ ทำซ้ำวงจรการปรับเป็นสเกลาร์และการแก้ปัญหาด้วยพารามิเตอร์ที่หลากหลายเพื่อเพิ่มความหนาแน่นของ front
นำเสนอ Pareto front ให้กับผู้ตัดสินใจพร้อมกับการแสดงภาพประกอบ (แผนภาพกระจาย, แผนภาพพิกัดขนาน) ใช้กฎการตัดสินใจหลายเกณฑ์ ความชอบของผู้มีส่วนได้ส่วนเสีย หรือการจัดลำดับตามพจนานุกรมเพื่อเลือกคำตอบที่ต้องการจากชุดคำตอบที่ไม่ถูกครอบงำสำหรับการนำไปใช้
ข้อผิดพลาดที่พบบ่อย
- การใช้วิธีผลรวมถ่วงน้ำหนักในพื้นที่วัตถุประสงค์ที่ไม่นูนจะพลาดส่วนทั้งหมดของ Pareto front; ควรใช้วิธีข้อจำกัดเอปไซลอนหรือฟังก์ชันปรับเป็นสเกลาร์แบบบรรลุเป้าหมายที่เพิ่มขึ้นในกรณีดังกล่าว
- การถือว่าตัวแปรจำนวนเต็มเป็นแบบต่อเนื่องในการผ่อนคลายแล้วปัดเศษภายหลังไม่รับประกัน Pareto-optimality และสามารถสร้างคำตอบที่ไม่เป็นไปได้หรือถูกครอบงำได้
- การละเลยการตรวจสอบความซ้ำซ้อนของข้อจำกัดหรือความแน่นหนาก่อนการแก้ปัญหาอาจทำให้ตัวแก้ปัญหาทำงานนานเกินไปหรือรายงานความไม่เป็นไปได้ที่ผิดพลาด
- การนำเสนอคำตอบ Pareto ทั้งหมดให้ผู้ตัดสินใจโดยไม่มีการกรองหรือคำแนะนำในการแสดงภาพนำไปสู่การตัดสินใจที่หยุดชะงัก; ควรมีผลลัพธ์พร้อมกับการสนับสนุนการเลือกที่มีโครงสร้างเสมอ
- การสันนิษฐานว่า Pareto front สมบูรณ์หลังจากรันการปรับเป็นสเกลาร์น้อยเกินไปอาจนำไปสู่ข้อสรุปที่มั่นใจเกินไป; ตรวจสอบความครอบคลุมโดยการตรวจสอบการไม่ถูกครอบงำในทุกคำตอบที่รวบรวมได้
คำถามที่พบบ่อย
MO-MIP แตกต่างจากการโปรแกรมเชิงเส้นหลายวัตถุประสงค์มาตรฐานอย่างไร?
ในการโปรแกรมเชิงเส้นหลายวัตถุประสงค์ ตัวแปรตัดสินใจทั้งหมดเป็นแบบต่อเนื่อง ดังนั้นจึงสามารถหาคำตอบ Pareto ที่มีประสิทธิภาพได้ที่จุดยอดของรูปทรงหลายเหลี่ยมนูน MO-MIP กำหนดให้ตัวแปรบางตัวหรือทั้งหมดเป็นค่าจำนวนเต็ม ทำให้ชุดที่เป็นไปได้ไม่นูนและไม่ต่อเนื่อง ซึ่งต้องใช้การค้นหาแบบ branch-and-bound แทนที่จะเป็นวิธีที่ใช้ simplex
ฉันสามารถใช้ metaheuristics เช่น NSGA-II แทนตัวแก้ปัญหา MIP ที่แม่นยำได้หรือไม่?
ได้ และสำหรับปัญหาขนาดใหญ่หรือปัญหาที่ซับซ้อนเชิงการจัดหมู่ มักนิยมใช้ metaheuristics เนื่องจากปรับขนาดได้ดีกว่า ข้อเสียคือให้ Pareto fronts โดยประมาณโดยไม่มีการรับประกันความเหมาะสมที่สุด ในขณะที่ตัวแก้ปัญหา MO-MIP ที่แม่นยำรับประกันการไม่ถูกครอบงำสำหรับคำตอบที่พบ
วิธีข้อจำกัดเอปไซลอนคืออะไรและทำไมจึงแนะนำ?
วิธีข้อจำกัดเอปไซลอนจะปรับปรุงวัตถุประสงค์หนึ่งในขณะที่จำกัดวัตถุประสงค์อื่น ๆ ทั้งหมดไม่ให้แย่ไปกว่าขอบเขตที่กำหนด (epsilons) สามารถค้นหาคำตอบในภูมิภาค Pareto ที่ไม่นูนซึ่งวิธีผลรวมถ่วงน้ำหนักพลาดไปได้ ทำให้เชื่อถือได้มากกว่าสำหรับปัญหา MO-MIP ทั่วไป
ฉันควรสร้างคำตอบ Pareto กี่คำตอบ?
ขึ้นอยู่กับจำนวนวัตถุประสงค์และความละเอียดที่จำเป็นสำหรับการตัดสินใจ สำหรับสองวัตถุประสงค์ โดยทั่วไป 20-50 คำตอบที่เว้นระยะห่างเท่ากันก็เพียงพอที่จะอธิบาย front ได้ สำหรับสามวัตถุประสงค์ขึ้นไป จำนวนจะเพิ่มขึ้นแบบผสมผสาน; แนะนำให้ใช้วิธีแบบโต้ตอบหรือแบบนำโดยความชอบเพื่อหลีกเลี่ยงการมีคำตอบมากเกินไป
MO-MIP เหมาะสำหรับปัญหาที่มีความไม่แน่นอนในข้อมูลหรือไม่?
MO-MIP มาตรฐานถือว่าข้อมูลเป็นแบบกำหนด การเมื่อข้อมูลนำเข้าไม่แน่นอน ควรใช้ร่วมกับการปรับปรุงการหาค่าเหมาะที่สุดที่แข็งแกร่ง (robust optimization) หรือการโปรแกรมเชิงสุ่ม (stochastic programming) เช่น MO-MIP แบบสุ่มสองขั้นตอน หรือ MO-MIP ที่แข็งแกร่งพร้อมขอบเขตวัตถุประสงค์กรณีที่เลวร้ายที่สุด
วิธีการที่เกี่ยวข้อง
แหล่งอ้างอิง
Ehrgott, M. (2005). Multicriteria Optimization (2nd ed.). Springer, Berlin.
ISBN: 9783540213987คัดลอกแล้วMavrotas, G. (2009). Effective implementation of the epsilon-constraint method in Multi-Objective Mathematical Programming problems. Applied Mathematics and Computation, 213(2), 455-465.
เปิดเอกสารอ้างอิง DOIคัดลอกแล้ว