การโปรแกรมจำนวนเต็มเชิงกำหนด — การหาค่าเหมาะที่สุดแบบแม่นยำด้วยตัวแปรตัดสินใจจำนวนเต็ม
- ผู้เสนอ
- Ralph E. Gomory
- ปี
- 1958
- ประเภท
- Exact combinatorial optimization
- กลุ่มวิธี
- Simulation / optimization
ข้อความนี้เป็นการแปลด้วยเครื่องและยังไม่ได้รับการตรวจทาน อ่านต้นฉบับภาษาอังกฤษ
ใช้ทำอะไร?
การโปรแกรมจำนวนเต็มเชิงกำหนด (Deterministic Integer Programming หรือ DIP) เป็นแนวทางการหาค่าเหมาะที่สุดทางคณิตศาสตร์ที่ค้นหาคำตอบที่ดีที่สุดสำหรับปัญหาที่ตัวแปรตัดสินใจบางส่วนหรือทั้งหมดต้องเป็นจำนวนเต็ม โดยมีข้อมูลวัตถุประสงค์และข้อจำกัดที่ทราบอย่างสมบูรณ์ (เชิงกำหนด) เป็นรูปแบบคลาสสิกที่ไม่ใช่เชิงสุ่มของการโปรแกรมจำนวนเต็ม ซึ่งเป็นรากฐานสำคัญของการวิจัยดำเนินงานและการหาค่าเหมาะที่สุดเชิงการจัดหมู่มาตั้งแต่ปลายทศวรรษ 1950
แนวคิดเบื้องหลังวิธีการ
การตัดสินใจในโลกแห่งความเป็นจริงจำนวนมากเป็นแบบไม่ต่อเนื่องโดยธรรมชาติ: คุณจะเปิดหรือไม่เปิดโรงงาน คุณจะมอบหมายหรือไม่มอบหมายพนักงานเข้ากะ วิธีการหาค่าเหมาะที่สุดแบบต่อเนื่องไม่สามารถบังคับใช้ข้อกำหนดจำนวนเต็มเหล่านี้ได้ การโปรแกรมจำนวนเต็มเชิงกำหนดจัดการปัญหานี้โดยจำกัดตัวแปรให้เป็นจำนวนเต็ม ในขณะที่พารามิเตอร์ปัญหาทั้งหมด — ต้นทุน, ขีดความสามารถ, ความต้องการ — ทราบได้อย่างแน่นอน ผลลัพธ์ที่ได้คือคำตอบที่แม่นยำและสามารถพิสูจน์ได้ว่าเหมาะสมที่สุดภายใต้สมมติฐานความแน่นอนนั้น ทำให้เป็นสูตรอ้างอิงที่ใช้เปรียบเทียบกับรูปแบบเชิงสุ่มและรูปแบบที่แข็งแกร่ง
ประวัติศาสตร์
การโปรแกรมจำนวนเต็มเกิดขึ้นจากการโปรแกรมเชิงเส้นในช่วงปลายทศวรรษ 1950 อัลกอริทึมระนาบตัดของ Ralph Gomory ในปี 1958 เป็นวิธีการที่แม่นยำและเป็นระบบวิธีแรก ควบคู่ไปกับการแตกกิ่งและขอบเขต (Land and Doig, 1960) แนวทางเหล่านี้ได้กำหนดขอบเขตของสาขาวิชานี้ คำคุณศัพท์ 'เชิงกำหนด' ใช้เพื่อแยกความแตกต่างของสูตรคลาสสิกจากการโปรแกรมจำนวนเต็มเชิงสุ่ม (Birge and Louveaux, 1997) และกลายเป็นคำศัพท์มาตรฐานเมื่อรูปแบบที่คำนึงถึงความไม่แน่นอนแพร่หลายมากขึ้น
ควรใช้เมื่อใด
ใช้การโปรแกรมจำนวนเต็มเชิงกำหนดเมื่อ: (1) ตัวแปรตัดสินใจเป็นแบบไม่ต่อเนื่องโดยธรรมชาติ (การมอบหมาย, การจัดตารางเวลา, การกำหนดที่ตั้งโรงงาน, การจัดเรียงสิ่งของลงกล่อง, การออกแบบเครือข่าย); (2) พารามิเตอร์ปัญหาทั้งหมดทราบอย่างแน่นอนหรือสามารถประมาณค่าเป็นจุดได้อย่างน่าเชื่อถือ; (3) ต้องการคำตอบที่เหมาะสมที่สุดแบบแม่นยำมากกว่าการประมาณค่าแบบฮิวริสติก ห้ามใช้เมื่อ: พารามิเตอร์ไม่แน่นอนหรือขึ้นอยู่กับสถานการณ์ (ให้ใช้การโปรแกรมจำนวนเต็มเชิงสุ่มหรือแบบแข็งแกร่งแทน); ขนาดของปัญหาใหญ่มากจนการแตกกิ่งและขอบเขตไม่สามารถคำนวณได้ในทางปฏิบัติและยอมรับฮิวริสติกได้; ตัวแปรเป็นแบบต่อเนื่องอย่างแท้จริง (ให้ใช้ LP); หรือต้องรักษาสมดุลของวัตถุประสงค์ที่ขัดแย้งกันหลายอย่างพร้อมกัน (ให้ใช้การโปรแกรมจำนวนเต็มหลายวัตถุประสงค์)
ข้อจำกัดและข้อควรพิจารณา
- สมมติว่าพารามิเตอร์ปัญหาทั้งหมดทราบอย่างแม่นยำ — ความไม่แน่นอนในโลกแห่งความเป็นจริงถูกละเลยโดยเจตนา
- เป็นปัญหา NP-hard โดยทั่วไป; เวลาในการแก้ปัญหาในกรณีที่เลวร้ายที่สุดจะเพิ่มขึ้นแบบทวีคูณตามขนาดของปัญหา
- ปัญหาเชิงการจัดหมู่ขนาดใหญ่อาจต้องใช้เวลาคำนวณหลายชั่วโมงหรือหลายวันแม้จะใช้ตัวแก้ปัญหาที่ทันสมัย
- คุณภาพของการกำหนดแบบจำลอง (ความกระชับของข้อจำกัด, การทำลายสมมาตร) มีผลอย่างมากต่อเวลาในการแก้ปัญหา
เงื่อนไขจากแหล่งที่มาไม่สามารถใช้แทนการทบทวนทางวิทยาศาสตร์ที่เป็นอิสระหรือการตรวจสอบโดยเอนจินวิเคราะห์ได้
จุดแข็ง
- รับประกันคำตอบที่เหมาะสมที่สุดที่สามารถพิสูจน์ได้ภายใต้สมมติฐานของแบบจำลองเชิงกำหนด
- จัดการโครงสร้างการตัดสินใจแบบไม่ต่อเนื่องเชิงการจัดหมู่ที่วิธีการต่อเนื่องไม่สามารถทำได้โดยธรรมชาติ
- ได้รับการสนับสนุนจากตัวแก้ปัญหาเชิงพาณิชย์และโอเพนซอร์สที่มีประสิทธิภาพสูงและเป็นที่ยอมรับ (CPLEX, Gurobi, SCIP)
- ให้ใบรับรองช่องว่างการหาค่าเหมาะที่สุด ทำให้สามารถยุติการทำงานก่อนกำหนดได้อย่างมีหลักการสำหรับกรณีขนาดใหญ่
- ทำหน้าที่เป็นเกณฑ์มาตรฐานทองคำสำหรับการเปรียบเทียบฮิวริสติกและรูปแบบเชิงสุ่ม
การประยุกต์ใช้
- การวางแผนการผลิตและการจัดตารางเวลาด้วยทรัพยากรเครื่องจักรหรือแรงงานแบบไม่ต่อเนื่อง
- การกำหนดที่ตั้งโรงงาน: การตัดสินใจว่าจะเปิดคลังสินค้าหรือโรงงานใด
- การกำหนดเส้นทางยานพาหนะและการจัดตารางเวลาพนักงานขับรถในการขนส่งและโลจิสติกส์
- การจัดทำงบประมาณลงทุน: การเลือกกลุ่มโครงการลงทุนที่ไม่สามารถแบ่งแยกได้
- การออกแบบเครือข่ายโทรคมนาคมด้วยต้นทุนการจัดตั้งลิงก์ที่คงที่
- การจัดตารางเวรพนักงานในโรงพยาบาลและการจัดตารางเวลาห้องผ่าตัด
วิธีการทำงาน
วิธีการทำงาน
กำหนดแบบจำลองการหาค่าเหมาะที่สุด: ฟังก์ชันวัตถุประสงค์ที่ต้องการลดค่า (หรือเพิ่มค่า) ในรูปผลรวมเชิงเส้นของตัวแปรตัดสินใจจำนวนเต็ม ภายใต้ชุดของข้อจำกัดเชิงเส้นแบบอสมการหรือสมการ สัมประสิทธิ์ทั้งหมด (c, A, b) ถูกกำหนดและทราบค่า — นี่คือสิ่งที่ทำให้สูตรเป็นเชิงกำหนด ตัวแปรไบนารี (0/1) เป็นกรณีพิเศษสำหรับการตัดสินใจแบบใช่/ไม่ใช่
สูตร
\min \; c^\top x \quad \text{s.t.} \quad Ax \leq b,\; x \geq 0,\; x \in \mathbb{Z}^nแก้ปัญหาการผ่อนปรนเชิงเส้น (LP relaxation) ซึ่งอนุญาตให้ตัวแปรมีค่าต่อเนื่องได้ชั่วคราว สิ่งนี้ให้ขอบเขตล่างของค่าวัตถุประสงค์จำนวนเต็มที่เหมาะสมที่สุด หากคำตอบของการผ่อนปรนเชิงเส้นเป็นจำนวนเต็มอยู่แล้ว ก็ถือว่าเหมาะสมที่สุดสำหรับ IP; มิฉะนั้นจะเริ่มการแตกกิ่ง
สูตร
\text{Solve LP relaxation: } \min \; c^\top x \quad \text{s.t.} \quad Ax \leq b,\; x \geq 0เลือกตัวแปรที่เป็นเศษส่วนจากคำตอบของการผ่อนปรนเชิงเส้น และแบ่งขอบเขตที่เป็นไปได้โดยการเพิ่มข้อจำกัดขอบเขตล่าง (x_j <= ค่าขอบเขตล่าง) ในกิ่งหนึ่ง และข้อจำกัดขอบเขตบน (x_j >= ค่าขอบเขตบน) ในอีกกิ่งหนึ่ง สร้างปัญหาย่อยสองปัญหาที่จะต้องแก้ไขแบบเรียกซ้ำ
สูตร
\text{Select fractional variable } x_j^*. \text{ Create two subproblems: } x_j \leq \lfloor x_j^* \rfloor \text{ and } x_j \geq \lceil x_j^* \rceilแก้ปัญหาการผ่อนปรนเชิงเส้นของปัญหาย่อยแต่ละปัญหาเพื่อหาขอบเขต หากขอบเขตของโหนดใดแย่กว่าคำตอบจำนวนเต็มที่ดีที่สุดที่ทราบ (incumbent) ให้ตัดโหนดนั้นทิ้ง หากปัญหาย่อยให้คำตอบที่เป็นไปได้เชิงจำนวนเต็มที่ดีกว่า incumbent ให้ปรับปรุง incumbent กระบวนการนี้จะสร้างโครงสร้างต้นไม้การค้นหาแบบแตกกิ่งและขอบเขต
สูตร
\text{Compute bounds; prune nodes where LP bound} \geq \text{incumbent. Update best integer solution.}วิธีการระนาบตัด (Cutting-plane methods) — ที่โดดเด่นที่สุดคือ Gomory cuts — ได้มาซึ่งอสมการเชิงเส้นเพิ่มเติมจากตาราง LP ที่สอดคล้องกับคำตอบจำนวนเต็มทั้งหมด แต่ไม่สอดคล้องกับคำตอบ LP ที่เป็นเศษส่วนในปัจจุบัน การเพิ่ม cuts เหล่านี้จะทำให้การผ่อนปรนเชิงเส้นกระชับขึ้นและลดการแตกกิ่ง ตัวแก้ปัญหาที่ทันสมัยรวมการแตกกิ่งและขอบเขตเข้ากับ cuts ในกรอบการทำงานแบบ branch-and-cut
สูตร
\text{Optionally add Gomory cuts or problem-specific valid inequalities to tighten LP relaxation.}อัลกอริทึมจะสิ้นสุดเมื่อโหนดที่เปิดอยู่ทั้งหมดถูกตัดทิ้งหรือให้คำตอบจำนวนเต็ม incumbent ณ การสิ้นสุดคือคำตอบจำนวนเต็มที่สามารถพิสูจน์ได้ว่าเหมาะสมที่สุด ตัวแก้ปัญหายังรายงานช่องว่างระหว่างขอบเขตที่ดีที่สุดกับ incumbent ซึ่งสามารถใช้เป็นเกณฑ์การหยุดสำหรับปัญหาขนาดใหญ่ได้
สูตร
\text{Return optimal integer solution } x^* \text{ with objective value } z^* = c^\top x^*ข้อผิดพลาดที่พบบ่อย
- การถือว่าพารามิเตอร์ที่ไม่แน่นอนเป็นการประมาณค่าแบบจุดเชิงกำหนดอาจให้คำตอบที่ทำงานได้ไม่ดีในทางปฏิบัติ — ตรวจสอบสมมติฐานนี้ก่อนนำ DIP ไปใช้
- การผ่อนปรนเชิงเส้นที่อ่อนแอ (ช่องว่างจำนวนเต็มขนาดใหญ่) นำไปสู่โครงสร้างต้นไม้แบบแตกกิ่งและขอบเขตขนาดมหึมา; ลงทุนในอสมการที่ถูกต้องและการปรับสูตรใหม่ก่อนที่จะขยายขนาด
- การระเบิดของตัวแปรไบนารีจากการกำหนดสูตรแบบ big-M อาจทำให้การผ่อนปรนเชิงเส้นไม่เสถียรในเชิงตัวเลข; ควรเลือกการปรับสูตรข้อจำกัดที่กระชับกว่า
- ความเข้าใจผิดระหว่างความเป็นไปได้กับความเป็นค่าเหมาะที่สุดเมื่อใช้ค่าความคลาดเคลื่อนช่องว่างที่ไม่เป็นศูนย์ — ควรรายงานช่องว่างควบคู่ไปกับค่าวัตถุประสงค์เสมอ
- การละเลยสมมาตรในแบบจำลอง (เช่น เครื่องจักรหรือพนักงานที่เหมือนกัน) ทำให้เกิดการแตกกิ่งที่ซ้ำซ้อน; เพิ่มข้อจำกัดการทำลายสมมาตร
คำถามที่พบบ่อย
อะไรคือความแตกต่างระหว่างการโปรแกรมจำนวนเต็มเชิงกำหนดกับการโปรแกรมจำนวนเต็มเชิงสุ่ม?
ในการโปรแกรมจำนวนเต็มเชิงกำหนด พารามิเตอร์วัตถุประสงค์และข้อจำกัดทั้งหมดจะถูกกำหนดและทราบค่า การโปรแกรมจำนวนเต็มเชิงสุ่มจะจำลองพารามิเตอร์ที่ไม่แน่นอนอย่างชัดเจนผ่านการแจกแจงความน่าจะเป็นหรือสถานการณ์ต่างๆ ทำให้ได้คำตอบที่แข็งแกร่งหรือเหมาะสมที่สุดโดยเฉลี่ยในสถานการณ์เหล่านั้น การโปรแกรมจำนวนเต็มเชิงกำหนดนั้นง่ายกว่าและเร็วกว่าในการแก้ปัญหา แต่ละเลยความไม่แน่นอน
การโปรแกรมไบนารีเป็นกรณีพิเศษของการโปรแกรมจำนวนเต็มหรือไม่?
ใช่ การโปรแกรมไบนารี (0-1) จำกัดตัวแปรตัดสินใจแต่ละตัวให้เป็น {0, 1} เป็นกรณีพิเศษที่พบบ่อยที่สุด ใช้สำหรับการตัดสินใจแบบใช่/ไม่ใช่ เช่น จะเปิดโรงงานหรือไม่ เลือกโครงการหรือไม่ หรือมอบหมายพนักงานหรือไม่ การโปรแกรมจำนวนเต็มทั่วไปอนุญาตให้มีค่าจำนวนเต็มที่ไม่เป็นลบใดๆ
ฉันควรเปลี่ยนจากการโปรแกรมจำนวนเต็มเชิงกำหนดไปใช้วิธีฮิวริสติกเมื่อใด?
เมื่อโครงสร้างต้นไม้แบบแตกกิ่งและขอบเขตมีขนาดใหญ่เกินไปที่จะสำรวจได้ภายในเวลาที่ยอมรับได้ และช่องว่างการหาค่าเหมาะที่สุดจากฮิวริสติกที่ดี (เช่น อัลกอริทึมเชิงพันธุกรรม, การจำลองการอบอ่อน, การค้นหาแบบเพื่อนบ้านขนาดใหญ่) เป็นที่ยอมรับได้สำหรับการประยุกต์ใช้ รายงานและให้เหตุผลช่องว่างเมื่อเบี่ยงเบนจากการหาค่าเหมาะที่สุดแบบแม่นยำ
การโปรแกรมจำนวนเต็มเชิงกำหนดสามารถจัดการวัตถุประสงค์หรือข้อจำกัดที่ไม่เป็นเชิงเส้นได้หรือไม่?
การโปรแกรมจำนวนเต็มเชิงกำหนดแบบคลาสสิกสมมติความเป็นเชิงเส้น (การโปรแกรมเชิงเส้นจำนวนเต็ม) การโปรแกรมจำนวนเต็มที่ไม่เป็นเชิงเส้นมีอยู่แต่ยากกว่ามาก รูปแบบที่ไม่เป็นเชิงเส้นหลายรูปแบบสามารถทำให้เป็นเชิงเส้นได้ผ่านตัวแปรไบนารีเสริมและการปรับสูตรแบบ big-M การโปรแกรมจำนวนเต็มกำลังสอง (QIP) ได้รับการสนับสนุนโดยตรงจากตัวแก้ปัญหาที่ทันสมัยบางตัว
ฉันควรใช้ตัวแก้ปัญหาใดสำหรับการโปรแกรมจำนวนเต็มเชิงกำหนดในทางปฏิบัติ?
เชิงพาณิชย์: Gurobi หรือ IBM CPLEX เพื่อประสิทธิภาพที่ดีที่สุด เชิงวิชาการ/โอเพนซอร์ส: SCIP, CBC (ผ่าน COIN-OR) หรือ HiGHS ทั้งหมดนี้ใช้การแตกกิ่งและตัดพร้อมการประมวลผลล่วงหน้าอัตโนมัติ สำหรับผู้ใช้ Python, PuLP, Pyomo หรือ scipy.optimize.milp มีอินเทอร์เฟซการสร้างแบบจำลองที่สะดวก
วิธีการที่เกี่ยวข้อง
แหล่งอ้างอิง
Gomory, R. E. (1958). Outline of an algorithm for integer solutions to linear programs. Bulletin of the American Mathematical Society, 64(5), 275-278.
เปิดเอกสารอ้างอิง DOIคัดลอกแล้วWolsey, L. A. (1998). Integer Programming. Wiley-Interscience, New York.
ISBN: 9780471283669คัดลอกแล้ว