ปัญหาการเขียน โปรแกรมจำนวนเต็มหรือที่รู้จักกันในชื่อการเพิ่มประสิทธิภาพจำนวนเต็ม^{[ 1 ]}คือปัญหาการเพิ่มประสิทธิภาพทางคณิตศาสตร์หรือ โปรแกรม ความเป็นไปได้ซึ่งตัวแปรบางส่วนหรือทั้งหมดถูกจำกัดให้เป็นจำนวนเต็มในหลายกรณี คำนี้หมายถึงการเขียนโปรแกรมเชิงเส้นจำนวนเต็ม (ILP) ซึ่งฟังก์ชันวัตถุประสงค์และข้อจำกัด (นอกเหนือจากข้อจำกัดจำนวนเต็ม) เป็นเชิงเส้น

การเขียนโปรแกรมจำนวนเต็มเป็นปัญหา NP-complete ^{[ 2 ]} (ส่วนที่ยากคือการแสดงให้เห็นว่าเป็นสมาชิกของ NP ^{[ 3 ]} ) โดยเฉพาะอย่างยิ่ง กรณีพิเศษของการเขียนโปรแกรมเชิงเส้นจำนวนเต็ม 0–1 ซึ่งตัวแปรที่ไม่ทราบค่าเป็นไบนารี และต้องเป็นไปตามข้อจำกัดเท่านั้น เป็นหนึ่งใน21 ปัญหา NP-complete ของ Karp ^{[ 4 ]}

หากตัวแปรการตัดสินใจบางตัวไม่ใช่ตัวแปรแบบไม่ต่อเนื่อง ปัญหาดังกล่าวจะเรียกว่าปัญหาการเขียนโปรแกรมจำนวนเต็มแบบผสม^{[ 5 ]}

โปรแกรมเชิงเส้นจำนวนเต็มสามารถแสดงได้ทั้งในรูปแบบแคนอนิกหรือรูปแบบมาตรฐาน (ทั้งสองแบบตามที่กำหนดไว้ด้านล่าง) ซึ่งแตกต่างกัน โปรแกรมเชิงเส้นจำนวนเต็มในรูปแบบแคนอนิกแสดงได้ดังนี้ (โปรดทราบว่าเวกเตอร์เป็นสิ่งที่ต้องตัดสินใจ): ^{[ 6 ]}${\displaystyle \mathbf {x} }$

${\displaystyle {\begin{aligned}&{\underset {\mathbf {x} \in \mathbb {Z} ^{n}}{\text{maximize}}}&&\mathbf {c} ^{\mathrm {T} }\mathbf {x} \\&{\text{subject to}}&&A\mathbf {x} \leq \mathbf {b} ,\\&&&&\mathbf {x} \geq \mathbf {0} \end{aligned}}}$

และ ILP ในรูปแบบมาตรฐานจะแสดงออกมาดังนี้

${\displaystyle {\begin{aligned}&{\underset {\mathbf {x} \in \mathbb {Z} ^{n}}{\text{maximize}}}&&\mathbf {c} ^{\mathrm {T} }\mathbf {x} \\&{\text{subject to}}&&A\mathbf {x} +\mathbf {s} =\mathbf {b} ,\\&&&\mathbf {s} \geq \mathbf {0} ,\\&&&\mathbf {x} \geq \mathbf {0} ,\end{aligned}}}$

โดยที่ เป็นเวกเตอร์ และเป็นเมทริกซ์ เช่นเดียวกับโปรแกรมเชิงเส้น โปรแกรมเชิงเส้นจำนวนเต็ม (ILP) ที่ไม่ได้อยู่ในรูปแบบมาตรฐานสามารถแปลงเป็นรูปแบบมาตรฐานได้โดยการกำจัดอสมการ การแนะนำตัวแปรส่วนเกิน ( ) และการแทนที่ตัวแปรที่ไม่มีข้อจำกัดด้านเครื่องหมายด้วยผลต่างของตัวแปรสองตัวที่มีข้อจำกัดด้านเครื่องหมาย ${\displaystyle \mathbf {c} \in \mathbb {R} ^{n},\mathbf {b} \in \mathbb {R} ^{m}}$${\displaystyle A\in \mathbb {R} ^{m\times n}}$${\displaystyle \mathbf {s} }$

แผนภาพทางด้านขวามือแสดงให้เห็นถึงปัญหาดังต่อไปนี้

