Pustaka Ilmiah Universitas Padjadjaran

Abstrak

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

Berbagai masalah disain sesungguhnya merupakan masalah optimisasi. Penekanan utama dalam laporan ini berada pada pemodelan beberapa masalah disain yang robas, yaitu masalah-masalah yang berkenaan dengan mencari suatu solusi optimal dari suatu msalah 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 smeua nilai yang mungkin dalam data tak tentu. Diasumsikan bahwa data berada pada suatu himpunan taktentu 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 denga mengeksploitasi struktur khusus. Dalam laporan 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 laporan penelitian ini.

Many design problems are in fact optimization problems. The main emphasis in this paper is on modelling some robust design problems, i.e., problems that deal with _nding a robust optimal solution of an uncertain design problem. Our aim is to use the robust counterpart (RC) Methodology of Ben-Tal and Nemirovskii [1]. The robust counterpart represents the best worst-case oriented approach: a solution is robust feasible only if the solution satis_es the technological constraints for all possible values of the uncertainty data. We assume that the data belongs to an ellipsoidal uncertainty set. In this case, the robust counterpart of a linear optimization problem leads to a conic quadratic optimization problem (which can be solved efficiently by using interior-point methods). In some specific problems such as the robust shortest path problem [9], the robust counterpart contains binary variables. This problem is in general not computationally tractable, since we need a branch and bound scheme to solve the problem. Therefore we need to develop a more efficient algorithm by exploiting the special structure. We intend to solve the problem approximately via a semide_nite relaxation. We elaborate the semidefinite relaxations as proposed by Poljak et al. [11] and by Ben-Tal and Nemirovkii [2]. A semidefinite relaxation formulation for conic quadratic problem with binary variables is presented.

Pustaka Terkait

• Tidak ada pustaka terkait