EVALUASI HASIL UJI COBA KOMPUTASI PEMECAHAN SISTEM PERSAMAAN LINEAR PADA ALGORITMA DUAL-AFFINE SCALING INTERIOR POINT UNTUK PEMROGRAMAN LINEAR DENGAN MATLAB Hendri Murfi*, T. Basaruddin**
ABSTRAK EVALUASI HASIL UJI COBA KOMPUTASI PEMECAHAN SISTEM PERSAMAAN LINEAR PADA ALGORITMA DUAL-AFFINE SCALING INTERIOR POINT UNTUK PEMROGRAMAN LINEAR DENGAN MATLAB. Metode interior point telah menjadi metode alternatif untuk memecahkan pemrograman linear setelah Karmarkar mempresentasikan suatu algoritma dari metode ini dengan kompleksitas waktu polinomial. Dalam pengimplementasian algoritma dari metode ini, ada dua hal penting yang sangat mempengaruhi kinerja algoritma yaitu struktur data dan metode yang digunakan untuk memecahkan sistem persamaan linear yang ada pada algoritma tersebut. Tulisan ini akan mendeskripsikan tentang penyelesaian sistem persamaan linear yang ada pada salah satu variasi dari metode interior point yang disebut dual-affine scaling. Selanjutnya dilakukan evaluasi terhadap hasil uji coba komputasi dari beberapa metode yang digunakan, baik dari metode langsung maupun metode iterative. Uji coba dilakukan dengan menggunakan Matlab. Kata kunci: metode interior point, algoritma dual-affine scaling, sistem persamaan linear, pemrograman linear, matlab
ABSTRACT The interior point method for linear programming has gained extraordinary interest as an alternative to simplex method since Karmarkar presented a polynomial-time algorithm for linear programming based on interior point method. In implementation of the algorithm of this method, there are two important things that have impact heavily to performance of the algorithm; they are data structure and used method to solve linear equation system in the algorithm. This paper describes about solving linear equation system in variants of the algorithm called dual-affine scaling algorithm. Next, we evaluate experimentally results of some used methods, either direct method or iterative method. The experimental evaluation used Matlab. Keywords: Interior point method, dual-affine scaling algorithm, linear equation system, linear programming, matlab
*
Jurusan Matematika FMIPA – Universitas Indonesia Fakultas Ilmu Komputer – Universitas Indonesia
**
PENDAHULUAN Metode interior point pertama kali dikemukakan oleh Dikin pada pertengahan tahun 1967 [2], dan mulai menjadi topik penelitian yang menarik. Banyak peneliti setelah Karmarkar, pada tahun 1984, mempresentasikan suatu algoritma (algoritma Karmarkar) yang memiliki kompleksitas waktu polinomial. Algoritma tersebut dapat menyelesaikan pemrograman linear sampai limapuluh kali lebih cepat dari metode simplek [6]. Sesuai dengan namanya, metode ini akan melalui daerah dalam (interior) dari daerah solusi yang mungkin (feasible) dalam mencari solusi optimal. Yang berbeda dengan metode simplek, di mana pencarian solusi optimalnya melalui daerah batas (boundary). Dalam perkembangannya, metode ini telah dikembangkan dengan beberapa pendekatan. Secara umum metode ini dapat dikelompokkan menjadi tiga kategori, yaitu: metode affine scaling, metode potential reduction (barrier) dan metode central trajectory (path-following). Sementara persoalan yang bisa diselesaikan dengan metode ini juga mengalami perkembangan. Awalnya metode ini dikembangkan untuk pemrograman linear dan sekarang sudah dikembangkan untuk masalah-masalah yang lain, seperti : pemrograman integer, pemrograman jaringan (network programming), pemrograman semidefinite (semidefinite programming), dll [8]. Ada dua hal penting yang perlu diperhatikan dalam mengimplementasikan algoritma dual-affine scaling ini, yaitu struktur data dan metode yang digunakan untuk memecahkan sistem persamaan linear (SPL) yang ada pada algoritma tersebut. Kedua hal ini sangat mempengaruhi kinerja algoritma secara keseluruhan. Struktur data menjadi hal yang sangat penting karena sebagian besar masalah pemrograman linear adalah masalah yang jarang (sparse). Sehingga jika struktur data yang digunakan tidak mendukung penyimpanan secara jarang (sparse), maka efisiensi algoritma akan menjadi kurang optimal. Pada tulisan ini, struktur data yang digunakan adalah struktur data yang mendukung penyimpanan secara jarang (sparse). Struktur data ini didesain dengan memanfaatkan fasilitas dari perangkat lunak Matlab. Hal berikutnya yang penting dalam mengimplementasikan algoritma dual-affine scaling ini adalah metode yang digunakan untuk memecahkan SPL yang ada pada algoritma tersebut. Pemilihan metode ini sangat penting, karena untuk masalah yang besar maka jenis metode yang digunakan akan sangat mempengaruhi efisiensi algoritma secara keseluruhan. Baik efisiensi ditinjau dari waktu komputasi maupun memori yang digunakan. Pada tulisan kami sebelumnya [4], kami menggunakan metode dari kelompok metode langsung (direct method) yaitu faktorisasi cholesky dan modifikasi faktorisasi cholesky. Modifikasi dilakukan terhadap faktorisasi cholesky, karena faktorisasi cholesky hanya bisa menyelesaikan SPL yang symmetric definite positive [3][5]. Sementara selama proses iterasi algoritma dual-affine scaling, SPL dapat menjadi tidak symmetric definite positive [4][11]. Dengan metode modifikasi faktorisasi tersebut kasus yang tidak dapat diselesaikan dengan metode cholesky
terpecahkan dengan metode modifikasi faktorisasi cholesky. Pada tulisan ini akan memfokuskan penggunaan metode iterative dalam memecahkan SPL tersebut. Metode yang akan digunakan adalah preconditioned conjugate gradient dengan incomplete cholesky factor sebagai preconditioned-nya [7][9]. Selanjutnya akan dilakukan evaluasi dan studi perbandingan terhadap hasil uji coba dari masing-masing metode yang digunakan. Uji coba ini dilakukan dengan menggunakan menggunakan perangkat lunak Matlab pada PC IBM Think Pada Pentium II berbasis windows 98. Sistematika dari tulisan ini adalah sebagai berikut. Pada bagian II, akan dideskripsikan algoritma dual-affine scaling di mana SPL yang akan diselesaikan berada. Pada bagian III, akan ditampilkan masalah-masalah penguji (test problems), yang akan digunakan untuk melihat perbandingan efisiensi dari masing-masing metode. Pada bagian IV, akan dibahas penyelesaian SPL dengan menggunakan metode preconditioned conjugate gradient. Hasil yang diperoleh dengan menggunakan metode modifikasi faktorisasi cholesky juga akan diberikan sebagai bahan perbandingan. Tulisan ini akan ditutup dengan suatu kesimpulan berdasarkan hasil uji coba komputasi yang diperoleh.
ALGORITMA DUAL-AFFINE SCALING Algoritma yang digunakan pada tulisan ini berdasarkan algoritma I dari Adler et al [1] (pseudocode 2.1). Algoritma ini diterapkan pada pemrograman linear yang berbentuk pertidaksamaan. Karena sebagian besar pemrograman linear diformulasikan dalam bentuk persamaan, maka algoritma ini diterapkan pada bentuk dual-nya. P:
min s.t.
cTx Ax = b x≥0
(2.1) (2.2) (2.3)
di mana Am x n adalah matrik koefisien dari pemrograman linear yang full-rank, b adalah vektor berdimensi-m, c adalah vektor objektif yang berdimensi-n, dan x adalah vektor solusi dari primal berdimensi-n. D:
max s.t.
bTy ATy ≤ c
(2.4) (2.5)
di mana y adalah vektor solusi dari dual berdimensi-m. Algoritma (pseudocode 2.1) akan berhenti jika perubahan nilai objektif dual lebih kecil dari suatu nilai toleransi yang diberikan, yang diformulasikan sbb: |cTyk – cTyk-1| / max{1, |cTyk-1|} < ε
(2.6)
di mana ε adalah nilai toleransi yang diberikan. Procedure DAS (A, b, c, y0, stopping criterion, γ) 1. k := 0 2. do stopping criterion not satisfied 3. vk := c - ATyk; 4. Dk := diag(v1k, ….. , vmk); 5. dy := (ADk-2AT)-1b; 6. dv := -ATdy; 7. α := γ x min{-vIk/(dv)i : (dv)i < 0, i = 1, …, m}; 8. yk+1 := yk + αdy; 9. xk+1 := Dk2dv; 10. k := k+1; 11. end do end DAS Pseudocode 2.1 Algoritma Dual-Affine Scaling Algoritma juga memerlukan suatu vektor y0 yang merupakan tebakan awal untuk solusi bentuk dual di atas (initial interior dual feasible solution) sebagai input. Akan tetapi, tidak ada jaminan bahwa vektor y0 tersebut selalu ada. Untuk mengatasi ini, Adler et al [1] memperkenakan suatu skema Big M. Bedasarkan pendekatan ini, suatu variabel buatan ditambahkan ke bentuk Dual sbb: Da :
max s.t.
bTy – M ya ATy - eT ya ≤ c
(2.7) (2.8)
di mana eT = (1, 1, ……., 1) dan M adalah suatu konstanta yang besar. Dalam implementasinya, algoritma di atas menggunakan skema fase I / fase II. Pertama-tama, algoritma diterapkan pada Da, yang dikenal sebagai fase I, dengan variabel inisial sbb: y0 ya0 eT M
= = = =
(||b||2 / ||A c||2) .c 2 ||b – A y0||2 (1, 1, …, 1)T µ cT y0 / ya0, di mana µ adalah bilangan yang besar
(2.9) (2.10) (2.11) (2.12)
Pada fase I ini, algoritma akan mencari nilai tebakan awal untuk mencari solusi bentuk dual. Sementara kriteria penyetop dimodifikasi menjadi :
1. Jika yak < 0 pada iterasi ke-k, maka yk adalah tebakan awal untuk solusi bentuk dual 2. Jika algoritma berhenti berdasarkan kriteria penyetop standar (2.6) dan yak > δ, maka D dinyatakan tidak memiliki solusi (infeasible) 3. Jika algoritma memenuhi kriteria penyetop standar (2.6) dan yak < δ, maka D unboundedness atau suatu solusi yang optimal ditemukan. Dalam hal ini, D tidak mempunyai interior feasible solution. Pada tulisan ini, uji coba komputasi menggunakan nilai-nilai konstanta sebagai berikut : ε adalah 10-8, γ adalah 0,95, µ adalah 105 dan δ adalah 10-4. MASALAH PENGUJI (TEST PROBLEM) DAN KARAKTERISTIKNYA Pemrograman linear yang akan digunakan sebagai masalah penguji pada uji coba komputasi adalah masalah penguji buatan. Di mana matrik koefisien-nya diambil dari matrik yang ada pada Matlab. Ada 8 pemrograman linear buatan yang akan digunakan sebagai masalah penguji. Karakteristik matrik koefisien dari pemrograman linear buatan tersebut dilihat pada Tabel 3.1. Tabel 3.1. Karakteristik Matrik Koefisien dari Pemrograman Linear Penguji No 1 2 3 4 5 6 7 8
Masalah Penguji TP-1 TP-2 TP-3 TP-4 TP-5 TP-6 TP-7 TP-8
Matrik Koefisien Baris Kolom 62 746 260 260 77 760 479 479 100 1,000 300 1,000 627 1,665 400 2,000
Elemen Tidak Nol Jumlah Kepadatan 1,998 0.0432 1,228 0.0182 569 0.0097 1,887 0.0082 3,731 0.0373 2,821 0.0094 4,101 0.0039 7,254 0.0091
PEMECAHAN SISTEM PERSAMAAN LINEAR Pada algoritma metode interior point, waktu komputasi yang dibutuhkan sebagian besar digunakan untuk memecahkan SPL yang ada pada algoritma tersebut. Pada algoritma dual-affine scaling (Gambar II.1), SPL-nya terbentuk pada waktu mencari nilai dy (search direction) pada setiap iterasi k. (A Dk-2 AT) dy = b
(4.1)
di mana Dk adalah matrik skala untuk iterasi k (Gambar II.1), dan dy adalah arah pencarian (search direction). Dengan asumsi bahwa A adalah matrik yang full-rank, maka sistem (4.1) adalah sistem yang simetri dan definite positive [1]. Dan karena matrik A umumnya adalah matrik jarang (sparse) dan besar (large) maka SPL di atas adalah SPL yang large sparse symmetric definite positive. Metode langsung (direct method) yang banyak digunakan untuk memecahkan SPL yang symmetric definite positive adalah faktorisasi cholesky [3][5]. Secara umum ada 4 fase yang dilakukan dalam memecahkan SPL dengan menggunakan metode faktorisasi, yaitu : fase pengurutan (ordering), fase faktorisasi simbolik (symbolic factorization), fase faktorisasi numerik (numerical factorization) dan fase pencarian solusi [4]. Dua fase pertama hanya dilakukan sekali diawal iterasi, sementara fase ketiga dan keempat dilakukan pada setiap iterasi. Pada proses faktorisasi numerik digunakan metode modifikasi faktorisasi cholesky. Modifikasi dilakukan terhadap metode faktorisasi cholesky karena metode ini hanya bisa menyelesaikan SPL yang symmetric definite positive, sementara SPL pada algoritma dual-affine scaling dapat menjadi tidak symmetric definite positive walaupun matrik koefisien (A) full rank. Hal ini disebabkan karena SPL tersebut sering tidak stabil [11]. Tabel 4.1 merupakan hasil uji coba komputasi terhadap delapan masalah penguji yang diberikan [4]. Pada uji coba tersebut metode ordering yang digunakan adalah minimum degree ordering. Sementara proses faktorisasi numerik menggunakan metode modifikasi faktorisasi cholesky yang dikembangkan oleh wright [11]. Modifikasi dilakukan dengan cara mengganti pivot, yang menyebabkan kegagalan faktorisasi cholesky (sangat kecil), dengan suatu bilangan yang besar. Sementara elemen-elemen lain yang berhubungan dengan pivot tersebut diganti dengan nol. Tabel 4.1. Pemecahan SPL dengan Modifikasi Faktorisasi Cholesky No 1 2 3 4 5 6 7 8
Masalah Penguji TP-1 TP-2 TP-3 TP-4 TP-5 TP-6 TP-7 TP-8
Elemen Tidak Nol Jumlah Iterasi SPL Ordering % Fill-in Total Fase I 776 1,226 36.70 25 4 3,036 8,464 64.13 28 1 511 721 29.13 21 2 8,490 15,573 45.48 25 5 2,334 4,486 47.97 27 4 2,378 5,838 59.27 24 2 337,299 372,747 9.51 26 5 3,356 10,270 67.32 26 2
Waktu Komputasi Waktu CPU Flops 8.29 1,236,080 2.96 5,421,761 6.15 403,528 8.70 12,411,059 16.15 4,476,377 14.31 3,126,991 192.24 2,084,441,394 57.56 8,077,809
Nilai Objektif 8.3431033E+01 2.6000000E+02 1.4345821E+02 4.7900021E+02 1.0861600E+02 6.4177046E+02 1.5230797E+03 1.5230797E+03
PEMECAHAN SPL DENGAN METODE ITERATIVE Disamping dengan metode langsung, pemecahan SPL dapat juga dilakukan dengan menggunakan metode iterative. Metode iterative yang banyak digunakan untuk menyelesaikan SPL pada algoritma dual-affine scaling adalah metode preconditioned conjugate gradient. Alasan utama dari penggunaan metode ini adalah bahwa ordering tidak signifikan dalam mengurangi jumlah fill-in terutama untuk kasus di mana matrik koefisiennya padat (dense) [1]. Pada lingkungan Matlab, metode ini dapat diimplementasikan dengan menggunakan fungsi pcg() [10]. Tahap pertama uji coba, SPL diselesaikan dengan fungsi pcg() tanpa menggunakan preconditioner yang dikenal juga sebagai algoritma conjugate gradient. Dengan algoritma ini, kita dapat menghemat memori karena tidak terjadinya proses fill-in. Akan tetapi, waktu CPU yang dibutuhkan sangat besar jika dibandingkan dengan waktu CPU yang dibutuhkan oleh metode modifikasi faktorisasi cholesky. Disamping itu TP-4 dan TP-7 tidak dapat diselesaikan karena terjading kondisi yang tidak stabil (ill-condition) (Tabel 4.2). Tabel 4.2. Pemecahan SPL dengan Conjugate Gradient No 1 2 3 4 5 6 7 8
Masalah Penguji TP-1 TP-2 TP-3 TP-4 TP-5 TP-6 TP-7 TP-8
Elemen Tdk Nol Chol CG 1,226 776 8,464 3,036 721 511 15,573 8,490 4,486 2,334 5,838 2,378 372,747 337,299 10,270 3,356
Jumlah Iterasi Total Fase I 24 4 30 1 20 2 25 22
4 2
24
2
Waktu Komputasi Nilai Waktu CPU Flops Objektif 14.26 20,766,095 8.3430000E+01 32.96 198,169,814 2.6000000E+02 9.66 12,260,942 1.4346000E+02 33.51 81.78
135,443,449 1.0862000E+02 443,132,295 6.4177000E+02
248.86 1,403,636,246 1.5230800E+03
Tahap kedua uji coba, SPL diselesaikan dengan algoritma precondition conjugate gradient. Pada algoritma ini suatu preconditioner ditambahkan pada SPL. Preconditioner ini akan mengubah SPL 4.1 menjadi SPL 4.2. Selanjutnya SPL ini diselesaikan dengan menggunakan algoritma conjugate gradient. [R-1(A Dk-2 AT)(R’)-1] [R’dy] = [R-1b]
(4.2)
di mana R adalah suatu preconditioner. Salah satu preconditioner yang banyak digunakan untuk memecahkan SPL pada algoritma dual-affine scaling adalah incomplete cholesky factors [1][7]. Pada Matlab, pengimplementasian algoritma ini masih tetap menggunakan fungsi pcg(). Hanya saja diperlukan tambahan prosedur untuk mencari incomplete cholesky factors. Dalam hal ini menggunakan fungsi cholinc() [10].
Tabel 4.3 memperlihatkan adanya pengurangan waktu CPU dengan diberikannya preconditioner incomplete cholesky factor pada SPL. Selanjutnya kita dapat mengontrol jumlah elemen tidak nol pada incomplete cholesky factor berdasarkan nilai drop tolerance. Drop tolerance ini akan menentukan nilai tidak nol terkecil dari incomplete cholesky factor. Jika pada proses faktorisasi terdapat elemen tidak nol yang lebih kecil dari drop tolerance, maka elemen tersebut diganti dengan nol. Tabel 4.3 juga memperlihatkan pengaruh beberapa nilai drop tolerance dalam proses penyelesaian SPL. Terlihat terjadinya trade-off, di mana jika drop tolerance diperbesar maka jumlah elemen tidak nol (space memori) semakin kecil, akan tetapi waktu CPU-nya meningkat. Bahkan untuk nilai drop tolerance 5.10-2, untuk beberapa masalah penguji, waktu CPU-nya lebih besar dari waktu CPU pada metode conjugate gradient. Tabel 4.3. Pengaruh Drop Tolerance Terhadap Algoritma Preconditioned Conjugate Gradient No 1
Masalah Drop Penguji Tolerance TP-1 1.00E-08 1.00E-02 5.00E-02
Elemen Tidak Nol Chol IncChol 1,226 1,324 1,226 670 1,226 444
Jumlah Iterasi Total Fase I 25 4 25 4 25 4
Nilai Waktu Komputasi Waktu CPU Flops Objektif 9.28 1,766,971 8.3431033E+01 10.03 4,115,529 8.3431033E+01 10.56 5,256,616 8.3431033E+01
2
TP-2
1.00E-08 1.00E-02 5.00E-02
8,464 8,464 8,464
9,708 8,308 6,038
28 32 23
1 2 6
4.74 20.61 2,002.81
11,086,204 2.6000000E+02 98,420,696 2.6000000E+02 10,900,000,000 2.6000000E+02
3
TP-3
1.00E-08 1.00E-02 5.00E-02
721 721 721
787 779 647
21 21 21
2 2 2
6.72 7.87 8.77
620,029 1.4345821E+02 3,085,594 1.4345821E+02 4,994,809 1.4345821E+02
4
TP-4
1.00E-08 1.00E-02 5.00E-02
15,531 15,531 15,531
5
TP-5
1.00E-08 1.00E-02 5.00E-02
4,486 4,486 4,486
4,836 3,384 2,258
27 27 27
4 4 4
17.28 26.09 30.39
7,293,142 1.0861600E+02 60,427,927 1.0861600E+02 75,468,911 1.0861600E+02
6
TP-6
1.00E-08 1.00E-02 5.00E-02
5,838 5,838 5,838
6,674 4,964 3,332
24 24 24
2 2 2
15.49 35.77 78.36
5,181,979 6.4177046E+02 94,264,598 6.4177046E+02 263,737,472 6.4177046E+02
7
TP-7
1.00E-08 1.00E-02 5.00E-02
372,747 372,747 372,747
373,713 363,107 18,261
8
TP-8
1.00E-08 1.00E-02 5.00E-02
10,270 10,270 10,270
12,106 7,494 5,152
26 26 26
2 2 2
63.06 237.50 268.59
13,312,382 1.5230797E+03 835,528,431 1.5230797E+03 918,161,247 1.5230797E+03
Dari Tabel 4.3 juga terlihat bahwa untuk nilai drop tolerance lebih besar atau sama dengan 10-2, nilai element tidak nol (space memori) sudah cukup kecil dibandingkan dengan jumlah elemen tidak nol yang dihasilkan pada modifikasi faktorisasi cholesky. Akan tetapi waktu CPU-nya masih cukup besar. Selanjutnya dicoba untuk memperkecil waktu CPU dengan cara memperbesar nilai akurasi dari algoritma preconditioned conjugate gradient. Nilai drop tolerance yang dipilih adalah 10-2. Pemilihan nilai ini dilakukan dengan alasan bahwa dengan nilai tersebut, jumlah elemen tidak nol (space memori) dari incomplete cholesky factors sudah lebih kecil dari modifikasi faktorisasi cholesky dan waktu CPU-nya masih lebih kecil dari waktu CPU pada algoritma conjugate gradient. Tabel 4.4. Pengaruh Akurasi Terhadap Algoritma Preconditioned Conjugate Gradient No 1
Masalah Penguji TP-1
Akurasi
2
TP-2
1.00E-08 1.00E-06 1.00E-04
32 34 36
1 1 1
20.61 25.38 25.19
98,420,696 122,459,375 121,021,331
2.6000000E+02 2.6000000E+02 2.5999987E+02
3
TP-3
1.00E-08 1.00E-06 1.00E-04
21 21 21
2 2 2
7.87 7.62 7.56
3,085,594 2,792,386 2,586,611
1.4345821E+02 1.4345821E+02 1.4345906E+02
4
TP-4
1.00E-08 1.00E-06 1.00E-04
5
TP-5
1.00E-08 1.00E-06 1.00E-04
27 27 28
4 4 4
26.09 24.93 24.63
60,427,927 53,155,876 46,696,978
1.0861600E+02 1.0861600E+02 1.0861465E+02
6
TP-6
1.00E-08 1.00E-06 1.00E-04
24 24 24
2 2 2
35.77 34.18 31.14
94,264,598 86,784,947 72,846,880
6.4177046E+02 6.4177046E+02 6.4176542E+02
7
TP-7
1.00E-08 1.00E-06 1.00E-04
8
TP-8
1.00E-08 1.00E-06 1.00E-04
26 26 26
2 2 2
237.50 218.16 166.09
835,528,431 754,054,821 499,130,431
1.5230797E+03 1.5230798E+03 1.5230685E+03
1.00E-08 1.00E-06 1.00E-04
Jumlah Iterasi Total Fase I 25 4 25 4 25 4
Waktu Komputasi Waktu CPU Flops 10.03 4,115,529 10.04 3,783,940 9.96 3,323,772
Nilai Objektif 8.3431033E+01 8.3431048E+01 8.3431049E+01
Dari Tabel 4.4 terlihat adanya penurunan waktu CPU dengan memperbesar nilai akurasi. Akan tetapi pada nilai akurasi 10-4 nilai objektif dari pemrograman linear yang dihasilkan mulai mengalami perubahan. Dari hasil yang didapat terlihat bahwa untuk mendapatkan nilai objektif yang sama, waktu CPU dari metode ini masih lebih besar dari waktu CPU modifikasi faktorisasi cholesky walaupun dari segi space memori lebih kecil. Selain itu kita juga dapat melihat bahwa metode iterative ini sangat lambat dan cendrung gagal dalam memecahkan SPL yang ill-condition atau tidak definite positive (TP-2, TP-4 dan TP-7). Pada uji coba ini, algoritma mengalami stagnated (TP-2) atau tidak konvergen sampai dengan iterasi ke-100.000 (TP-4 dan TP-7).
KESIMPULAN Dari hasil-hasil yang didapat melalui uji coba seperti yang dideskripsikan pada bagian sebelumnya, ada beberapa hal yang perlu ditegaskan kembali pada bagian penutup ini, yaitu: 1. Penggunaaan metode conjugate gradient dalam menyelesaikan SPL pada Algoritma dual-affine scaling, walaupun efisien jika ditinjau dari segi space memori yang dibutuhkan akan tetapi sangat tidak efisien jika ditinjau dari segi waktu CPU yang dibutuhkan. 2. Penggunaan metode preconditioned conjugate gradient dapat mengurangi waktu CPU yang dibutuhkan oleh metode conjugate gradient, akan tetapi terjadi penambahan space memori pada proses pembentukan precondinioner-nya. Dalam hal ini adalah incomplete cholesky factors 3. Penggunaan metode preconditioned conjugate gradient dengan preconditioner incomplete cholesky factors dapat memiliki space memori yang lebih efisien dibandingkan dengan menggunakan metode modifikasi faktorisasi cholesky, akan tetapi tidak dapat mengungguli dari segi waktu CPU. Sehingga metode ini sangat cocok untuk pemrograman linear dengan matrik koefisien yang dense, di mana metode ordering tidak signifikan dalam mengurangi jumlah space memori yang dibutuhkan. 4. Metode preconditioned conjugate gradient sangat lambat dan cenderung gagal dalam menyelesaikan SPL yang ill condition atau tidak symmetric definite positive
DAFTAR PUSTAKA 1. ADLER, N. KARMARKAR, M.G.C. RESENDE and G. VEIGA, An Implementation of Karmarkar’s Algorithm For Linear Programming, Originally appeared in Mathematical Programming 44, (1989) (revised 1995) 2. DIKIN, l. l., Iterative Solution of Problems of Linear and Quadratic Programming, Soviet Mathematics Doklady, (1967) 674-675 3. DUFF, S and J.K. REID. Direct Method for Sparse Matrices. Clarendon Press, Oxford, (1986) 4. MURFI, H., T. BASARUDDIN, Implementasi Algoritma Dual-Affine Scaling Untuk Pemrograman Linear dengan Menggunakan Matlab. Prosiding Seminar Nasional dan Konferda Matematika Wilayah VII DIY dan Jawa Tengah, UIIYogyakarta. (2001) 5. GOLUB, G. H., C. F. V. LOAN. Matrix Computations. The Johns Hopkins University Press, Maryland, (1989) 6. KARMARKAR, N., New Polynomial-Time Algorithm for Linear Programming, Combinatorica 4, (1984) 373-395 7. MEHROTRA, S., Implementations of Affine Scaling Methods : Approximate Solutions of Systems of Linear Equations Using Preconditioned Conjugate Gradient Methods. ORSA Journal on Computing 4 (2) (1992) 8. MITCHELL, J.E., P.M. PARDALOS and M.G.C. RESENDE. Interior Point Methods for Combinatorial Optimization. Kluwer Academic Publishers (1998) 9. SAAD, Y. Iterative Methods Sparse Linear Systems. PWS Publishing Company, Boston (1986) 10. Team. Using Matlab. The Math Works Inc, Natick (1998) 11. WRIGHT, S.J. Modified Cholesky Factorizations in Interior-Point Algorithms for Linear Programming. Mathematical and Computer Science Division, Argonne National Laboratory, (1997)
HOME
KOMPUTASI DALAM SAINS DAN TEKNOLOGI NUKLIR XII
