Skip to content
กลับไปยังผลการค้นหา

การโปรแกรมจำนวนเต็ม (Integer Programming — IP) และการโปรแกรมจำนวนเต็มแบบผสม (Mixed-Integer Programming — MIP)

ผู้เสนอ
Ralph Gomory (cutting planes, 1958); land-and-doig branch-and-bound (1960)
ปี
1958
ประเภท
Mathematical optimisation — exact combinatorial method

ข้อความนี้เป็นการแปลด้วยเครื่องและยังไม่ได้รับการตรวจทาน อ่านต้นฉบับภาษาอังกฤษ

ขนาดตัวอักษร

ใช้ทำอะไร?

การโปรแกรมจำนวนเต็ม (IP) หรือที่เรียกว่าการโปรแกรมจำนวนเต็มแบบผสม (MIP) เมื่อตัวแปรบางตัวเท่านั้นถูกจำกัดให้เป็นจำนวนเต็ม เป็นสาขาหนึ่งของการหาค่าเหมาะที่สุดทางคณิตศาสตร์ ซึ่งตัวแปรตัดสินใจบางตัวหรือทั้งหมดจะต้องเป็นจำนวนเต็มหรือค่าไบนารี การโปรแกรมจำนวนเต็มต่อยอดมาจากการโปรแกรมเชิงเส้น โดยได้รับการวางกรอบอย่างเป็นทางการผ่านระเบียบวิธีระนาบตัด (cutting-plane method) ของ Ralph Gomory (1958) และขั้นตอนวิธี Branch-and-Bound ของ Land and Doig (1960) และตั้งแต่นั้นมาก็กลายเป็นกรอบการทำงานที่แม่นยำมาตรฐานสำหรับปัญหาการจัดตารางเวลา การมอบหมายงาน การกำหนดเส้นทาง และการจัดสรรทรัพยากร

แนวคิดเบื้องหลังวิธีการ

การโปรแกรมเชิงเส้นทั่วไปจะค้นหาจุดที่ดีที่สุดในขอบเขตที่เป็นไปได้แบบต่อเนื่อง แต่การตัดสินใจจริงหลายอย่างเป็นแบบไม่ต่อเนื่อง เช่น คุณไม่สามารถจัดพยาบาล 2.7 คน หรือเปิดคลังสินค้าครึ่งเดียวได้ การโปรแกรมจำนวนเต็มเพิ่มข้อจำกัดว่าตัวแปรบางตัวหรือทั้งหมดต้องเป็นจำนวนเต็ม (หรือตัวเลือกไบนารี 0/1) ราคาของข้อจำกัดนั้นคือการคำนวณ: เซตที่เป็นไปได้ไม่ได้เป็นพื้นผิวเรียบอีกต่อไป แต่เป็นเซตของจุดที่กระจัดกระจาย และการค้นหาจุดที่ดีที่สุดอาจต้องตรวจสอบจำนวนคำตอบที่เป็นไปได้จำนวนมหาศาล ตัวแก้ปัญหาจัดการสิ่งนี้โดยการแบ่งปัญหาออกเป็นปัญหาย่อยที่เล็กลงอย่างชาญฉลาด (branching) และการตัดกิ่งที่ไม่สามารถเอาชนะคำตอบที่ดีที่สุดที่พบได้จนถึงขณะนั้น (bounding) ในขณะเดียวกันก็ทำให้การประมาณค่าแบบต่อเนื่องมีความแม่นยำยิ่งขึ้นผ่านอสมการที่เพิ่มเข้ามา (cutting planes)

ประวัติศาสตร์

