Masalah pemrograman linier bilangan bulat muncul ketika mencoba menyelesaikan sistem linier sambil menetapkan bahwa semua variabel yang tidak diketahui harus bilangan bulat, atau bilangan bulat. Sistem linier adalah kumpulan persamaan yang menggambarkan situasi di mana programmer mencoba untuk menemukan solusi. Mereka biasanya terdiri dari satu persamaan yang harus dimaksimalkan atau diminimalkan dan satu atau lebih persamaan pembatas yang membatasi variabel yang tidak diketahui. Agar sistem menjadi linier, setiap batasan harus berupa persamaan linier; artinya, variabel tersebut tidak boleh mengandung instance dari variabel yang tidak diketahui dengan eksponen lebih besar dari satu.
Pria memegang komputer
Sistem linier biasa dapat diselesaikan dengan mudah menggunakan komputer. Program dapat mengidentifikasi solusi dengan mencari turunan dan menyetelnya sama dengan nol. Kemudian dapat memverifikasi bahwa titik tersebut adalah maksimum atau minimum dengan memeriksa lingkungan terdekatnya pada fungsi tersebut. Selama turunan didefinisikan pada setiap titik di sepanjang fungsi, komputer hanya memiliki sejumlah solusi yang mungkin untuk diperiksa.
Pemrograman linier menjadi program linier bilangan bulat dengan penambahan batasan bilangan bulat. Ini berarti bahwa masalahnya tetap sama, tetapi jawabannya harus terdiri dari nilai-nilai integer untuk nilai-nilai yang tidak diketahui: mereka harus bilangan bulat. Kadang-kadang, ini berarti bahwa solusinya akan suboptimal dibandingkan dengan kasus di mana pecahan diperbolehkan; itu mencerminkan, bagaimanapun, dari dunia nyata, di mana item sering datang dalam unit terpisah dan tak terpisahkan. Hal ini membuat pemrograman linier bilangan bulat penting untuk aplikasi bisnis, karena perusahaan ingin memaksimalkan keuntungan sebanyak mungkin tetapi tidak dapat memilih untuk menjual sebagian kecil dari suatu produk.
Setelah pembatasan bilangan bulat diterapkan, masalah penyelesaian sistem linier adalah NP-lengkap. Ini berarti bahwa waktu yang diperlukan komputer untuk menyelesaikan sistem tidak dapat ditentukan. Dengan pembatasan bilangan bulat, komputer tidak dapat menggunakan alat turunan karena tidak ada jaminan bahwa titik nol turunan akan jatuh pada bilangan bulat. Solusinya adalah bilangan bulat dengan nilai tertinggi atau terendah dari semua bilangan bulat, sehingga komputer harus memeriksa semuanya — sebuah proses yang dapat memakan waktu tak terbatas.
Pemrogram telah mengembangkan heuristik, atau metode pemecahan masalah, untuk menangani kompleksitas masalah ini. Salah satu metode untuk memecahkan masalah pemrograman linier bilangan bulat adalah algoritma cabang dan terikat , di mana komputer memecahkan serangkaian masalah yang terkait dengan masalah asli untuk mempersempit rentang nilai yang tersedia menjadi satu solusi. Untuk masalah yang kompleks, bagaimanapun, ini bisa memakan waktu lama.
