• การเพิ่มประสิทธิภาพจำนวนเต็ม

โจทย์การเพิ่มประสิทธิภาพเชิงเส้นที่ตัวแปรบางตัวต้องเป็นจำนวนเต็มจะเรียกว่าโปรแกรมจำนวนเต็มผสม (MIP)

ตัวแปรเหล่านี้สามารถเกิดขึ้นได้ 2 วิธีดังนี้

  • ตัวแปรที่เป็นจำนวนเต็มที่แสดงจำนวนสินค้า เช่น รถยนต์หรือชุดโทรทัศน์ และปัญหาคือการตัดสินใจเกี่ยวกับจำนวนสินค้าแต่ละรายการที่จะผลิตเพื่อเพิ่มผลกำไรสูงสุด
    โดยปกติแล้ว ปัญหานี้สามารถกำหนดเป็นปัญหาการเพิ่มประสิทธิภาพเชิงเส้นแบบมาตรฐานได้ โดยมีข้อกำหนดเพิ่มเติมว่าตัวแปรต้องเป็นจำนวนเต็ม ส่วนถัดไปแสดงตัวอย่างของปัญหาประเภทนี้

  • ตัวแปรบูลีนที่แสดงถึงการตัดสินใจที่มีค่า 0-1
    ลองดูตัวอย่างปัญหาที่เกี่ยวข้องกับการมอบหมายงานให้ผู้ปฏิบัติงาน (ดูงาน) ในการตั้งค่าปัญหาประเภทนี้ คุณกำหนดตัวแปรบูลีน xi,j ที่เท่ากับ 1 ได้หากมีการกำหนดให้ผู้ปฏิบัติงาน i เป็นงาน j และกำหนดตัวแปรบูลีนเป็น 0 ได้

เราขอแนะนำให้ดูตำราอาหารการสร้างโมเดลของ Mosek สำหรับการเพิ่มประสิทธิภาพจำนวนเต็มที่ดี

เครื่องมือ

Google มีวิธีแก้ปัญหา MIP 3 วิธีดังนี้

ฉันควรใช้เครื่องมือแก้โจทย์ปัญหาใด

ไม่มีกฎเกณฑ์ตายตัวในการตัดสินใจว่าจะใช้ตัวแก้โจทย์ MIP หรือตัวแก้ปัญหา CP-SAT โปรดดูคำแนะนำคร่าวๆ ดังนี้

  • เครื่องมือแก้โจทย์คณิต MIP เหมาะกับปัญหาที่ตั้งค่าเป็น LP มาตรฐานได้มากกว่า แต่ใช้ตัวแปรจำนวนเต็มที่กำหนดเองอย่างเช่นตัวอย่างแรกข้างต้น
  • เครื่องมือแก้โจทย์คณิต CP-SAT เหมาะกับปัญหาที่ตัวแปรส่วนใหญ่เป็นบูลีนมากกว่าอย่างเช่นตัวอย่างที่ 2 ข้างต้น

สำหรับ MIP ทั่วไปที่มีทั้งตัวแปรจำนวนเต็มและบูลีน อัตราความเร็วของเครื่องมือแก้ทั้ง 2 ตัวมักจะไม่มีความแตกต่างที่ชัดเจน จึงขึ้นอยู่กับความชอบส่วนตัว

สำหรับตัวอย่างที่ใช้ทั้งเครื่องมือแก้โจทย์ MIP และ CP-SAT โปรดดูการแก้ปัญหาเกี่ยวกับงานและส่วนการมอบหมายอื่นๆ

อีกวิธีในการแก้โจทย์การเขียนโปรแกรมจำนวนเต็มคือการใช้การแก้โจทย์โฟลว์เครือข่าย
ดูตัวอย่างได้ที่การกำหนดเป็นปัญหาโฟลว์ต้นทุนขั้นต่ำ
สำหรับปัญหาที่ตั้งค่าเป็นกระบวนการของเครือข่ายได้ เครื่องมือแก้โฟลว์ต้นทุนขั้นต่ำอาจเร็วกว่าเครื่องมือแก้โจทย์ MIP หรือ CP-SAT อย่างไรก็ตาม อาจตั้งค่า MIP บางประเภทไม่ได้ด้วยวิธีนี้