การโปรแกรมจำนวนเต็มเกิดขึ้นในช่วงปลายทศวรรษ 1950 เมื่อนักวิจัยพยายามขยายการโปรแกรมเชิงเส้นไปสู่การตัดสินใจแบบไม่ต่อเนื่อง Ralph Gomory ได้นำเสนอระเบียบวิธีระนาบตัดอย่างเป็นระบบในปี 1958 โดยพิสูจน์ว่าโปรแกรมจำนวนเต็มใดๆ สามารถแก้ไขได้โดยการเพิ่ม cuts จำนวนจำกัด Land และ Doig (1960) ได้วางกรอบ Branch-and-Bound ซึ่งกลายเป็นขั้นตอนวิธีที่แม่นยำที่โดดเด่น Wolsey (1998) และ Nemhauser และ Wolsey (1988) ได้ให้ตำราเรียนที่เป็นมาตรฐานที่สาขายังคงพึ่งพาอยู่ การปฏิวัติในทางปฏิบัติเกิดขึ้นพร้อมกับการพัฒนาตัวแก้ปัญหา Branch-and-Cut ในทศวรรษ 1990 ซึ่งรวมทั้งสองเทคนิคเข้ากับฮิวริสติกขั้นสูง และต่อมาด้วยการระเบิดของประสิทธิภาพของตัวแก้ปัญหาเชิงพาณิชย์และโอเพนซอร์สที่ช่วยให้สามารถใช้งานจริงขนาดใหญ่ได้ในปัจจุบัน

ควรใช้เมื่อใด

ใช้การโปรแกรมจำนวนเต็มเมื่อการตัดสินใจเป็นแบบไม่ต่อเนื่องโดยธรรมชาติ — ตัวเลือกใช่/ไม่ใช่แบบไบนารี, ปริมาณจำนวนเต็ม, หรือข้อจำกัดตรรกะเปิด/ปิด — และเมื่อคุณต้องการคำตอบที่เหมาะสมที่สุดที่แม่นยำหรือใกล้เคียงกับความแม่นยำพร้อมกับขอบเขตคุณภาพที่พิสูจน์ได้ เหมาะสำหรับการจัดตารางเวลา, การมอบหมายพนักงานและทรัพยากร, การกำหนดเส้นทางยานพาหนะ, การเลือกที่ตั้งโรงงาน, การจัดทำงบประมาณลงทุน, และการเลือกพอร์ตการลงทุน ไม่มีข้อกำหนดขนาดตัวอย่างขั้นต่ำเนื่องจาก IP เป็นกรอบการทำงานการหาค่าเหมาะที่สุดแบบกำหนดค่าได้ (deterministic optimisation framework) ไม่ใช่กระบวนการอนุมานทางสถิติ ประเภทตัวแปรสามารถเป็นไบนารี, จัดหมวดหมู่ (เข้ารหัสเป็นไบนารี), หรือต่อเนื่อง (ในกรณีจำนวนเต็มแบบผสม) ข้อกำหนดที่สำคัญในทางปฏิบัติคือปัญหาต้องสามารถจำลองได้ด้วยฟังก์ชันวัตถุประสงค์เชิงเส้นและข้อจำกัดเชิงเส้น หากฟังก์ชันวัตถุประสงค์หรือข้อจำกัดไม่เป็นเชิงเส้น จะต้องใช้ส่วนขยายการโปรแกรมจำนวนเต็มแบบผสมที่ไม่เป็นเชิงเส้น (MINLP)

ข้อจำกัดและข้อควรพิจารณา

  • การโปรแกรมจำนวนเต็มเป็นปัญหา NP-hard โดยทั่วไป; เวลาในการแก้ปัญหาอาจเพิ่มขึ้นแบบทวีคูณตามขนาดของปัญหาและการกำหนดสูตรที่ไม่ดี
  • LP relaxation ที่อ่อนแอ (ช่องว่างความเป็นจำนวนเต็มขนาดใหญ่) นำไปสู่แผนภูมิต้นไม้การค้นหาที่ลึกและมีค่าใช้จ่ายสูง และใช้เวลานาน
  • การขยายไบนารีของตัวแปรจัดหมวดหมู่ที่มีจำนวนสมาชิกมากอาจทำให้ขนาดของโมเดลใหญ่ขึ้นมาก
  • สำหรับกรณีขนาดใหญ่มาก ตัวแก้ปัญหาอาจต้องยุติการทำงานก่อนกำหนดด้วยค่าความคลาดเคลื่อนของช่องว่าง แทนที่จะบรรลุช่องว่างเป็นศูนย์

เงื่อนไขจากแหล่งที่มาไม่สามารถใช้แทนการทบทวนทางวิทยาศาสตร์ที่เป็นอิสระหรือการตรวจสอบโดยเอนจินวิเคราะห์ได้

