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