${\displaystyle {\begin{aligned}{\underset {x,y\in \mathbb {Z} }{\text{maximize}}}\quad &y\\{\text{subject to}}\quad &-x+y\leq 1\\&3x+2y\leq 12\\&2x+3y\leq 12\\&x,y\geq 0\end{aligned}}}$

จุดจำนวนเต็มที่เป็นไปได้แสดงด้วยสีแดง และเส้นประสีแดงแสดงถึงขอบเขต ของจุดเหล่านั้น ซึ่งเป็นรูปทรงหลายเหลี่ยมนูนที่เล็กที่สุดที่ครอบคลุมจุดทั้งหมดเหล่านี้ เส้นสีน้ำเงินพร้อมกับแกนพิกัดกำหนดรูปทรงหลายเหลี่ยมของการผ่อนคลาย LP ซึ่งกำหนดโดยอสมการโดยไม่มีข้อจำกัดเรื่องจำนวนเต็ม เป้าหมายของการหาค่าเหมาะสมที่สุดคือการเลื่อนเส้นประสีดำขึ้นไปให้ไกลที่สุดเท่าที่จะทำได้โดยยังคงสัมผัสกับรูปทรงหลายเหลี่ยม คำตอบที่ดีที่สุดของปัญหาจำนวนเต็มคือจุดและซึ่งทั้งสองจุดมีค่าเป้าหมายเท่ากับ 2 ค่าเหมาะสมที่สุดที่ไม่ซ้ำกันของการผ่อนคลายคือโดยมีค่าเป้าหมายเท่ากับ 2.8 หากปัดเศษคำตอบของการผ่อนคลายให้เป็นจำนวนเต็มที่ใกล้ที่สุด จะไม่สามารถใช้ได้กับ ILP ดูการฉายภาพลงในซิมเพล็กซ์${\displaystyle (1,2)}$${\displaystyle (2,2)}$${\displaystyle (1.8,2.8)}$

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

ให้เป็นกราฟแบบไม่มีทิศทาง กำหนดโปรแกรมเชิงเส้นดังต่อไปนี้: ${\displaystyle G=(V,E)}$

${\displaystyle {\begin{aligned}\min \sum _{v\in V}y_{v}\\y_{v}+y_{u}&\geq 1&&\forall u,v\in E\\y_{v}&\in \mathbb {Z_{0}^{+}} &&\forall v\in V\end{aligned}}}$

วิธีแก้ปัญหาที่เป็นไปได้สำหรับโปรแกรมจำนวนเต็มจะต้องไม่เป็นศูนย์บนเซตย่อยของจุดยอด ข้อจำกัดแรกบ่งชี้ว่าอย่างน้อยหนึ่งจุดปลายของขอบทุกขอบจะต้องอยู่ในเซตย่อยนี้ ดังนั้น วิธีแก้ปัญหาจึงอธิบายถึงการครอบคลุมจุดยอด นอกจากนี้ เมื่อกำหนดการครอบคลุมจุดยอด C แล้วสามารถตั้งค่าเป็น 1 สำหรับใดๆและเป็น 0 สำหรับใดๆซึ่งทำให้เราได้วิธีแก้ปัญหาที่เป็นไปได้สำหรับโปรแกรมจำนวนเต็ม ดังนั้นเราจึงสรุปได้ว่าหากเราลดผลรวมของให้เหลือน้อยที่สุดเราก็จะพบการครอบคลุมจุดยอดขั้นต่ำด้วย^{[ 7 ]}${\displaystyle y_{v}}$${\displaystyle v\in C}$${\displaystyle v\not \in C}$${\displaystyle y_{v}}$

การเขียนโปรแกรมเชิงเส้นแบบจำนวนเต็มผสม ( MILP ) เกี่ยวข้องกับปัญหาที่ตัวแปรบางตัวเท่านั้นที่ถูกจำกัดให้เป็นจำนวนเต็ม ในขณะที่ตัวแปรอื่นๆ สามารถเป็นจำนวนที่ไม่ใช่จำนวนเต็มได้ ${\displaystyle x_{i}}$