จุดแข็ง

  • ให้คำตอบที่เหมาะสมที่สุดที่แม่นยำพร้อมกับช่องว่างค่าเหมาะที่สุดที่รับรองได้ ซึ่งแตกต่างจากฮิวริสติกที่ไม่มีการรับประกันคุณภาพ
  • จัดการตัวแปรไบนารีและตัวแปรจำนวนเต็มทั่วไปได้อย่างเป็นธรรมชาติ ทำให้เป็นกรอบการทำงานที่เหมาะสมสำหรับการตัดสินใจแบบผสมผสาน
  • สามารถนำไปใช้กับปัญหาโดเมนที่หลากหลาย — การจัดตารางเวลา, การกำหนดเส้นทาง, การมอบหมายงาน, ปัญหาเป้สะพายหลัง — ด้วยกลไกทางคณิตศาสตร์เดียวกัน
  • ตัวแก้ปัญหาแบบ Branch-and-Cut ที่ทันสมัยสามารถแก้ปัญหาที่มีตัวแปรและข้อจำกัดนับล้าน ซึ่งเคยเป็นไปไม่ได้เมื่อหลายทศวรรษที่แล้ว

การประยุกต์ใช้

  • การจัดตารางเวลาพนักงานและพยาบาล — การมอบหมายกะเพื่อตอบสนองความต้องการการครอบคลุมในขณะที่เคารพกฎระเบียบชั่วโมงการทำงาน
  • การกำหนดเส้นทางยานพาหนะและโลจิสติกส์ — การค้นหาเส้นทางการจัดส่งที่มีต้นทุนต่ำสุดภายใต้ข้อจำกัดด้านความจุและกรอบเวลา
  • การเลือกที่ตั้งโรงงาน — การตัดสินใจว่าจะเปิดคลังสินค้าหรือโรงงานใดเพื่อลดต้นทุนการจัดจำหน่ายทั้งหมด
  • การจัดทำงบประมาณลงทุน — การเลือกพอร์ตการลงทุนภายในงบประมาณเพื่อเพิ่มผลตอบแทนรวมสูงสุด
  • การวางแผนการผลิต — การกำหนดขนาดล็อตจำนวนเต็มในช่วงเวลาต่างๆ เพื่อรักษาสมดุลระหว่างต้นทุนการติดตั้งและต้นทุนการเก็บรักษา
  • การออกแบบเครือข่าย — การเลือกการเชื่อมโยงที่จะติดตั้งในเครือข่ายการสื่อสารหรือการขนส่ง

วิธีการทำงาน

วิธีการทำงาน

1

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

2

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

3

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

4

ระนาบตัด (cutting planes) คืออสมการเชิงเส้นที่ถูกต้องซึ่งตัดส่วนหนึ่งของขอบเขตที่เป็นไปได้ของ LP-relaxation ออกไป โดยไม่ลบจุดที่เป็นไปได้ที่เป็นจำนวนเต็มออกไป การเพิ่ม cuts ที่แข็งแกร่ง (Gomory cuts, cover inequalities, clique cuts) จะทำให้ขอบเขต LP กระชับขึ้นและลดจำนวนโหนดที่ตัวแก้ปัญหาต้องสำรวจ

5

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

ข้อผิดพลาดที่พบบ่อย

  • การประกาศตัวแปรเป็นแบบต่อเนื่องในขณะที่ควรเป็นจำนวนเต็ม — หรือในทางกลับกัน — จะทำให้เกิดคำตอบที่ผิดพลาดโดยไม่รู้ตัว; ควรตรวจสอบเสมอว่าประเภทตัวแปรตรงกับความเป็นจริงทางกายภาพของปัญหา
  • การกำหนดสูตรที่หลวมซึ่งมีช่องว่าง LP relaxation ขนาดใหญ่ทำให้เกิดการแตกกิ่งมากเกินไป; ควรลงทุนเวลาในการกระชับการกำหนดสูตร (อสมการที่แข็งแกร่ง, การทำลายสมมาตร) ก่อนที่จะแก้ปัญหา
  • การละเลยช่องว่างความเป็นจำนวนเต็มในผลลัพธ์ของตัวแก้ปัญหา: ค่าวัตถุประสงค์ที่รายงานเป็นเพียงคำตอบจำนวนเต็มที่ดีที่สุดที่พบ ไม่จำเป็นต้องเป็นค่าเหมาะที่สุดทั่วโลก เว้นแต่ช่องว่างจะเป็นศูนย์
  • การนำ IP ไปใช้กับปัญหาที่ฟังก์ชันวัตถุประสงค์หรือข้อจำกัดไม่เป็นเชิงเส้นโดยไม่มีการจัดการ MINLP ที่เหมาะสมจะทำให้ได้โมเดลที่ไม่ถูกต้อง
  • สำหรับปัญหาการจัดตารางเวลาหรือการกำหนดเส้นทาง การไม่เพิ่มอสมการที่ถูกต้อง (เช่น clique หรือ cover cuts) ทำให้สูญเสียประสิทธิภาพที่สำคัญไป

