February 14, 2005

Karakterisasi Metode Numerik Baru Untuk Menyelesaikan Masalah Optimisasi Tak Tentu Yang Melibatkan Variabel Biner

Dr. Diah Chaerani, M.Si. Dr. H. Sudrajat, MS Firdaniza, M.Si Fakultas: MIPA Sumberdana: FUNDAMENTAL Tahun: 2009 Abstrak: Berbagai masalah disain sesungguhnya merupakan masalah optimisasi. Penekanan utama penelitian ini berada pada pemodelan beberapa masalah disain yang robas, yaitu masalah-masalah yang berkenaan dengan mencari suatu solusi optimal dari suatu masalah disain tak tentu. Tujuan yang hendak dicapai adalah penggunaan metodologi Robust Counterpart seperti yang diusulkan oleh Ben-Tal dan Nemirovskii [1]. Robust counterpart ini merepresentasikan suatu pendekatan yang berorientasi pada kasus terbaik dari yang terburuk, yaitu mencari suatu solusi fisibel yang robas. Ini berarti bahwa solusi tersebut memenuhi kendala teknologi untuk semua nilai yang mungkin dalam data tak tentu. Diasumsikan bahwa data berada pada suatu himpunan tak tentu ellipsoid. Dalam kasus ini, Robust counterpart dari suatu masalah pemrograman linier membentuk suatu masalah optimisasi kuadratik konik (yang dapat diselesaikan dengan menggunakan metode interior point). Dalam beberapa kasus spesifik seperti Robust Shortest Path Problem [9], robust counterpart memuat variabel biner. Masalah ini secara umum tidaklah computationally tractable, karena diperlukan suatu skema branch and bound untuk menyelesaikan masalahnya. Sehingga diperlukan pembentukan suatu algoritma yang lebih efisien dengan mengeksploitasi struktur khusus. Dalam penelitian ini, diusulkan untuk menyelesaikan masalah dengan menggunakan pendekatan relaksasi semidefinite dengan cara mengelaborasikan relaksasi semidefinit seperti yang diusulkan oleh Poljak et al [11] dan oleh Ben-Tal & Nemirovskii [2]. Suatu formulasi relaksasi semidefinit untuk masalah kuadratik konik dengan variabel biner disajikan dalam penelitian ini. Kata kunci: Metode Numerik, Optimasi, Varibel Biner

Artikel terkait