|
Masalah program bilangan bulat (integer programming problem/IP) adalah masalah program linear yang semua atau beberapa variabelnya harus merupakan bilangan bulat nonnegatif.
Macam-macam integer programming:
- Program bilangan bulat murni, menghendaki semua variabelnya harus bilangan bulat nonnegatif.
- Program bilangan bulat campuran, beberapa variabelnya harus bilangan bulat nonnegatif.
- Program bilangan bulan 0-1 adalah IP yang menghendaki semua variabel harus 0 atau 1.
Algoritma cabang dan batas (branch and bound) merupakan salah satu algoritma yang dapat diselesaikan dengan program bilangan bulat murni.
Langkah:
- Dibentuk submasalah I, yaitu submasalah yang didapat dari PL dengan syarat mutlak x1 > 0.
- Pilih salah satu penyelesaian optimal yang berbentuk pecahan (katakan xi).
- Tentukan range dari penyelesaian optimal tersebut, misalkan a < xi < a + 1. Kemudian submasalah I dicabangkan menjadi 2 submasalah, dengan ketentuan:
i. Submasalah 2
Submasalah 1 + kendala xi ≥ a + 1
ii. Submasalah 3
Submasalah 1 + kendala xi ≤ a
Submasalah tidak dicabangkan jika
- Infeasibel
- Penyelesaian optimal sudah integer
- Nilai optimal z melebihi z awal, untuk kasus memaksimalkan sedangkan nilai optimal z kurang dari z awal, untuk kasus meminimalkan.