คำถามที่พบบ่อย

ความแตกต่างระหว่าง IP และ MIP คืออะไร?

ในการโปรแกรมจำนวนเต็มบริสุทธิ์ (IP) ตัวแปรตัดสินใจทุกตัวต้องเป็นจำนวนเต็ม ในการโปรแกรมจำนวนเต็มแบบผสม (MIP) ตัวแปรบางตัวเป็นจำนวนเต็มหรือไบนารี ในขณะที่ตัวแปรอื่นๆ สามารถเป็นแบบต่อเนื่องได้ MIP เป็นกรอบการทำงานที่ทั่วไปกว่าและใช้บ่อยกว่าในทางปฏิบัติ เนื่องจากปัญหาจริงส่วนใหญ่ผสมผสานการเลือกแบบไม่ต่อเนื่องเข้ากับปริมาณแบบต่อเนื่อง

ทำไมการโปรแกรมจำนวนเต็มจึงเป็น NP-hard ในเมื่อการโปรแกรมเชิงเส้นเป็นแบบพหุนาม?

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

ฉันจะรู้ได้อย่างไรว่าคำตอบของฉันเหมาะสมที่สุด?

ตัวแก้ปัญหาจะรายงานช่องว่างค่าเหมาะที่สุด (optimality gap) — ความแตกต่างเป็นเปอร์เซ็นต์ระหว่างคำตอบจำนวนเต็มที่ดีที่สุดที่พบและขอบเขตล่างที่เหลือที่ดีที่สุด ช่องว่าง 0% รับรองค่าเหมาะที่สุดทั่วโลก สำหรับปัญหาขนาดใหญ่ คุณอาจกำหนดค่าความคลาดเคลื่อนของช่องว่าง (เช่น 1%) และยอมรับคำตอบที่ใกล้เคียงค่าเหมาะที่สุด; ขอบเขตยังคงรับประกันว่าค่าเหมาะที่สุดที่แท้จริงจะไม่ดีไปกว่าเปอร์เซ็นต์นั้น

อะไรทำให้การกำหนดสูตร 'กระชับ' และทำไมจึงสำคัญ?

การกำหนดสูตรที่กระชับคือการกำหนดสูตรที่ LP relaxation ให้ขอบเขตที่ใกล้เคียงกับค่าเหมาะที่สุดจำนวนเต็ม ทำให้มีช่องว่างความเป็นจำนวนเต็มเล็กน้อย เมื่อช่องว่างมีขนาดเล็ก Branch-and-Bound จำเป็นต้องสำรวจโหนดน้อยลงและยุติการทำงานเร็วขึ้น การเพิ่มอสมการที่ถูกต้อง เช่น Gomory cuts, cover inequalities, หรือ clique cuts จะทำให้การกำหนดสูตรกระชับขึ้น และมักเป็นวิธีที่มีผลกระทบมากที่สุดในการเร่งความเร็วของตัวแก้ปัญหา

วิธีการที่เกี่ยวข้อง

แหล่งอ้างอิง

  1. Wolsey, L.A. (1998). Integer Programming. Wiley.

    ISBN: 9780471283669
    คัดลอกแล้ว
  2. Nemhauser, G.L. & Wolsey, L.A. (1988). Integer and Combinatorial Optimization. Wiley.

    ISBN: 9780471359432
    คัดลอกแล้ว