พื้นที่ทดลองโปรแกรมจำนวนเต็ม
แก้โปรแกรมเชิงเส้นจำนวนเต็มขนาดเล็กด้วย branch-and-bound แบบแม่นตรงและดูทุกโหนดของการค้นหา จะรายงานว่าจุดดีที่สุดพิสูจน์แล้วว่าเหมาะที่สุดก็ต่อเมื่อสำรวจต้นไม้ครบ
โปรแกรมจำกัดที่ 4,000 อักขระ 40 บรรทัด 8 ตัวแปร และข้อจำกัด 8 ข้อที่มีตัวแปรอย่างน้อยสองตัว ขีดจำกัดโหนดคือ 1 ถึง 5,000 และการค้นหาหยุดเมื่อครบ 3,000,000 ขั้นการคำนวณแม่นตรง คำนวณบนอุปกรณ์ใน worker เบื้องหลัง จำกัด 15 วินาที ดาวน์โหลดรายงาน JSON และ CSV โหนดได้ บรรทัดแรกให้ระบุ maximize หรือ minimize และฟังก์ชันวัตถุประสงค์ จากนั้นใส่ข้อจำกัดบรรทัดละหนึ่งข้อ สูงสุด 4,000 ตัวอักษร ตรวจสอบการตั้งค่าก่อนเริ่มประมวลผล
ผลลัพธ์ของคุณ
พื้นที่ทดลองโปรแกรมจำนวนเต็ม
- เขียนวัตถุประสงค์ในบรรทัดแรก เช่น maximize 5x + 4y
- เพิ่มข้อจำกัดบรรทัดละหนึ่งข้อ เช่น ขอบเขต x, y >= 0 และบรรทัดเสริมอย่าง integer x หรือ binary z โดยใช้ตัวแปรจากโปรแกรม
- กำหนดขีดจำกัดโหนดแล้วเริ่มค้นหา
- อ่านสถานะ คำตอบดีที่สุดปัจจุบัน ขอบเขตที่ดีที่สุดและช่องว่าง จากนั้นดาวน์โหลดรายงาน JSON หรือ CSV โหนด
สิ่งที่ควรทราบ
โปรแกรมจำกัดที่ 4,000 อักขระ 40 บรรทัด 8 ตัวแปร และข้อจำกัด 8 ข้อที่มีตัวแปรอย่างน้อยสองตัว ขีดจำกัดโหนดคือ 1 ถึง 5,000 และการค้นหาหยุดเมื่อครบ 3,000,000 ขั้นการคำนวณแม่นตรง คำนวณบนอุปกรณ์ใน worker เบื้องหลัง จำกัด 15 วินาที ดาวน์โหลดรายงาน JSON และ CSV โหนดได้
วิธีแตกกิ่งและกำหนดขอบเขต
แต่ละโหนดแก้ปัญหาผ่อนคลายเชิงเส้นอย่างแม่นตรงด้วยวิธีซิมเพล็กซ์ ตัวแปรจำนวนเต็มที่มีค่าเป็นเศษส่วนแบ่งเป็นสองแขนงคือ x <= floor และ x >= ceiling จะตัดโหนดเมื่อปัญหาผ่อนคลายเป็นไปไม่ได้หรือไม่อาจดีกว่าจุดจำนวนเต็มที่ดีที่สุดที่พบแล้ว วิธี: Wolsey, Integer Programming, ฉบับที่ 2, บทที่ 7 (2020)
ความหมายของการพิสูจน์แล้ว
เมื่อแก้หรือใช้ขอบเขตแม่นตรงตัดทุกโหนดแล้ว จะพิสูจน์ได้ว่าคำตอบดีที่สุดปัจจุบันเหมาะที่สุด หรือพิสูจน์ว่าปัญหาเป็นไปไม่ได้ หากขีดจำกัดโหนดหรืองบขั้นตอนหยุดการค้นหาก่อน incumbent เป็นเพียงจุดดีที่สุดที่พบจนถึงขณะนั้น และรายงานจะแสดงขอบเขตที่ดีที่สุดกับช่องว่างระหว่างกัน
กฎอินพุต
ตัวแปรเป็นจำนวนเต็ม เว้นแต่ระบุบางตัวด้วย integer x, y ซึ่งกรณีนั้นตัวแปรที่เหลือจะเป็นจำนวนต่อเนื่อง ข้อจำกัดตัวแปรเดียวกลายเป็นขอบเขต หากปัญหาผ่อนคลายไม่มีขอบเขต การค้นหาจะหยุด เพราะโปรแกรมจำนวนเต็มอาจไม่มีขอบเขตหรือเป็นไปไม่ได้