Algoritma Eksak untuk Menyelesaikan Persoalan Bin Covering

Abstract

ABSTRACT This tesis present an exact algorithm for solving the problems of bin covering. Us- ing the branch and bound procedures and the technique of column generation. In the problem of integer programming, column generation is used to solve the relax- ation of linear programming. While a straightforward branch and bound approach could be adopted, for many classes of large scale problems such a procedure would be prohibitively expensive in terms of total computing time. After have adopted the approach of examining a reduced problem in which most of the integer variables are held constant and only a small subset allowed to vary in discrete steps. This may be implemented within the structure of a program by examining all integer variables at their bounds at the continuous solution as nonbasic and solving the reduced problem with these maintained nonbasic Keyword : Column generation, Branch and bound, Linear programming relaxation, Integer programming, Bin covering

ABSTRAK Tesis ini menjelaskan tentang algoritma eksak untuk menyelesaikan permasalahan bin covering. Penyelesaiannya dengan menggunakan prosedur branch and bound dan teknik generasi kolom. Dalam permasalahan integer programming, generasi kolom digunakan untuk menyelesaikan linear programming relaksasi. Branch and bound dapat digunakan untuk banyak kelas pada masalah skala besar seperti sebuah prosedur yang dapat menjadi penghalang berat dalam hal total waktu komputasi. Setelah diambil pendekatan untuk menguji pengurangan masalah dimana sebagian besar variabel integer tetap konstan dan hanya sebagian kecil diperbolehkan untuk bervariasi dalam langkah-langkah diskrit. Hal ini dapat di implementasikan dalam struktur dari sebuah program dengan memperhatikan semua variabel integer pada batas solusi yang selanjutnya sebagai non basic dan penyelesaian masalah berkurang dengan mempertahankan non basic. Kata kunci : Generasi kolom, Branch and bound, Program linear relaksasi, Integer programming, Bin covering