Pendekatan Pencarian Langsung Penyelesaian Problema Program Integer Tak Linier Campuran

Abstract

It is well understood that integer programming is not a new subject in the field of optimization. Nevertheless, it is still an attractive field to be explored, spurred by the fact that its domain covers a wide range of important and challenging practical applications. However, given its practical applicability, we face computational difficulties in solving the integer programming problems effectively, particularly for large scale problems. This dissertation addresses computational aspects of solving large scale nonlinear integer programming problems, with emphasis on the class of mixed integer problems. The basic idea is to release a nonbasic variable, found in the continuous optimal solution in such a way that will force a corresponding non-integer basic variable to take its neighbourhood integer value. The notion of superbasic is exploited in order to maintain integer feasibility. The strategy of choosing nonbasic variables in the integrizing process is based on minimizing the deririoration of the optimal continuous solution. For a mixed integer linear programming problems, a ratio test is used in order to keep the integer result in the feasible region. In the nonlinear case, besides this ratio test, a feasibility check is used in a way to make sure the variables still satisfy the constraints of the problem. Computational experience with this approach is described for solving a large scale problem. The result shows that the proposed strategy is promising in tackling certain classes of mixed integer programming problems.

Program integer bukan suatu subjek yang baru dalam bidang optimisasi. Namun demikian, program integer masih merupakan bidang yang menarik untuk dikembangkan didorong oleh fakta bahwa domainnya melingkupi berbagai aplikasi praktis yang penting dan menantang. Namun, oleh karena penerapannya yang praktis, peneliti dihadapkan pada kesulitan komputasi dalam menyelesaikan problema-problema pemrograman integer secara efektif, khususnya untuk problema-problema skala besar. Disertasi ini menyampaikan aspek perhitungan pemecahan masalah program integer tak linier skala besar, dengan menitikberatkan pada kelas problema integer tak linier campuran. Ide dasar disertasi ini ialah membebaskan variabel nonbasis, yang ditemukan dalam penyelesaian optimum kontinu yang memaksa suatu variabel basis tak integer yang bersesuaian untuk memilih nilai integer terdekat. Gagasan tentang superbasis dieksploitasi untuk mempertahankan kelayakan bilangan bulat (integer). Strategi pemilihan variabel nonbasis dalam proses pengintegrasian didasarkan pada minimisasi penurunan penyelesaian optimum kontinu. Untuk permasalahan mixed integer linear programming, uji rasio digunakan untuk menjaga agar hasil bilangan bulat tetap dalam daerah layak. Dalam kasus non-linier, selain uji rasio ini, pemeriksaan kelayakan juga digunakan sebagai cara untuk mamastikan bahwa variabel-variabel masih memenuhi kendala permasalahan. Perhitungan-perhitungan dengan pendekatan ini digambarkan untuk pemecahan problema dengan skala besar. Hasil penelitian menunjukkan bahwa strategi yang diajukan menjanjikan untuk menyelesaikan kelas-kelas problema tertentu dari permasalahan mixed integer programming.