การเขียนโปรแกรมเชิงเส้นศูนย์-หนึ่ง (หรือ การ ^{เขียน}โปรแกรมจำนวนเต็มไบนารี ) เกี่ยวข้องกับปัญหาที่ตัวแปรถูกจำกัดให้เป็น 0 หรือ 1 เท่านั้น ตัวแปรจำนวนเต็มที่มีขอบเขตใดๆ ก็สามารถแสดงได้ในรูปของการรวมกันของตัวแปรไบนารี [ ^{8 ]}ตัวอย่างเช่น เมื่อกำหนดตัวแปรจำนวนเต็มตัวแปรสามารถแสดงได้โดยใช้ตัวแปรไบนารี: ${\displaystyle 0\leq x\leq U}$${\displaystyle \lfloor \log _{2}U\rfloor +1}$

$${\displaystyle x=x_{1}+2x_{2}+4x_{3}+\cdots +2^{\lfloor \log _{2}U\rfloor }x_{\lfloor \log _{2}U\rfloor +1}.}$$

มีเหตุผลหลักสองประการในการใช้ตัวแปรจำนวนเต็มเมื่อจำลองปัญหาเป็นโปรแกรมเชิงเส้น:

1. ตัวแปรจำนวนเต็มบางตัวแทนปริมาณที่สามารถเป็นจำนวนเต็มได้เท่านั้น ตัวอย่างเช่น ไม่สามารถสร้างรถยนต์ได้ 3.7 คัน
2. ตัวแปรจำนวนเต็มอื่นๆ แสดงถึงการตัดสินใจ (เช่น การตัดสินใจว่าจะรวมเส้นเชื่อมในกราฟ หรือ ไม่) ดังนั้นจึงควรมีค่าเป็น 0 หรือ 1 เท่านั้น

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

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

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

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

เป้าหมายของปัญหาเหล่านี้คือการออกแบบเครือข่ายสายส่งเพื่อติดตั้งให้ตรงตามข้อกำหนดการสื่อสารที่กำหนดไว้ล่วงหน้า และต้นทุนรวมของเครือข่ายให้น้อยที่สุด^{[ 9 ]} ซึ่งต้องอาศัยการปรับโครงสร้างเครือข่ายให้เหมาะสมที่สุดควบคู่ไปกับการกำหนดความจุของสายส่งต่างๆ ในหลายกรณี ความจุจะถูกจำกัดให้เป็นจำนวนเต็ม โดยปกติแล้วจะมีข้อจำกัดเพิ่มเติม ขึ้นอยู่กับเทคโนโลยีที่ใช้ ซึ่งสามารถจำลองได้เป็นอสมการเชิงเส้นที่มีตัวแปรจำนวนเต็มหรือไบนารี

งานวางแผนความถี่ใน เครือข่ายมือถือ GSMเกี่ยวข้องกับการกระจายความถี่ที่มีอยู่ไปยังเสาอากาศต่างๆ เพื่อให้ผู้ใช้ได้รับการบริการและลดการรบกวนระหว่างเสาอากาศให้น้อยที่สุด^{[ 10 ]} ปัญหานี้สามารถกำหนดเป็นโปรแกรมเชิงเส้นจำนวนเต็มได้ โดยที่ตัวแปรไบนารีจะระบุว่าความถี่นั้นถูกกำหนดให้กับเสาอากาศหรือไม่

• การจับคู่กระแสเงินสด
• การเพิ่มประสิทธิภาพระบบพลังงาน^{[ 11 ] [ 12 ]}
• การนำทางUAV ^{[ 13 ] [ 14 ]}
• การจัดวางแผนที่การขนส่ง^{[ 15 ]}

วิธีแก้ปัญหา ILP แบบง่ายๆ คือ การลบข้อจำกัดที่ว่าxเป็นจำนวนเต็มออกไป แก้ปัญหา LP ที่เกี่ยวข้อง (เรียกว่าการผ่อนคลาย LPของ ILP) แล้วปัดเศษค่าในคำตอบให้เข้ากับการผ่อนคลาย LP นั้น แต่คำตอบนี้อาจไม่ใช่คำตอบที่ดีที่สุด และอาจเป็นไปไม่ได้ด้วยซ้ำ กล่าวคือ อาจขัดกับข้อจำกัดบางประการ

