Algoritma titik interior, sebuah tinjauan empiris

SIHABUDDIN, Agus, Prof.Drs. Subanar, PhD

2004 | Tesis | S2 Ilmu Komputer

Ada beberapa metode yang dapat digunakan untuk menyelesaikan permasalahan program linear. Masing-masing metode penyelesaian mempunyai waktu kompleksitas yang berbeda-beda yang menunjukkan efisiensi algoritma. Efisiensi Algoritma dapat dilihat dengan beberapa cara yang salah satunya adalah dengan cara empiris. Algoritma titik interior yang dikenalkan pertama kali oleh Karmakar merupakan salah satu algoritma yang mempunyai waktu kompleksitas polinomial. Pada penelitian ini dikupas mengenai algoritma tersebut secara empiris yaitu dengan menjalankan berbagai ukuran permasalahan dan dicatat datanya. Hal-hal yang dilihat dari algoritma ini adalah pengaruh presolving dan kompleksitas algoritma. Hasil yang diperoleh adalah bahwa pertama: presolving dapat mengurangi ukuran permasalahan, waktu penyelesaian algoritma, dan waktu total penyelesaian. Hal lain yang dilihat adalah waktu untuk presolving lebih besar dari pada satu iterasi algoritma. Kedua: kecenderungan jumlah iterasi dan waktu kompleksitas algoritma titik interior terhadap ukuran permasalahan secara empiris berupa fungsi power yaitu O(n0.2294) untuk jumlah iterasi dan. O(n0.9760) untuk waktu kompleksitas dengan n adalah ukuran permasalahan

There are some algorithms to solve linear programming problems. Each method has its own time complexity showing the efficiency of the each algorithm. Empirical point of view is one of methods to see the efficiency. The interior point algorithm introduced by Karmakar is one of algorithms having polynomial time complexity. This paper observes this algorithm empirically by executing the various problems in linear programming and gives the emphasis on the impact of presolving and algorithm complexity. The results are first: presolving can reduce the size of problems, solving time, and total solution time, also the presolving time is longer than the time for one iteration. Second: solving time and the count of iteration tend to be the form of power function those bond to O(n0.2294) for the count of iteration and O(n0.9760) for the time complexity with n is size of the problem.

Kata Kunci : Komputer,Algoritma Titik Interior,Program Linear, complexity, empiric, interior point algorithm, polynomial, presolving,