Penerapan Metode Barvinok Rational Functions Pada Optimasi Integer Programming Riska Kurniawati1, Rully Soelaiman, S.Kom, M.Kom2 1 2
Jurusan Teknik Informatika, Institut Teknologi Sepuluh Nopember, Surabaya, Indonesia Jurusan Teknik Informatika, Institut Teknologi Sepuluh Nopember, Surabaya, Indonesia
Permasalahan optimasi sering kali menjadi permasalahan yang sangat penting dalam menentukan suatu keputusan yang akan diambil, contohnya saja pada proses pembuatan produksi produk pada suatu bidang industri. Kebanyakan hasil yang didapatkan dari proses optimasi ini berupa bilangan pecahan yang tidak memungkinkan untuk digunakan dalam proses pengambilan keputusan. Oleh karena itu perlu diterapkan metode integer programming untuk menghasilkan solusi optimal dalam bilangan bulat sehingga dapat digunakan dalam proses pengambilan keputusan. Tugas Akhir ini menganalisa suatu metode baru yang dapat digunakan untuk menyelesaikan kasus integer programming yaitu dengan menggunakan metode Barvinok Rational Functions. Metode barvinok rational function ini mampu memberikan kemudahan dalam menyelesaikan kasus integer programming serta mempunyai waktu komputasi yang lebih cepat dan lebih efisien dalam penggunaan memori.
Kata Kunci : Integer Programming, Barvinok Rational Function I. PENDAHULUAN ermasalahan optimasi merupakan bagian yang tidak asing lagi dalam kehidupan manusia sehari-hari. Sering kali dalam usaha untuk memenuhi kebutuhannya, manusia membutuhkan proses optimasi dalam pekerjaannya. Bentuk optimasi tersebut dapat berupa meminimumkan biaya yang dikeluarkan atau juga dapat berupa memaksimumkan pendapatan yang ingin diperoleh. Akan tetapi kadang kala terdapat permasalahan jika hasil yang didapatkan dari proses optimasi tersebut berupa bilangan pecahan, padahal hasil yang diinginkan tidak memungkinkan jika menggunakan bilangan pecahan. Oleh karena itu digunakan proses optimasi dengan menggunakan metode integer programming untuk menyelesaikan masalah tersebut. Saat ini, metode yang digunakan untuk proses optimasi pada kasus integer programming sangat banyak sekali, tetapi pada pembahasan kali ini hanya difokuskan pada penggunaan metode Barvinok Rational Functions. Metode Barvinok Rational Functions ini memberikan solusi untuk menyelesaikan kasus integer programming dengan lebih cepat dan lebih efisien dalam penggunaan memori.
B. Teori Fungsi Polynomial
P
Monomial merupakan suatu fungsi yang terdiri dari term tunggal, misalnya cxn , dimana c merupakan konstanta, x merupakan variabel, dan n bernilai nol atau positif integer. Sedangakan polynomial bisa juga diartikan sebagai suatu fungsi yang mengandung operasi baik penjumlahan ataupun perkalian dari sejumlah monomial term yang terbatas (finite) [14]. Fungsi polynomial f (x) merupakan fungsi yang didefinisikan dengan mengevaluasi bentuk polynomial tersebut. Bentuk fungsi polynomial pada umumnya : (1) f ( x) = an x n + an−1 x n−1 + ..... + a2 x 2 + a1 x + a0 x 0 C. Lattice Point Lattice Points merupakan suatu kumpulan (set) titiktitik integer yang berada dalam suatu region yang terbatas (bounded polyhedron), baik yang berada tepat di batas region maupun yang berada didalam region [2]. D. Polyhedra Polyhedra merupakan representasi geometris dari sistem persamaan baik linier maupun tidak linier. Polyhedra dapat berupa suatu bidang . Perpotongan (intersection) dari beberapa polyhedra akan membentuk suatu polyhedron [2]. Bounded Polyhedron biasanya disebut juga sebagai Polytope. Polyhedron yang bounded akan convergen terhadap semua nilai. Sistem polyhedra dibentuk oleh sekumpulan cone dimana cone tersebut merupakan kombinasi linier dari x (titik) didalam polyhedra P yang mempunyai koordinat integer, dengan v (vertex) dari P.
II. DASAR TEORI A. Pemrograman Integer Tipe data integral terbagi menjadi dua buah kategori, baik itu bertanda (signed) ataupun tidak bertanda (unsigned). Bilangan bulat bertanda mampu merepresentasikan nilai bilangan bulat negatif, sementara bilangan bulat tak bertanda hanya mampu merepresentasikan bilangan bulat positif [12]. Pemrograman Integer atau juga disebut pemrograman bulat sering kali dibutuhkan ketika keputusan harus dilakukan dalam bentuk bilangan bulat (bukan pecahan yang sering terjadi bila menggunakan metode simplex). Model matematis dari pemrograman bulat sebenarnya sama dengan model linier programming, dengan tambahan batasan bahwa variabelnya harus bilangan bulat [11].
E. Generating function Generating function merupakan suatu proses untuk mendapatkan suatu bentuk persamaan yang tidak dipengaruhi oleh faktor rekursifnya. Disini generating function digunakan untuk proses pemecahan cone (decompose cone). 1
Dan bentuk dari penyebut ini berupa polynomial
Bentuk umum dari generating function :
f ( P, x ) =
∑ xm
m∈z
v
Π (1 − z ij ) .
(2)
d
-
single monomial
F. Rational function Jika terdapat dua buah fungsi polynomial, dan dilakukan operasi baik penjumlahan, pengurangan, maupun perkalian terhadap keduanya, maka hasil operasi dari kedua fungsi polynomial tersebut akan menghasilkan bentuk polynomial pula. Akan tetapi, jika terdapat dua buah fungsi polynomial, dan dilakukan operasi pembagian atau dicari rasio dari kedua fungsi polynomial tersebut, maka hasil dari operasi tersebut bukan merupakan bentuk polynomial, tetapi akan menghasilkan suatu fungsi yang rasional. Untuk lebih mudahnya, Rational function merupakan suatu fungsi yang dituliskan berdasarkan ratio dari 2 fungsi polynomial, contoh f ( x) =
Algoritma : Input : A ∈ Zm×d, b ∈ Zm, c ∈ Zd Output : Nilai Optimal dari M = maximize[c . x : Ax ≤ b, x ≥ 0, x ∈ Zd] 1. Selesaikan masalah Integer Programming dengan menggunakan metode linier programming relaxation dimana M = [max { c . x : Ax ≤ b, x ≥ 0}] dan m = [min{ c . x : Ax ≤ b, x ≥ 0}] . Dengan demikian, [M,m] merupakan initial range untuk algoritma binary search ini 2. Algoritma: While M > m do new := ⎡ M + m ⎤
P( x) , dimana P dan Q( x)
Bentuk umum dari Rational function : n
i =1
pi (x ) 1 − x ..... 1 − x uid
(
ui1
) (
)
⎢⎢
(3)
i∈I
z ui v
⎥⎥
I.
Monomial Substitution Dari metode barvinok rational function f(P,z) suatu polytope P, jumlah dari Lattice Point di dalam P menjadi terbatas ketika vektor (z1.....zd) mendekati nilai (1,....,1). Untuk mengatasi hal tersebut, substitusi vektor tidak dapat dilakukan dengan mudah. Oleh karenanya dilakukan general monomial substitution dengan mensubstitusikan suatu bentuk monomial (misal : y1a1, y2a2...., ynan) kedalam variabel zi, dengan y1a1 ∈ Zd. Jika diberikan suatu cost vector c ∈ Zd yang diterapkan untuk mensubstitusikan zk = tck , maka bentuk rational functionnya dalam t adalah t c.ui (5) f ( P, t ) = ∑ E i k c.vij ( 1 − t ) i∈I Π j =1
(4)
Π j =1 (1 − z ij ) d
2
Using Barvinok algorithm compute qnew = | P ∩ {x: c.x ≥ new}∩ Zd| If qnew > 0 then set m = new Else M = new -1 Return M
G. Metode Barvinok Rational function. Metode Barvinok rational functions pertama kali diperkenalkan oleh A.I Barvinok pada tahun 1993. Metode Barvinok rational functions ini merupakan suatu metode baru yang ditawarkan untuk memperbaiki dan menyempurnakan penyelesaian kasus integer programming. Tujuan dari metode Barvinok rational functions ini adalah untuk menemukan solusi optimal dari : Maximize c.x subject to : Ax ≤ b x≥0 x ∈ Zd dengan input data berupa mxd integral matrix A, dimana m merupakan panjang vektor dari b dan d merupakan panjang vector dari c. Input data ini mendeskripsikan non-empty full-dimensional convex polytope P = {x ∈ ℜ d : Ax ≤ b, x ≥ 0}. bentuk umum dari Barvinok Rational Function adalah sebagai berikut :
f ( P; z ) = ∑ Ei
z ui
H. Algoritma Binary search Algoritma Binary search ini merupakan algoritma straightforward dimana hanya menggunakan metode Binary search. Algoritma ini menghitung jumlah Lattice Point P yang memenuhi syarat c . x ≥ M, dimana rentang nilai maksimum dari c . x dapat dipersempit. Ketika dilakukan proses pengulangan maka akan didapatkan hasil integer M terbesar adalah tidak nol. Algoritma Binary Search ini memberikan kemungkinan penghitungan baru dalam integer programming dengan dimensi yang tetap.
Q merupakan fungsi polynomial. Rational Function merupakan salah satu bentuk expansi dari generating function, dimana semua variabel dalam persamaan tersebut berupa bilangan integer. Jika inputan yang digunakan dalam persamaan Rational Function tersebut berupa Lattice Point, maka persamaan tersebut disebut rational polyhedron
f ( P, x ) = ∑
Numerator (pembilang) dari fungsi diatas berupa
III. METODOLOGI Secara keseluruhan terdapat 4 proses utama yang harus dilakukan dalam menyelesaikan kasus integer programming untuk mendapatkan solusi optimal yang diinginkan, yaitu : 1. Proses Inisialisasi yaitu proses untuk mendapatkan bentuk persamaan Barvinok Rational Function dari suatu kasus permasalahan integer programming. Pada
Persamaan (4) merupakan bentuk dari rational function dimana, dalam bentuk fungsi rational tersebut selalu ada komponen pembilang dan penyebut, yaitu : - Denominator (penyebut) dari fungsi diatas berupa v
hasil kali binomial dari 1 − z ij , dimana vij merupakan generator dari cone Pi (ray dari cone Pi). 2
proses inisialisasi ini terdapat 2 tahapan yang dilalui yaitu: a. Tahap pengecekan inputan b. Tahap baca problem data 2. Proses Decompose Cone dengan metode Barvinok Rational Function untuk mendapatkan unimodular cone. 3. Proses Compute Lattice Point dengan menggunakan metode monomial substitution untuk mendapatkan Lattice Point yang paling optimal. 4. Proses Optimasi yaitu mencari nilai dan solusi optimal dari permasalahan IP menggunakan algoritma binary search dan algoritma digging dalam software Latte v1.2. Untuk lebih jelasnya diagram alir keseluruhan sistem dapat dilihat pada Gambar 3.2
2. Tahap Baca Problem Data Pada tahap ini dilakukan proses pembacaan problem data. Inputan yang sudah dicek pada tahap cek inputan kemudian dibaca problem data yang terkandung didalamnya. Kemudian di inisialisasi apakah problem pada inputan tersebut berupa permasalahan integer ataukah bukan. Jika hasil inisialisasi terhadap problem data tersebut bukan merupakan permasalahan integer maka inputan tersebut dianggap kosong dan tidak dapat dikerjakan. B. Proses Pemecahan Cone Proses pemecahan cone dapat dikatakan sebagai bagian yang paling penting dalam metode Barvinok rational functions ini. Proses Decompose cone merupakan proses pemecahan suatu cone kedalam beberapa unimodular cone. Salah satu cara yang digunakan untuk memecah suatu cone (decompose cone) kedalam beberapa bentuk unimodular cone dengan tepat adalah dengan menerapkan fungsi generating function. C. Proses Menghitung Lattice Point Setelah didapatkan unimodular cone dari proses decompose cone diatas, maka untuk menentukan Lattice Point yang paling optimal adalah dengan melakukan proses monomial substitution. D. Proses Optimasi Pada proses optimasi ini, akan dicari solusi dan nilai optimal dari permasalahan yang ada dengan menganalisa jalannya algoritma binary search. E. Penerapan Metode Barvinok rational functions dalam suatu kasus IP 1. Proses Inisialisasi Jika proses inisialisasi ini diterapkan dalam suatu kasus permasalahan integer maka bentuk inisialisasi berupa menterjemahkan permasalahan IP yang ada.
Gambar III.1 Diagram Alir Keseluruhan Sistem
Contoh: Maximize z = 100x + 90 y Subject to : x + y ≤ 100 x ≤ 50 x,y≥0
A. Proses Inisialisasi Proses inisialisasi ini merupakan suatu proses untuk menginisialisasi permasalahan integer programming yang akan diselesaikan menggunakan metode Barvinok Rational Function. Proses inisialisasi ini terdiri dari dua proses yaitu proses cek inputan dan proses baca problem data.
x,y ∈Ζ
d
Dari permasalahan IP yang ada, kemudian dicari vertice yang memenuhi constrain dengan melakukan proses substitusi, sehingga jika persamaan tersebut diterapkan pada persamaan garis 2 dimensi, maka batasan dari persamaan tersebut adalah: 1. Pada batasan x + y ≤ 100 jika x = 0 maka x + y ≤ 100 y ≤ 100 jika y = 0 maka x + y ≤ 100 x ≤ 100 2. Pada batasan x ≤ 50
1. Tahap Pengecekan Inputan Pada tahap ini dilakukan pengecekan terhadap inputan yang akan diselesaikan menggunakan metode Barvinok Rational Function yaitu salah satu proses yang dilakukan dalam tahapan ini yaitu proses pengecekan inputan apakah inputan tersebut kosong atau tidak. Disini maksud dari kosong adalah apakah inputan tersebut mengandung Lattice Point ataukah tidak. Jika inputan yang dimasukkan tidak mengandung Lattice Point, maka inputan tersebut dianggap kosong dan tidak dapat diselesaikan. Tahapan ini menghasilkan keluaran berupa persamaan integer programming yang telah dilakukan pengecekan inputan.
Sehingga didapatkan persamaan garis sebagai berikut :
3
Setelah dilakukan proses decompose cone berdasarkan Gambar III.2 diatas , maka didapatkan 4 buah unimodular cones dan bentuk rational functionnya adalah:
f (P; z) =
Gambar III.2 Bentuk persamaan garis dari max Z = 100x + 90y
3. Proses Hitung Lattice Point a. Jika unimodular cone sudah didapatkan, maka dilakukan proses monomial substitution dengan mensubstitusikan zk = tck , dimana c merupakan suatu cost vector c ∈ Z b. Terapkan substitusi zk = tck pada persamaan (4), sehingga menghasilkan persamaan (5), dari multivariate monomial menjadi univariate monomial. c. Dengan mengasumsikan bahwa c dipilih secara random dari suatu dimensi Zd, maka jika ditetapkan cost vector c = (100,90) maka z1 = t100 dan z2 = t90. d. Lakukan proses perhitungan persamaan (5) dengan cost vector yang sudah ditentukan, sehingga menghasilkan
2. Proses Pemecahan Cone Dari persamaan garis diatas, maka terbentuk suatu bidang P (dalam gambar berwarna kuning) yang nantinya pada bidang tersebut akan dilakukan proses decompose cone. a.
Proses cari vertice dan edge Setelah bidang P terbentuk, maka dari bidang tersebut dapat dicari komponen vertice dan edge nya. - ui (vertice)= Koordinat dari zd (dalam gambar berupa (x,y)), sehingga dihasilkan :: u1 = (0,0) u2 = (50,0) u3 = (0,100) u4 = (50,50) - vij (edge) = Generators Cone Pi berupa arah dari vektor z (dalam gambar berupa (xij,yij)) • Jika i mempunyai arah vektor ke kanan maka bernilai = 1 • Jika i mempunyai arah vektor ke kekiri maka bernilai = -1 • Jika j mempunyai arah vektor ke atas maka bernilai = 1 • Jika j mempunyai arah vektor ke bawah maka bernilai = -1
f ( P, t ) = ∑ E i i∈I
=
z10 z20
+
z150z20
(1− z11z20 )(1− z10 z12 ) (1− z1−1z20 )(1− z10 z12 )
Π
k j =1
(1 − t
c.vij
)
+
t 100.50 t 90.50
(1 − z 2−1 )(1 − z1 z 2−1 ) (1 − z 2−1 )(1 − z1−1 z 2 ) Setelah didapatkan lattice point yang paling optimal dari masing-masing unimodular cone maka untuk mendapatkan nilai optimal dari persamaan integer diperlukan penerapan algoritma binary search
4. Proses Optimasi Berdasarkan proses perhitungan diatas, maka dapat diketahui bahwa nilai dari : - Maximize z = 100x1 + 90x2 Subject to : x1+ x2 ≤ 100 x1≤ 50 x1 , x2 ≥ 0 dan integer adalah 9500 dengan x1 = 50 dan x2=50 - Minimize z = 100x1 + 90x2 Subject to : x1+ x2 ≤ 100 x1≤ 50 x1 , x2 ≥ 0 dan integer adalah 0 dengan x1 = 0 dan x2=0 Oleh karena nilai optimum yang dihasilkan merupakan bilangan integer, maka proses linear programming relaxation menghasilkan M = 9500 dengan x1 = 50, dan x2 = 50, serta m = 0 dengan x1 =0 dan x2 =0: Identifikasi setiap unimodular cone yang dihasilkan dari proses cari lattice point, dan dilakukan pengecekan apakah unimodular cone tersebut berada dalam range [M,m] dan integer, sehingga dihasilkan :
Proses Generating Function Setelah didapatkan komponen ui dan vij maka proses decompose cone dengan menerapkan metode Barvinok Rational function pada persamaan (4) dapat dilakukan. Sehingga dihasilkan : z ui f ( P; z ) = ∑ E i d v i∈I Π j =1 (1 − z ij )
=
t c.ui
t 100.50 1 + + (1 − z1 )(1 − z 2 ) (1 − z1−1 )(1 − z 2 ) t 90.100
Sehingga dihasilkan : v11 = (1,0) v31 = (0,-1) v12 = (0,1) v32 = (1,-1) v21 = (-1,0) v41 = (0,-1) v22 = (0,1) v42 = (-1,1) b.
z150 1 + + (1 − z1 )(1 − z 2 ) (1 − z1−1 )(1 − z2 ) z100 z150z250 2 + (1− z2−1)(1− z1z2−1) (1− z2−1)(1− z1−1z2 )
+
z10 z 100 z150 z 250 2 = + (1 − z10 z 2−1 )(1 − z11 z 2−1 ) (1 − z10 z 2−1 )(1 − z1−1 z 12 )
z150 1 + ++ (1 − z1 )(1 − z 2 ) (1 − z1−1 )(1 − z 2 ) z100 z150z250 2 + (1− z2−1)(1− z1z2−1) (1− z2−1)(1− z1−1z2)
4
P4 (50,50) Æ Maximize z = 100x1 + 90x2 = 9500
P1 (0,0) Æ Maximize z = 100x1 + 90x2 =0 P2 (50,0) Æ Maximize z = 100x1 + 90x2 = 5000 P3 (0,100) Æ Maximize z = 100x1 + 90x2 = 9000
-
Dari hasil diatas dapat diketahui bahwa terdapat 4 buah unimodular cone yang memiliki batasan yang integer. Proses Dari hasil iterasi didapatkan :
Unimodular cone P1 Tabel III.1Hasil iterasi unimodular cone P1 (Bagian 1) M,m
Iterasi 1 M = 9500, m= 0
Iterasi 2 M = 4249 m=0
Iterasi 3 M = 2124 m=0
Iterasi 4 M = 1061 m=0
Iterasi 5 M = 530, m=0
Iterasi 6 M = 264, m=0
M>m
y
y
y
new = [M+m / 2] qnew P1
4250 0
2125 0
1062 0
y
y
y
531 0
265 0
132 0
qnew= c.x≥ new
0 ≥ 4250
0 ≥ 2125
0 ≥ 1062
0 ≥ 531
0 ≥ 265
0 ≥ 132
qnew > 0
n
n
n
n
n
n
M
4249
2124
1061
530
264
131
m
Tabel III.2 Hasil iterasi unimodular cone P1 (Bagian 2) Iterasi 7 M = 131, m=0
M,m
Iterasi 8 M = 60, m=0
Iterasi 9 M = 29, m=0
Iterasi 9 M = 14, m=0
Iterasi 10 M = 6, m=0
Iterasi 11 M = 2, m=0
Iterasi 12 M = 0, m=0 n
M>m
y
y
y
y
y
y
new = [M+m / 2] qnew P1
61 0
30 0
15 0
7 0
3 0
1 0
qnew= c.x≥ new
0 ≥ 61
0 ≥ 30
0 ≥ 15
0≥7
0≥3
0≥1
qnew > 0
n
n
n
n
n
n
M
60
29
14
6
2
0
m Solusi
-
M=0
Unimodular cone P2 Tabel III.3 Hasil iterasi unimodular cone P2 (Bagian 1) Iterasi 1 M = 9500, m= 0
Iterasi 2 M = 9500 m=4250
Iterasi 3 M = 6874 m=4250
Iterasi 4 M = 5561 m=4250
Iterasi 5 M = 5561, m=4901
M>m
y
y
y
y
new = [M+m / 2] qnew P2
4250
6875
5562
4901
5000
5000
5000
qnew= c.x≥ new qnew > 0
5000 ≥ 4250
5000≥ 6875
5000≥ 5562
n
n
y
6874
5561
M,m
y
M m
4250
Iterasi 6 M = 5230, m=4901
Iterasi 7 M= 5065 m=4901
y
y
y
5231
5066
4983
5000
5000
5000
5000
5000≥ 4901
5000≥ 5231
5000≥ 5066
5000≥ 4983
n
n
y
5230
5065
4901
4983
Tabel III.4 Hasil iterasi unimodular cone P2 (Bagian 2) M,m
Iterasi 8 M=5065 m=4983
Iterasi 9 M = 5023, m=4983
Iterasi 9 M = 5002, m= 4983
Iterasi 10 M = 5002, m=4993
Iterasi 11 M=5002, m=4998
Iterasi 11 M=5002, m=5000
Iterasi 12 M = 5000, m= 5000 n
M>m
y
y
y
y
y
y
new = [M+m / 2] qnew P2
5024 5000
5003 5000
4993 5000
4998 5000
5000 5000
5001 5000
qnew= c.x≥ new
5000≥ 5024
5000≥ 5003
5000≥ 4993
5000≥ 4998
5000≥ 5000
5000≥ 5001
qnew > 0
n
n
y
y
y
M
5023
5002
m
n 5000
4993
4998
Solusi
5000 M = 5000
5
-
Unimodular cone P3 Tabel III.5 Hasil iterasi unimodular cone P3 (Bagian 1) M,m
Iterasi 1 M = 9500, m= 0
Iterasi 2 M = 9500 m=4250
Iterasi 3 M = 9500 m=6875
Iterasi 4 M = 9500 m=8188
Iterasi 5 M = 9500, m=8844
Iterasi 6 M = 9171, m=8844
Iterasi 7 M= 9007 m=8844
M>m
y
y
y
y
y
y
y
new = [M+m / 2] qnew P3
4250
6875
8188
8844
9172
9008
8926
9000
9000
9000
9000
9000
9000
9000
9000≥ 4250
9000≥ 6875
9000≥ 8188
9000≥ 8844
9000≥ 9172
9000≥ 9008
9000≥ 8926
y
y
y
y
n
n
y
9171
9007
qnew= c.x≥ new qnew > 0 M m
4250
M,m
Iterasi 8 M=9007 m=8926
6875
8188
8844
8926
Tabel III.6 Hasil iterasi unimodular cone P3 (Bagian 2)
M>m new = [M+m / 2] qnew P3 qnew= c.x≥ new qnew > 0 M m Solusi
-
y 8967
Iterasi 9 M= 9007 m= 8967 y 8987
Iterasi 9 M = 9007, m= 8987
Iterasi 10 M = 9007, m=8997
Iterasi 11 M=9001, m=8997
Iterasi 12 M=9001, m=8999
Iterasi 13 M= 9001, m= 9000
Iterasi 13 M = 9000, m= 9000
y 8997
y 9002
y 8999
y 9000
y 9001
n
9000 9000≥ 8967
9000 9000≥ 8987
y
y
9000 9000≥ 8997 y
9000 9000≥ 9002
9000 9000≥ 8999
9000 9000≥ 9000
9000 9000≥ 9001
n 9001
y
y
n 9000
8967
8987
8997
8999
9000 M = 9000
Unimodular cone P4 Tabel III.7 Hasil iterasi unimodular cone P4 (Bagian 1) M,m
Iterasi 1 M = 9500, m= 0
Iterasi 2 M = 9500 m=4250
Iterasi 3 M = 9500 m=6875
Iterasi 4 M = 9500 m=8188
Iterasi 5 M = 9500, m=8844
Iterasi 6 M = 9500, m=9172
Iterasi 7 M= 9500 m=9336
M>m
y
y
y
y
y
y
y
new = [M+m / 2] qnew P3
4250
6875
8188
8844
9172
9336
9418
9500
9500
9500
9500
9500
9500
9500
qnew= c.x≥ new qnew > 0
9500≥ 4250
9500≥ 6875
9500≥ 8188
9500≥ 8844
9500≥ 9172
9500≥ 9336
9500≥ 9418
y
y
y
y
y
y
y
4250
6875
8188
8844
9172
9336
9418
M m
Tabel III.8 Hasil iterasi unimodular cone P4 (Bagian 2) M,m
M>m new = [M+m / 2] qnew P3 qnew= c.x≥ new qnew > 0 M m Solusi
Iterasi 8 M= 9500 m= 9418 y 9459
Iterasi 9 M= 9500 m= 9459 y 9480
Iterasi 9 M = 9500, m= 9480
Iterasi 10 M = 9500, m= 9490
Iterasi 12 M= 9500, m= 9498 y 9499
Iterasi 13 M= 9500, m= 9499
Iterasi 13 M = 9500, m= 9500
y 9495
Iterasi 11 M= 9500, m= 9495 y 9498
y 9490
y 9500
n
9500 9500≥ 9459
9500 9500≥ 9480
9500 9500≥ 9495
9500 9500≥ 9498
9500 9500≥ 9499
9500 9500≥ 9500
y
9500 9500≥ 9490 y
y
y
y
y
y
9459
9480
9490
9495
9498
9499
9500 M = 9500
6
Bandingkan nilai M dari tiap unimodular cone, nilai M yang terbesar adalah nilai optimal dari persamaan integer. Dari hasil iterasi diatas, nilai M pada polytope P4 merupakan nilai M terbesar sehingga dapat disimpulkan bahwa nilai optimal untuk:
IV. HASIL UJI COBA DAN EVALUASI Uji coba dilakukan pada Intel (R)Pentium (R) Dual CPU T2390 1,86 GHz . Pada bagian ini akan ditampilkan data uji coba dengan beberapa ukuran persoalan dengan jumlah constrain dan variabel yang berbeda. Data uji coba ini adalah matrik data yang berisi variable serta constrains dari persamaan integer. Data variabel tiap persamaan dituliskan dalam bentuk file dengan ekstensi .cost sedangkan data constrains dituliskan dalam bentuk file input. Data yang digunakan sebagai uji coba sistem ini diambil dari [4] dan [9]. Berikut data dan hasil uji coba dapat dilihat pada Tabel IV.1, Tabel IV.2, dan Tabel IV.3
Maximize z = 100x1 + 90x2 Subject to : x1+ x2 ≤ 100 x1≤ 50 x1 , x2 ≥ 0 dan integer
adalah 9500 dengan x1 = 50 dan x2 = 50
Tabel IV.1 Data variabel Problem taaa1 taaa2 cuww1
c1 5 2
c2 4 -1
c3
c4
c5
213
-1928
cuww2
213
cuww3
213
c6
-11111
-2345
9123
-1928
-11111
-2345
9123
– 12834
-1928
-11111
-2345
9123
– 12834
3
Tabel IV.2 Data constrains Problem taaa1 taaa2 cuww1
a1 1 10 1 2 12,223
a2 1 6 -1 -1
a3
a4
a5
12,224
36,674
61,119
85,569
a6
b 5 45 10 40 89,643,482
5 3
cuww2
12,228
36,679
36,682
48,908
61,139
73,365
89,716,839
cuww3
12,137
24,269
36,405
36,407
48,545
60,683
58,925,135
Tabel IV.3 Perbandingan Hasil Problem taaa1 taaa2 cuww1 cuww2 cuww3
Value
Iterasi BBS
23 40 156,2142 −4,713,321 1,034,115
3 0 26 25 25
Iterasi TORA 5 2 -
Run Time BBS 0.04 s 0,08 s 135 s 1,2 h 1,15 h
Run Time TORA 1s 2s Unsolved Unsolved Unsolved
dibandingkan dengan program TORA, hal ini dapat dilihat pada record satu dengan problem = taaa1 dengan jumlah iterasi untuk BBS = 3 sedangkan untuk TORA =5. Begitu pula pada record dua dengan problem = taaa2 dengan jumlah iterasi untuk BBS = 0 sedangkan untuk TORA =2. Dari hasil uji coba, dapat dianalisa bahwa program Latte v1.2 yang menerapkan algoritma binary seach mempunyai waktu eksekusi program yang lebih cepat dibandingkan dengan waktu eksekusi program TORA. Hal ini dapat dilihat pada record satu dengan problem = taaa1 dengan nilai optimal 23 yang memiliki waktu eksekusi program untuk Latte v1.2 = 0,04 s sedangkan waktu eksekusi program untuk TORA = 1 s. Hal ini dapat dilihat pula pada record dua dengan problem = taaa2 dengan nilai optimal 40 yang memiliki waktu eksekusi program untuk Latte v1.2 = 0,08 s sedangkan waktu eksekusi program untuk TORA = 2 s
A. Skenario Uji Coba Kebenaran Hasil Dari hasil uji coba, dapat dianalisa bahwa data uji coba dengan menggunakan 2 variabel dapat diselesaikan menggunakan program Latte v1.2 maupun menggunakan program TORA dan dapat menghasilkan nilai optimal. Hal ini dapat dilihat pada record satu dengan problem = taaa1 dengan nilai optimal 23. Dari hasil uji coba, dapat dianalisa bahwa data uji coba dengan menggunakan 3 variabel dapat diselesaikan menggunakan program Latte v1.2 maupun menggunakan program TORA dan dapat menghasilkan nilai optimal. Hal ini dapat dilihat pada record dua dengan problem = taaa2 dengan nilai optimal 40. B. Skenario Uji Coba Kinerja Dari hasil uji coba, dapat dianalisa bahwa jumlah iterasi yang dibutuhkan program latte v1.2 lebih sedikit 7
programming dengan solver IP lainnya yang sudah umum.
Dari hasil uji coba dengan menggunakan 5 variabel, dapat dianalisa bahwa penyelesaian persamaan integer programming menggunakan program TORA dengan metode Branch and Bound tidak dapat menghasilkan solusi yang diharapkan, karena semua data uji coba tidak dapat terselesaikan (unsolved). Hal ini dapat dilihat pada record tiga dengan problem = cuww1 didapatkan output unsolved pada saat menggunakan program TORA. Sedangkan pada record empat dengan problem = cuww2 didapatkan output unsolved pada saat menggunakan program TORA. Begitu pula dengan record lima dengan problem = cuww3 didapatkan output unsolved pada saat menggunakan program TORA. Sedangkan hasil uji coba dengan menggunakan program Latte v1.2 semua record dapat terselesaikan dan menghasilkan nilai optimal.
VI.
DAFTAR PUSTAKA
[1] A.I. Barvinok, J. Pommersheim, An algorithmic theoryof lattice points in polyhedra, in: New Perspectives in Algebraic Combinatorics (Berkeley, CA, 1996–1997), Mathematical Science and Research Institute Publications, vol. 38, Cambridge University Press, Cambridge, 1999, pp. 91–147 [2] A.I Barvinok, Lattice Points, Polyhedra, and Complexity, IAS/Park City Mathematics Series Volume , 2004 [3] A.I. Barvinok, Polynomial time algorithm for counting integral points in polyhedra when the dimension is fixed, Math. Oper. Res. 19 (1994) 769– 779.
Untuk algoritma binary search, waktu yang tertera pada output program tidak sesuai dengan kondisi. Hal ini terbukti dengan saat eksekusi program waktu yang tertera pada output program record 4 dengan problem = cuww1 adalah 0,15 detik kenyataannya waktu yang dibutuhkan pada saat eksekusi program 135 detik. Sedangkan pada record 5 dengan problem = cuww3, saat eksekusi program waktu yang tertera pada output program adalah 0,09 detik, kenyatannya waktu yang dibutuhkan pada saat eksekusi program 1,15 jam. Lingkungan implementasi mempengaruhi waktu eksekusi dari program Latte v1.2. Berdasarkan paper acuan, uji coba program Latte diimplementasikan pada 1Ghz Pentium PC Red Hat Linux menghasilkan waktu eksekusi untuk record empat dengan problem = cuww 1 sebesar 414 sec. Sedangkan pada uji coba tugas akhir ini, program Latte v1.2 diimplementasikan pada 1,86 Ghz Intel (R)Pentium (R) Dual CPU T2390 pada record empat dengan problem = cuww1 waktu eksekusinya sebesar 135 sec. Begitu pula pada record enam dengan problem = cuww3 , pada paper acuan waktu eksekusi program 1,7 jam sedangkan pada tugas akhir ini waktu eksekusi program 1,15 jam.
[4] .J.A De Loera, D.Haws, R. Hemmecke, P. Huggins, R. Yoshida, A computational study of integer programming algorithms based on Barvinok rational functions, Discrete Optimization 2 (2005) 135 – 144 [5] J.A. De Loera, R. Hemmecke, J. Tauzer, R.Yoshida, Effective lattice point counting in rational convex polytopes, J. Symbolic Comput. 38 (2004) 1273– 1302. [6] J.A. De Loera, D. Haws, R. Hemmecke, P. Huggins, J. Tauzer, R.Yoshida, A User’s Guide for LattE v1.1, 2003, Software package LattE is available at http://www.math.ucdavis.edu/~latte/ [7] M. F. Muthohar, Penerapan Algoritma Branch and bound pada Masalah Integer Knapsack , ITB, 2008 [8] R. Maharesi, Perbandingan Antara Pendekatan Branch and Bound dan Pemrograman Linier: Dengan Sebuah Contoh Kasus Optimasi, Universitas Gunadarma, 2002.
V. Kesimpulan Dari hasil pengamatan selama perancangan, implementasi, dan proses uji coba, penulis mengambil kesimpulan sebagai berikut : 1. Berdasarkan hasil uji coba yang telah dilakukan, maka dapat disimpulkan bahwa Program Latte v1.2 yang menerapkan metode barvinok rational function mampu memberikan kemudahan dalam menyelesaikan kasus integer programming serta mempunyai waktu komputasi yang lebih cepat dan lebih efisien dalam penggunaan memori . 2. Algoritma binary search yang diterapkan dalam metode barvinok rational function, merupakan algoritma yang efektif dalam menyelesaikan kasus integer programming dibandingkan dengan metode branch and bound yang digunakan dalam TORA. 3. Penerapan metode barvinok rational function ini mampu menghasilkan one feasible integer solution untuk masing – masing data uji coba sehingga memudahkan pengguna dalam pengambilan keputusan. 4. Program Latte v1.2 mampu menghasilkan nilai optimal yang sama dari suatu permasalahan integer
[9] Taha, Hamdi A. 1982. Operation Research : An Introduction, Eight Edition, Macmillan Publishing Co.Inc. .New York [10] ……..2007, Barvinok,
[11]
..........2007, Bilangan Bulat
:
[12] ..........2007, Integer [13]
........2009, Laurent Polynomial
[14] ........2009, Polynomial http://en.wikipedia.org/ wiki/Polynomial>
8
:
