Analisis Algoritma Branch and Cut untuk Menyelesaikan Persoalan Program Integer Kuadrat

Abstract

A mathematical programming model quadratic objective function and linear constraints with integer valued decision variables are often known as quadratic integer programming. Quadratic integer programming can solve many mathematical problem is to determine the optimal function of the problem to change the parameters. Quadratic integer programming has fairly wide use, especially in the areas of scheduling, chemical process, in financial and network design. The algorithm branch and cut is a combination of algorithm branch and bound and cutting plane, Methods Branch and Cut is one method used to solve linear programming problem that requires settlement in the form of an integer, but is usually used in a linear programming problem that has the sole purpose of this algorithm is a method used in solving the problem of integer programming, where the concept of the solution leads to a completion point of the decent round. In this thesis will be shown how integer quadratic programming problems can be solved with the branch and cut algorithm.

Suatu model pemrograman matematika yang fungsi objektifnya berbentuk kuadratik dan kendala linier dengan peubah keputusan bernilai bilangan bulat yang sering dikenal sebagai quadratic integer programming. Quadratic integer programming dapat menyelesaikan banyak persoalan matematika yaitu untuk menentukan fungsi optimal dalam permasalahan terhadap perubahan parameter. Quadratik integer programming mempunyai penggunaan yang cukup luas terutama dalam bidang penjadwalan, proses kimia, bidang financial, dan rancangan jaringan. Algoritma branch and cut merupakan gabungan dari algoritma branch and bound dan cutting plane, Metode Branch and Cut merupakan salah satu metode yang digunakan untuk menyelesaikan masalah linear programming yang menghendaki penyelesaian dalam bentuk bilangan bulat, tetapi biasanya digunakan pada masalah linear programming yang memiliki tujuan tunggal, algoritma ini merupakan metode yang dipakai dalam menyelesaikan persoalan integer programming, dimana konsep penyelesaiannya mengarah pada suatu titik penyelesaian layak bulat. Dalam thesis ini akan ditunjukkan bagaimana persoalan quadratic integer programming dapat diselesaikan dengan algoritma branch and cut.