โดยทั่วไปแล้ว แม้ว่าคำตอบของการผ่อนคลาย LP จะไม่รับประกันว่าจะเป็นจำนวนเต็ม แต่ถ้า ILP มีรูปแบบที่ โดยที่และมีสมาชิกเป็นจำนวนเต็มทั้งหมด และเป็นเมทริก ซ์เอกมอดูลาร์โดยสมบูรณ์แล้ว คำตอบพื้นฐาน ที่เป็นไปได้ ทุก คำตอบ จะเป็นจำนวนเต็ม ดังนั้น คำตอบที่ได้จากอัลกอริธึมซิมเพล็กซ์จึงรับประกันว่าเป็นจำนวนเต็ม เพื่อแสดงว่าคำตอบพื้นฐานที่เป็นไปได้ทุกคำตอบเป็นจำนวนเต็ม ให้เป็นคำตอบพื้นฐานที่เป็นไปได้ใดๆ เนื่องจากเป็นไปได้ เราจึงทราบว่าให้เป็นองค์ประกอบที่สอดคล้องกับคอลัมน์ฐานสำหรับคำตอบพื้นฐานตามคำจำกัดความของฐาน จะมีเมทริกซ์ย่อยจัตุรัสบางส่วนของ ที่มีคอลัมน์ที่เป็นอิสระเชิงเส้น เช่น นั้น${\displaystyle \max \mathbf {c} ^{\mathrm {T} }\mathbf {x} }$${\displaystyle A\mathbf {x} =\mathbf {b} }$${\displaystyle A}$${\displaystyle \mathbf {b} }$${\displaystyle A}$${\displaystyle \mathbf {x} }$${\displaystyle \mathbf {x} }$${\displaystyle A\mathbf {x} =\mathbf {b} }$${\displaystyle \mathbf {x} _{0}=[x_{n_{1}},x_{n_{2}},\cdots ,x_{n_{j}}]}$${\displaystyle \mathbf {x} }$${\displaystyle B}$${\displaystyle A}$${\displaystyle B\mathbf {x} _{0}=\mathbf {b} }$

เนื่องจากคอลัมน์ของเมทริกซ์เป็นอิสระเชิงเส้นและเป็นเมทริกซ์จัตุรัสดังนั้นเมทริกซ์จึงไม่เอกฐาน และด้วยเหตุนี้ ตามสมมติฐาน จึง เป็น เมทริกซ์เอกฐานแบบโมดูลาร์ และดังนั้นนอกจากนี้ เนื่องจากเมทริกซ์ไม่เอกฐาน จึงสามารถผกผันได้ และดังนั้น ตามนิยาม โดย ที่หมายถึงเมทริกซ์ ผกผัน ของและเป็นจำนวนเต็มเนื่องจากเป็นจำนวนเต็ม ดังนั้น ดังนั้น หากเมทริกซ์ของปัญหา ILP เป็นเมทริกซ์เอกฐานแบบโมดูลาร์โดยสมบูรณ์ แทนที่จะใช้อัลกอริทึม ILP สามารถใช้วิธีซิมเพล็กซ์ในการแก้ปัญหาการผ่อนคลาย LP และคำตอบจะเป็นจำนวนเต็ม ${\displaystyle B}$${\displaystyle B}$${\displaystyle B}$${\displaystyle B}$${\displaystyle \det(B)=\pm 1}$${\displaystyle B}$${\displaystyle \mathbf {x} _{0}=B^{-1}\mathbf {b} }$${\displaystyle B^{-1}={\frac {B^{\mathrm {adj} }}{\det(B)}}=\pm B^{\mathrm {adj} }}$${\displaystyle B^{\คณิตศาสตร์ {adj} }}$${\displaystyle B}$${\displaystyle B}$$${\displaystyle {\begin{aligned}&\Rightarrow B^{-1}=\pm B^{\mathrm {adj} }{\text{ เป็นจำนวนเต็ม}}\\&\Rightarrow \mathbf {x} _{0}=B^{-1}b{\text{ เป็นจำนวนเต็ม}}\\&\Rightarrow {\text{คำตอบที่เป็นไปได้พื้นฐานทุกคำตอบเป็นจำนวนเต็ม}}\end{aligned}}}$$${\displaystyle A}$

เมื่อเมทริกซ์ไม่เป็นเมทริกซ์เอกโมดูลาร์โดยสมบูรณ์ จะมีอัลกอริทึมหลากหลายที่สามารถใช้แก้ปัญหาโปรแกรมเชิงเส้นจำนวนเต็มได้อย่างแม่นยำ อัลกอริทึมประเภทหนึ่งคือวิธีการตัดระนาบซึ่งทำงานโดยการแก้ปัญหาการผ่อนคลายโปรแกรมเชิงเส้น (LP relaxation) แล้วเพิ่มข้อจำกัดเชิงเส้นที่ผลักดันให้คำตอบเข้าใกล้จำนวนเต็มโดยไม่ตัดจุดที่เป็นไปได้ที่เป็นจำนวนเต็มใดๆ ออกไป ${\displaystyle A}$

