Algoritma Interior Point untuk Menyelesaikan Program Integer

Abstract

TBranch-and-bound is a method of solving an program integer problem by solving a sequence of linear programming problems. The subproblems can be regarded as forming a tree, rooted at the linear programming relaxation of the integer program ming problem. Research on using interior point algorithms to solve integer programming problems is surveyed. This thesis concentrates on branch and bound and cutting plane methods, a potential function method is also briefly mentioned. The princi pal difficulty with using an interior point algorithm in a branch and cut method to solve integer programming problems is in warm starting the algorithm efficiently. Methods for overcoming this difficulty are described and other features of the al gorithms are given. This thesis focuses on the techniques necessary to obtain an efficient computational implementation.

Metode branch and bound dapat digunakan untuk menyelesaikan persoalan pro gram integer dengan menyederhanakan persamaan program linier yang terdapat dalam permasalahan tersebut. Penyelesaiannya dilakukan dengan proses relaksasi program linier dari persoalan program integer tersebut. Penelitian algoritma interior point untuk menyelesaikan permasalahan pro gram integer telah banyak dilakukan. Tesis ini menjelaskan bagaimana metode branch dan bound serta metode cutting plane, merupakan metode yang sangat baik dalam penyelesaian masalah program integer yang akan dijelaskan secara tegas. Kesulitan yang utama dalam penggunaan metode interior point dengan menggunakan metode branch dan bound adalah teknik memodelkan persoalan program integer dengan kendala yang dimiliki. Algoritma interior point menggam barkan beberapa kendala yang muncul sehingga teknik komputasi akhirnya dapat digunakan untuk menyelesaikan persoalan program integer yang dimaksud.