Integer programming — การโปรแกรมเชิงจำนวนเต็ม

การโปรแกรมเชิงจำนวนเต็ม (ЦП; อังกฤษ integer programming, IP) — เป็นสาขาหนึ่งของการหาค่าเหมาะที่สุดทางคณิตศาสตร์ ซึ่งศึกษาปัญหาที่ตัวแปรบางส่วนหรือทั้งหมดต้องรับเฉพาะค่าจำนวนเต็มเท่านั้น

กรณีพิเศษที่ได้รับการศึกษามากที่สุดคือ การโปรแกรมเชิงเส้นจำนวนเต็ม (ЦЛП; อังกฤษ integer linear programming, ILP) ซึ่งฟังก์ชันวัตถุประสงค์และข้อจำกัดเป็นเชิงเส้น ต่างจากการโปรแกรมเชิงเส้นที่ตัวแปรสามารถรับค่าจำนวนจริงใดก็ได้ ข้อกำหนดความเป็นจำนวนเต็มทำให้ปัญหาการโปรแกรมเชิงจำนวนเต็มมีความซับซ้อนในการแก้ไขมากขึ้นอย่างมีนัยสำคัญ

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

นิยามและคำศัพท์

ปัญหาทั่วไปของการโปรแกรมเชิงเส้นจำนวนเต็มสามารถเขียนได้ดังนี้:

หาเวกเตอร์ $x$ ซึ่ง:

หาค่าสูงสุด (หรือต่ำสุด) ของ $c^{T}x$

ภายใต้เงื่อนไข:

$Ax\le b$

$x\ge 0$

$x\in {\mathbb{Z}}^n$ (ทุกองค์ประกอบของเวกเตอร์ $x$ เป็นจำนวนเต็ม)

โดยที่ $x$ คือเวกเตอร์ของตัวแปร, $c$ และ $b$ คือเวกเตอร์, และ $A$ คือเมทริกซ์สัมประสิทธิ์

ขึ้นอยู่กับข้อกำหนดของตัวแปร ปัญหาแบ่งออกเป็นประเภทต่าง ๆ ดังนี้:

• การโปรแกรมเชิงจำนวนเต็มทั้งหมด: ตัวแปรทั้งหมดต้องเป็นจำนวนเต็ม
• การโปรแกรมเชิงจำนวนเต็มผสม (อังกฤษ mixed-integer programming, MIP): เฉพาะบางส่วนของตัวแปรเท่านั้นที่ต้องเป็นจำนวนเต็ม
• การโปรแกรมแบบบูลีน (0-1): ตัวแปรรับค่าได้เพียง 0 หรือ 1 เท่านั้น ซึ่งช่วยให้สามารถจำลองการตัดสินใจเชิงตรรกะแบบ «ใช่/ไม่ใช่» ได้

คุณสมบัติสำคัญและความซับซ้อน

ความซับซ้อนเชิงการคำนวณ

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

ความสัมพันธ์กับการโปรแกรมเชิงเส้น (การผ่อนคลาย LP)

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

1. สามารถหาได้เร็วกว่ามาก (ในเวลาพหุนาม)
2. ค่าที่เหมาะที่สุดของฟังก์ชันวัตถุประสงค์จากการผ่อนคลาย LP ให้ขอบเขต (ขอบบนสำหรับปัญหาการหาค่าสูงสุดและขอบล่างสำหรับปัญหาการหาค่าต่ำสุด) สำหรับค่าที่เหมาะที่สุดของปัญหาจำนวนเต็มต้นฉบับ

อย่างไรก็ตาม การปัดเศษคำตอบเศษส่วนของการผ่อนคลาย LP ให้เป็นจำนวนเต็มที่ใกล้เคียงที่สุดโดยตรง โดยทั่วไปแล้วไม่นำไปสู่คำตอบที่เหมาะที่สุดหรือแม้แต่คำตอบที่เป็นไปได้ของปัญหาจำนวนเต็ม

คุณสมบัติ Totally Unimodular