อัลกอริทึมอีกประเภทหนึ่งคือรูปแบบต่างๆ ของ วิธี การแยกและจำกัดขอบเขต (Branch and Bound ) ตัวอย่างเช่น วิธี การแยกและตัด (Branch and Cut)ซึ่งเป็นการผสมผสานระหว่างวิธีการแยกและจำกัดขอบเขตและวิธีการระนาบตัด อัลกอริทึมแบบแยกและจำกัดขอบเขตมีข้อดีหลายประการเหนือกว่าอัลกอริทึมที่ใช้เฉพาะระนาบตัด ข้อดีประการหนึ่งคือ อัลกอริทึมสามารถยุติการทำงานได้ก่อนกำหนด และตราบใดที่พบคำตอบที่สมบูรณ์อย่างน้อยหนึ่งคำตอบ ก็สามารถส่งคืนคำตอบที่เป็นไปได้ แม้ว่าจะไม่จำเป็นต้องเป็นคำตอบที่ดีที่สุดก็ตาม นอกจากนี้ คำตอบของการผ่อนคลาย LP สามารถใช้เพื่อประมาณค่ากรณีที่เลวร้ายที่สุดว่าคำตอบที่ส่งคืนนั้นอยู่ห่างจากค่าที่เหมาะสมที่สุดมากน้อยเพียงใด สุดท้าย วิธีการแยกและจำกัดขอบเขตสามารถใช้เพื่อส่งคืนคำตอบที่เหมาะสมที่สุดหลายคำตอบได้

สมมติว่าเป็น เมทริกซ์จำนวนเต็มขนาด m x nและเป็น เวกเตอร์จำนวนเต็มขนาด m x 1 เราจะมุ่งเน้นไปที่ปัญหาความเป็นไปได้ ซึ่งก็คือการตัดสินใจว่ามี เวกเตอร์ขนาด n x 1 ที่สอดคล้องกับเงื่อนไข หรือ ไม่ ${\displaystyle A}$${\displaystyle \mathbf {b} }$${\displaystyle \mathbf {x} }$${\displaystyle A\mathbf {x} \leq \mathbf {b} }$

ให้Vเป็นค่าสัมบูรณ์สูงสุดของสัมประสิทธิ์ใน และถ้าn (จำนวนตัวแปร) เป็นค่าคงที่ ปัญหาความเป็นไปได้สามารถแก้ไขได้ในเวลาที่เป็นพหุนามในmและ log Vซึ่งเป็นเรื่องง่ายสำหรับกรณีn = 1 กรณีn = 2 ได้รับการแก้ไขในปี 1981 โดยHerbert Scarf [ ^{16 ] กรณี}ทั่วไปได้รับการแก้ไขในปี 1983 โดยHendrik LenstraโดยการรวมแนวคิดของLászló LovászและPeter van Emde Boas [ ^{17 ] ทฤษฎีบท}ของ Doignonยืนยันว่าโปรแกรมจำนวนเต็มมีความเป็นไปได้เมื่อใดก็ตามที่เซตย่อยของข้อจำกัดทุกเซตมีความเป็นไปได้ วิธีการที่รวมผลลัพธ์นี้กับอัลกอริทึมสำหรับปัญหาประเภท LPสามารถใช้เพื่อแก้โปรแกรมจำนวนเต็มในเวลาที่เป็นเชิงเส้นในและสามารถจัดการได้ด้วยพารามิเตอร์คงที่ (FPT) ในแต่เป็นไปได้ว่าจะเป็นเลขชี้กำลังสองเท่าในโดยไม่ขึ้นอยู่กับ^{[ 18 ]}${\displaystyle A}$${\displaystyle \mathbf {b} }$${\displaystyle 2^{n}}$${\displaystyle m}$${\displaystyle n}$${\displaystyle n}$${\displaystyle V}$

