Materi
Program linear bilangan bulat adalah program linear dengan syarat tambahan bahwa variabelnya harus bernilai bulat; bila hanya sebagian variabel yang wajib bulat, namanya program linear bilangan bulat campuran (MILP). Kamus algoritma NIST mencatat bahwa menyelesaikan kedua jenis soal ini termasuk NP-hard, jauh lebih berat daripada program linear biasa. Coffelt dan Hendrickson (§5.3) menjelaskan akibat geometrisnya: optimum tidak lagi pasti di titik sudut, karena titik sudut umumnya berkoordinat pecahan.
SciPy menyediakan scipy.optimize.milp(c, integrality=..., bounds=..., constraints=...). Seperti linprog, milp meminimumkan, jadi maksimasi memakai c yang dinegasikan. Kendala ditulis dengan LinearConstraint(A, lb, ub), yaitu lb ≤ A @ x ≤ ub, dan integrality berisi 1 untuk variabel bulat dan 0 untuk variabel kontinu. Menurut dokumentasinya, batas nonnegatif sudah berlaku bila bounds tidak diisi.
Panduan pengguna SciPy memperlihatkan jebakannya pada soal knapsack: solusi relaksasi (tanpa syarat bulat) mengandung pecahan; dibulatkan ke atas melanggar kapasitas, dibulatkan ke bawah menjadi tidak optimum. Nilai relaksasi tetap berguna sebagai batas atas bagi soal maksimasi bulat.
import numpy as np
from scipy.optimize import milp, LinearConstraint
# maks 5x + 4y; 6x + 4y <= 24; x + 2y <= 6; x, y bulat
kendala = LinearConstraint([[6, 4], [1, 2]], -np.inf, [24, 6])
res = milp(c=[-5, -4], constraints=kendala, integrality=[1, 1])
print(res.x, -res.fun) # x = 4, y = 0, laba 20.0
# tanpa syarat bulat: x = 3, y = 1,5 dengan nilai 21