มีประเภทปัญหาการโปรแกรมเชิงเส้นจำนวนเต็มที่สำคัญซึ่งสามารถแก้ได้ง่ายพอ ๆ กับการผ่อนคลาย LP ของตัวเอง นั่นคือปัญหาที่เมทริกซ์ข้อจำกัด $A$ เป็น totally unimodular (กล่าวคือ ดีเทอร์มิแนนต์ของเมทริกซ์ย่อยสี่เหลี่ยมจัตุรัสใด ๆ ของมันเท่ากับ 0, +1 หรือ −1) หากเมทริกซ์ $A$ เป็น totally unimodular และเวกเตอร์ $b$ เป็นจำนวนเต็ม จุดยอดทั้งหมดของรูปหลายเหลี่ยมของคำตอบที่เป็นไปได้จากการผ่อนคลาย LP จะเป็นจำนวนเต็มโดยอัตโนมัติ ดังนั้น คำตอบที่หาได้โดยวิธีซิมเพล็กซ์จะเป็นจำนวนเต็ม ตัวอย่างของปัญหาเหล่านี้ได้แก่ ปัญหาการขนส่งและปัญหาการมอบหมายงาน

วิธีการแก้ปัญหา

สำหรับการแก้ปัญหาการโปรแกรมเชิงจำนวนเต็มทั่วไปที่ไม่มีคุณสมบัติ totally unimodular ได้มีการพัฒนาวิธีการที่แม่นยำโดยอาศัยแนวคิดการค้นหาแบบไม่ชัดแจ้ง

• วิธีสาขาและขอบเขต (อังกฤษ Branch and Bound) — วิธีการที่แม่นยำหลัก อาศัยการแบ่งเซตของคำตอบที่เป็นไปได้อย่างเป็นระบบออกเป็นเซตย่อย (การแตกสาขา) และการตัดทิ้งเซตย่อยที่แน่นอนว่าไม่มีคำตอบที่เหมาะที่สุด สำหรับการประเมินความมีแนวโน้มของเซตย่อยจะใช้การผ่อนคลาย LP

• วิธีระนาบตัด (วิธีของ Gomory; อังกฤษ Cutting Plane Method) — แนวทางเชิงวนซ้ำที่เพิ่มข้อจำกัดเชิงเส้นใหม่ («การตัด») ให้กับปัญหาอย่างต่อเนื่อง การตัดเหล่านี้ «ตัดออก» คำตอบเศษส่วนของการผ่อนคลาย LP โดยไม่กระทบคำตอบจำนวนเต็มที่เป็นไปได้ใด ๆ เพื่อค่อย ๆ ทำให้บริเวณคำตอบที่เป็นไปได้ของการผ่อนคลาย LP เข้าใกล้เปลือกนูนของคำตอบจำนวนเต็ม

ตัวแก้ปัญหาสมัยใหม่โดยทั่วไปใช้อัลกอริทึมแบบผสมผสาน เช่น วิธีสาขาและตัด (อังกฤษ Branch and Cut) ซึ่งรวมข้อดีของทั้งสองแนวทางเข้าด้วยกัน

ตัวอย่างและพื้นที่การประยุกต์ใช้

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

• ปัญหากระเป๋าเป้ (Knapsack Problem): ปัญหาคลาสสิกของการโปรแกรม 0-1 ที่ต้องเลือกชุดของสิ่งของที่มีมูลค่ารวมสูงสุดโดยไม่เกินข้อจำกัดด้านน้ำหนักรวม
• ปัญหาพนักงานขาย (Travelling Salesman Problem): ปัญหาการหาเส้นทางสั้นที่สุดที่ผ่านชุดเมืองที่กำหนด สามารถกำหนดเป็นปัญหาการโปรแกรมเชิงจำนวนเต็มได้ โดยตัวแปรจะรับผิดชอบการรวมขอบของกราฟในเส้นทางสุดท้าย

ด้วยความยืดหยุ่นของมัน การโปรแกรมเชิงจำนวนเต็มจึงเป็นหนึ่งในเครื่องมือที่เป็นที่ต้องการมากที่สุดในการวิจัยเชิงปฏิบัติการ และมีการประยุกต์ใช้ในสาขาต่าง ๆ เช่น:

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

ดูเพิ่มเติม

• การโปรแกรมเชิงเส้น
• วิธีสาขาและขอบเขต

หมายเหตุ

</references>