ในกรณีพิเศษของ 0-1 ILP อัลกอริทึมของ Lenstra เทียบเท่ากับการแจงนับแบบสมบูรณ์: จำนวนคำตอบที่เป็นไปได้ทั้งหมดถูกกำหนดไว้ (2 ⁿ ) และการตรวจสอบความเป็นไปได้ของแต่ละคำตอบสามารถทำได้ในเวลา poly( m , log V ) ในกรณีทั่วไปที่แต่ละตัวแปรสามารถเป็นจำนวนเต็มใดๆ การแจงนับแบบสมบูรณ์เป็นไปไม่ได้ ในที่นี้ อัลกอริทึมของ Lenstra ใช้แนวคิดจากเรขาคณิตของจำนวนมันแปลงปัญหาดั้งเดิมให้เป็นปัญหาที่เทียบเท่ากันโดยมีคุณสมบัติดังต่อไปนี้: การมีอยู่ของคำตอบนั้นชัดเจน หรือค่าของ( ตัวแปรที่ n ) อยู่ในช่วงที่มีความยาวจำกัดโดยฟังก์ชันของnในกรณีหลัง ปัญหาจะลดลงเหลือจำนวนปัญหาที่มีมิติที่ต่ำกว่าจำนวนจำกัด ความซับซ้อนของเวลาการทำงานของอัลกอริทึมได้รับการปรับปรุงในหลายขั้นตอน: ${\displaystyle \mathbf {x} }$${\displaystyle x_{n}}$

• อัลกอริทึมดั้งเดิมของ Lenstra ^{[ 17 ]} มี เวลาทำงาน${\displaystyle 2^{O(n^{3})}\cdot (m\cdot \log V)^{O(1)}}$
• Kannan ^{[ 19 ]} นำเสนออัลกอริทึมที่ได้รับการปรับปรุงพร้อมเวลาการทำงาน^{[ 20 ]}${\displaystyle n^{O(n)}\cdot (m\cdot \log V)^{O(1)}}$
• แฟรงค์และทาร์ดอส^{[ 21 ]} นำเสนออัลกอริทึมที่ได้รับการปรับปรุง พร้อมรันไทม์ ^{[ 22 ] [ 23 ] : Prop.8} ${\displaystyle n^{2.5n}\cdot 2^{O(n)}\cdot (m\cdot \log V)^{O(1)}}$
• Dadush ^{[ 24 ]} นำเสนออัลกอริทึมที่ได้รับการปรับปรุง พร้อมรันไทม์${\displaystyle n^{n}\cdot 2^{O(n)}\cdot (m\cdot \log V)^{O(1)}}$
• Reis และ Rothvoss ^{[ 25 ]} นำเสนออัลกอริทึมที่ได้รับการ ปรับปรุง ด้วยรันไทม์${\displaystyle (\log n)^{O(n)}\cdot (m\cdot \log V)^{O(1)}}$

อัลกอริทึมเหล่านี้ยังสามารถใช้กับโปรแกรมเชิงเส้นจำนวนเต็มแบบผสม (MILP) ได้อีกด้วย ซึ่งเป็นโปรแกรมที่ตัวแปรบางตัวเป็นจำนวนเต็มและตัวแปรบางตัวเป็นจำนวนจริง^{[ 26 ]}อัลกอริทึมดั้งเดิมของ Lenstra ^{[ 17 ] : ส่วนที่ 5} มีเวลาทำงานโดยที่ n คือจำนวนตัวแปรจำนวนเต็ม d คือจำนวนตัวแปรต่อเนื่อง และLคือขนาดการเข้ารหัสไบนารีของปัญหา การใช้เทคนิคจากอัลกอริทึมในภายหลัง ปัจจัยสามารถปรับปรุงเป็นหรือ เป็นได้^{[ 26 ]}${\displaystyle 2^{O(n^{3})}\cdot poly(d,L)}$${\displaystyle 2^{O(n^{3})}}$${\displaystyle 2^{O(n\log n)}}$${\displaystyle n^{n}}$

