Pemrograman linier (PL) bilangan bulat merupakan bentuk khusus dari pemrograman linier dengan seluruh variabel keputusan berupa bilangan bulat. Salah satu metode yang digunakan dalam menyelesaikan masalah PL bilangan bulat adalah metode branch and bound (B&B). Tugas akhir ini membahas metode perbaikan B&B, yaitu melakukan beberapa tahapan sebelum mengimplementasikan metode B&B. Tahapan yang dilakukan dalam metode perbaikan B&B adalah memperkecil daerah layak dan menghilangkan kendala redundant. Metode ini bekerja secara efisien saat menyelesaikan masalah PL bilangan bulat dengan banyaknya kendala jauh lebih besar dibandingkan banyaknya variabel. Percobaan numerik yang dilakukan menunjukkan tingkat efisiensi dari metode perbaikan B&B sebesar 85% dalam menyelesaikan permasalahan PL bilangan bulat dengan banyaknya kendala 235 lebih besar dari banyaknya variabel.

---

Integer linear programming problem is a special form of linear programming with all the decision variables are integers. Branch and bound is one of the methods for solving an integer linear programming problem. This skripsi discusses an improved branch and bound method, which adding several steps before implementing the branch and bound method. New steps in the improved branch and bound method are narrowing down the feasible solution range and removing the redundant constraints.

This method works efficiently in solving an integer linear programming problem with the number of constraints are much more than the number of variables. Numerical experiments show that the efficiency of improved B&B method is about 85% for solving an integer linear programming problem with the number of constraints 235 more than the variables.