เนื่องจากการเขียนโปรแกรมเชิงเส้นจำนวนเต็มเป็นปัญหาNP-hardทำให้ปัญหาหลายกรณีไม่สามารถแก้ไขได้ ดังนั้นจึงต้องใช้วิธีการฮิวริสติกแทน ตัวอย่างเช่นสามารถใช้การค้นหาแบบแทบู เพื่อค้นหาคำตอบสำหรับ ILP ได้ ^{[ 27 ]} ในการใช้การค้นหาแบบแทบูเพื่อแก้ปัญหา ILP สามารถกำหนดการเคลื่อนไหวเป็นการเพิ่มหรือลดค่าตัวแปรจำนวนเต็มที่ถูกจำกัดของคำตอบที่เป็นไปได้ ในขณะที่รักษาตัวแปรจำนวนเต็มที่ถูกจำกัดอื่นๆ ทั้งหมดให้คงที่ จากนั้นจึงแก้หาค่าตัวแปรที่ไม่ถูกจำกัด หน่วยความจำระยะสั้นสามารถประกอบด้วยคำตอบที่เคยลองมาก่อน ในขณะที่หน่วยความจำระยะกลางสามารถประกอบด้วยค่าของตัวแปรจำนวนเต็มที่ถูกจำกัดซึ่งส่งผลให้ได้ค่าเป้าหมายสูง (โดยสมมติว่า ILP เป็นปัญหาการเพิ่มค่าสูงสุด) สุดท้าย หน่วยความจำระยะยาวสามารถนำทางการค้นหาไปยังค่าจำนวนเต็มที่ยังไม่เคยลองมาก่อน

วิธีการเชิงฮิวริสติกอื่นๆ ที่สามารถนำมาใช้กับ ILP ได้แก่

• การปีนเขา
• การอบอ่อนจำลอง
• การเพิ่มประสิทธิภาพการค้นหาแบบตอบสนอง
• การเพิ่มประสิทธิภาพอาณานิคมมด
• เครือข่ายประสาทฮอปฟิลด์

นอกจากนี้ยังมีวิธีการฮิวริสติกเฉพาะปัญหาอื่นๆ อีกมากมาย เช่นวิธีการฮิวริสติก k-optสำหรับปัญหาพนักงานขายเดินทาง ข้อเสียของวิธีการฮิวริสติกคือ หากวิธีการเหล่านี้ไม่สามารถหาคำตอบได้ ก็ไม่สามารถระบุได้ว่าเป็นเพราะไม่มีคำตอบที่เป็นไปได้ หรือว่าอัลกอริทึมไม่สามารถหาคำตอบได้ นอกจากนี้ โดยทั่วไปแล้วเป็นไปไม่ได้ที่จะวัดว่าคำตอบที่ได้จากวิธีการเหล่านี้ใกล้เคียงกับคำตอบที่เหมาะสมที่สุดมากน้อยเพียงใด

โดย ทั่วไปแล้ว เมทริกซ์ที่กำหนดโปรแกรมจำนวนเต็มมักจะเป็น เมทริก ซ์เบาบางโดยเฉพาะอย่างยิ่ง เมื่อเมทริกซ์มีโครงสร้างแบบบล็อกซึ่งเป็นกรณีในแอปพลิเคชันหลายๆ แอปพลิเคชัน ความเบาบางของเมทริกซ์สามารถวัดได้ดังนี้กราฟของมีจุดยอดที่สอดคล้องกับคอลัมน์ของและสองคอลัมน์จะสร้างขอบกันหากมีแถวที่ทั้งสองคอลัมน์มีค่าไม่เป็นศูนย์ หรือกล่าวอีกนัยหนึ่ง จุดยอดจะสอดคล้องกับตัวแปร และสองตัวแปรจะสร้างขอบกันหากตัวแปรทั้งสองมีอสมการร่วมกันการวัดความเบาบางของคือค่าต่ำสุดของความลึกของต้นไม้ของกราฟของและความลึกของต้นไม้ของกราฟของเมทริกซ์สลับตำแหน่งของ ให้เป็นการวัดเชิงตัวเลขของซึ่งกำหนดเป็นค่าสัมบูรณ์สูงสุดของรายการใดๆ ของให้ เป็นจำนวนตัวแปรของโปรแกรมจำนวนเต็ม จากนั้นในปี 2018 ^{[ 28 ]}แสดงให้เห็นว่าการเขียนโปรแกรมจำนวนเต็มสามารถแก้ไขได้ในเวลา ที่สามารถจัดการได้ ด้วยพหุนามอย่างเข้มแข็งและพารามิเตอร์คงที่ โดย กำหนด พารามิเตอร์ด้วย และกล่าวคือ สำหรับฟังก์ชันที่คำนวณได้บางฟังก์ชันและค่าคงที่บางค่าการเขียนโปรแกรมเชิงจำนวนเต็มสามารถแก้ไขได้ในเวลาโดยเฉพาะอย่างยิ่ง เวลาจะไม่ขึ้นอยู่กับด้านขวามือและฟังก์ชันเป้าหมายยิ่งไปกว่านั้น เมื่อเปรียบเทียบกับผลลัพธ์แบบคลาสสิกของ Lenstra ซึ่งจำนวนตัวแปรเป็นพารามิเตอร์ ในที่นี้จำนวนตัวแปรเป็นส่วนหนึ่งของข้อมูลนำเข้า ${\displaystyle A}$${\displaystyle A}$${\displaystyle A}$${\displaystyle A}$${\displaystyle d}$${\displaystyle A}$${\displaystyle A}$${\displaystyle A}$${\displaystyle a}$${\displaystyle A}$${\displaystyle A}$${\displaystyle n}$${\displaystyle a}$${\displaystyle d}$${\displaystyle f}$${\displaystyle k}$${\displaystyle f(a,d)n^{k}}$${\displaystyle b}$${\displaystyle c}$${\displaystyle n}$${\displaystyle n}$

• กำลังสองน้อยที่สุดแบบมีข้อจำกัด
• สมการไดโอแฟนไทน์  – สมการพหุนามที่ต้องการหาคำตอบที่เป็นจำนวนเต็ม

• George L. Nemhauser ; Laurence A. Wolsey (1988). การเพิ่มประสิทธิภาพเชิงจำนวนเต็มและเชิงการจัดเรียง . Wiley. ISBN 978-0-471-82819-8.
• Alexander Schrijver (1998). ทฤษฎีการเขียนโปรแกรมเชิงเส้นและจำนวนเต็ม . John Wiley and Sons. ISBN 978-0-471-98232-6.
• ลอเรนซ์ เอ. วอลซีย์ (1998). การเขียนโปรแกรมจำนวนเต็ม . ไวลีย์. ISBN 978-0-471-28366-9.
• Dimitris Bertsimas; Robert Weismantel (2005). การหาค่าเหมาะสมที่สุดบนจำนวนเต็ม . Dynamic Ideas. ISBN 978-0-9759146-2-5.
• John K. Karlof (2006). การเขียนโปรแกรมเชิงจำนวนเต็ม: ทฤษฎีและการปฏิบัติ . สำนักพิมพ์ CRC. ISBN 978-0-8493-1914-3.
• H. Paul Williams (2009). ตรรกศาสตร์และการเขียนโปรแกรมจำนวนเต็ม . Springer. ISBN 978-0-387-92279-9.
• Michael Jünger; Thomas M. Liebling; Denis Naddef; George Nemhauser ; William R. Pulleyblank ; Gerhard Reinelt; Giovanni Rinaldi; Laurence A. Wolsey, บรรณาธิการ (2009). 50 ปีแห่งการเขียนโปรแกรมจำนวนเต็ม 1958-2008: จากยุคเริ่มต้นสู่ยุคล้ำสมัย . Springer. ISBN 978-3-540-68274-5.
• Der-San Chen; Robert G. Batson; Yu Dang (2010). การเขียนโปรแกรมเชิงจำนวนเต็มประยุกต์: การสร้างแบบจำลองและการแก้ปัญหา . John Wiley and Sons. ISBN 978-0-470-37306-4.
• เจอราร์ด เซียร์กสมา; โยริ ซวอลส์ (2015) การเพิ่มประสิทธิภาพเชิงเส้นและจำนวนเต็ม: ทฤษฎีและการปฏิบัติ ซีอาร์ซี เพรส. ไอเอสบีเอ็น 978-1-498-71016-9.
• François Clautiaux; Ivana Ljubić (2024). "ห้าสิบปีที่ผ่านมาของการเขียนโปรแกรมเชิงเส้นจำนวนเต็ม: มุ่งเน้นไปที่ความก้าวหน้าในทางปฏิบัติล่าสุด"วารสารยุโรปด้านการวิจัยเชิงปฏิบัติการ 324 ( 3). INRIA : 707– 731. doi : 10.1016/j.ejor.2024.11.018 .บทความภาพรวม

• บทแนะนำเกี่ยวกับการเขียนโปรแกรมเชิงจำนวนเต็ม
• การประชุมการเขียนโปรแกรมจำนวนเต็มและการเพิ่มประสิทธิภาพเชิงการจัดเรียง (IPCO)
• การประชุมเชิงปฏิบัติการการเพิ่มประสิทธิภาพเชิงการจัดเรียงแบบออสซัวส์