SISFO-Jurnal Sistem Informasi
PEMROGRAMAN LINIER VERSUS PEMROGRAMAN KUADRATIK KONVEKS Wiwik Anggraeni Jurusan Sistem Informasi Fakultas Teknologi Informasi, Institut Teknologi Sepuluh Nopember Kampus ITS Sukolilo, Surabaya, 60111 E-mail :
[email protected]
Abstrak Dengan adanya kemajuan yang pesat di dalam Very-Large-Scale Integration (VLSI) , dalam beberapa tahun terakhir telah berkembang suatu sistem komputasi terdistribusi. Salah satu permasalahan yang dihadapi sistem komputasi tersebut adalah masalah pengalokasian modul program, atau biasa disebut dengan Module Allocation with Non-Uniform communication cost(MAPNU) yaitu bagaimana menempatkan sebuah modul program ke sebuah prosesor sehingga total biaya eksekusi dan komunikasi antar prosesor adalah minimum. Permasalahan ini secara alami diformulasikan sebagai permasalahan kuadratik 0-1 dengan batasan linear. Dalam tulisan ini, diperbandingkan dua metode solusi untuk permasalahan ini. Metode pertama berdasarkan pemrograman linear (Mixed Integer Linear Programming). Yang kedua, menggunakan pemrograman kuadratik (Mixed Integer Quadratic Programming). Kedua metode tersebut dapat diterapkan dengan menggunakan perangkat lunak optimasi yang ada. Setiap metode dijelaskan dan dilakukan perbandingan komputasional antar metode dalam menyelesaikan masalah MAPNU. Percobaan dilakukan dengan jumlah instance ang berbeda-dengan dengan jumlah prosesor serta task yang bervariasi. Dari beberapa kali ujicoba ditunjukkan bahwa ternyata metode pemrograman kuadratik mempunyai hasil lebih optimal 32.6% dibanding prmrograman linier. Kata kunci : VLSI, MAPNU, pemrogrman linier, pemrograman kuadratik, konveks
1. PENDAHULUAN Very-Large-Scale Integration (VLSI) adalah proses untuk membuat sebuah rangkaian terpadu dengan mengkombinasikan ribuan rangkaian transistor kedalam satu chip. Mikroprosesor komputer adalah sebuah contoh VLSI. Dengan adanya kemajuan teknologi, VLSI tidak lagi sebuah chip yang menampung ribuan rangkaian transistor, tetapi sudah mencapai ratusan juta transistor dalam setiap chipnya. Dengan adanya kemajuan yang pesat di dalam VLSI tersebut, dalam beberapa tahun terakhir telah berkembang suatu sistem komputasi terdistribusi. Salah satu permasalahan yang dihadapi sistem komputasi tersebut adalah masalah pengalokasian modul program, yaitu bagaimana menempatkan sebuah modul program ke sebuah prosesor sehingga total biaya eksekusi dan komunikasi antar prosesor adalah minimum. Beberapa penyelesaian permasalahan ini telah dipertimbangkan dengan asumsi yang berbeda berdasarkan arsitektur dari sistem terdistribusi atau struktur dari biaya dan solusi yang mungkin dilakukan. Dalam tulisan ini, permasalahan yang
diangkat adalah MAPNU (Module Allocation Program with Non-Uniform communication cost), program pengalokasian modul dengan biaya komunikasi non-uniform, Dalam permasalahan ini, tidak ada asumsi istimewa dibuat untuk biaya komunikasi dan eksekusi, dan tidak ada batasan kapasitas yang menjadi pertimbangan. MAPNU secara alami diformulasikan sebagai permasalahan kuadratik 0-1 dengan batasan linear, Permasalahan ini dikenal juga dalam literatur sebagai permasalahan kuadratik semiassignment. Dalam tulisan ini, diperbandingan dua metode solusi untuk mengatasi permasalahan tersebut. 2. PEMROGRAMAN LINIER PEMROGRAMAN KUADRATIK
VS
2.1 Pemrograman Linier
Di dalam matematika, Linear Programing (LP) digunakan untuk menyelesaikan permasalahan optimasi dengan fungsi tujuan yang linier serta
49
SISFO-Jurnal Sistem Informasi batasan yang berupa pertidaksamaan linier juga.
persamaan
dan
Program linear dapat di fomulasikan sebagai berikut : • •
Maksimalkan cTx Dengan batasan-batasan : • •
2.2 Optimasi Konveks
Ax ≤ b x≥0
Dengan x mewakili vektor variabel, c dan b merupakan vektor koefisien sedangkan A adalah matriks koefisien. Pemrograman linier (Linear Programming) memegang peranan penting dalam masalah optimasi, banyak permasalahan praktikal dalam riset operasi yang dapat di ekspresikan sebagai permasalahan program linier. Terdapat kasus-kasus khusus di dalam pemrograman linier (linear programming) seperti network flow problems dan multicommodity flow problems yang telah melahirkan banyak algoritma penting di dunia komputasi matematika seperti algoritma duality, dekomposisi, dan algoritma konveksitas. 2.1.1 Formulasi Standar
Formulasi standar adalah formulasi matematis yang sering digunakan untuk mengekspresikan permasalahan program linear, formulasi standar ini terdiri atas 3 bagian, yaitu: •
Variabel Keputusan Variabel keputusan biasanya mewakili apa yang ingin kita tentukan.
•
Fungsi Tujuan
Batasan, biasanya sebagai berikut
Optimasi konveks adalah bagian dari matematika konveks, diberikan vector ruang X dengan fungsi
sebagai subset konveks dari X, Definisikan maka permasalahan ini ditujukan untuk mencari titik
didalam
dimana akan menghasilkan
terkecil. 2.2.1. Formulasi Standar
Formulasi standar adalah formulasi matematis yang sering digunakan untuk mengekspresikan permasalahan optimasi konveks • Fungsi konveks diminimalkan terhadap x • Batasan dimana
pertidaksamaan
akan
,
adalah konveks
• Batasan persamaan hi(x) = 0, dimana h bersifat affine, didalam prakteknya linear dan affine adalah equivalen dan sering dtuliskan dengan adalah matriks sebagai dan adalah vector Sehingga permasalahan optimasi konveks dapat dtuliskan sebagai berikut:
Memaksimalkan •
Formulasi lain seperti permasalahan minimasi ataupun permasalahan yang melibatkan variable negatif selalu dapat ditulis ulang dalam bentuk formulasi standar.
di
formulasikan
o
Minimalkan
o
Dengan batasan
2.3
Pemrograman Programing)
o o o Batasan Non-Negatif o o Biasanya, permasalahan yang kita punyai diubah terlebih dulu dalam bentuk matriks menjadi sebagai berikut :
50
o
Maksimalkan
o
Dengan batasan
Kuadratik
(Quadratic
Quadratic programming (QP) adalah tipe special dari permasalahan optimasi matematika, permasalahan ini dapt diformulasikan sebagai berikut
SISFO-Jurnal Sistem Informasi
Asumsikan x terdapat pada ruang , Q adalah matrix simetris n x n, dan c adalah sembarang vector n x 1 •
Minimalkan terhadap x
•
Dengan batasan :
MAPNU dapat diformulasikan permasalahan quadratic 0-1 : T
Ex = d (persamaan)
Dengan
sebagai
P
∑x
P = { p1 , p2 ,…, pP } dan T = {t1 , t 2 ,…, tT }
P sebagai T
sebagai
prosesor modul program yang ditetapkan untuk tiap prosesor. Kemudian sebagai qtp t = 1,…, T , p = 1,…, P
)
t pada prosesor p
ctpt ' p ' (t , t ' = 1,…, T , t ≠ t ' , p, p' = 1, …, P ) sebagai communication cost yang terjadi ketika modul t dan t ' masing – masing ditetapkan untuk prosesor
p dan p ' . Nilai q tp dan c tpt ' p '
dapat bernilai positif atau negatif. Formulasi metematika dari CMAP dapat dipertimbangkan dengan membuat variabel vektor x = xtp t = 1,…, T ; p = 1, …, P
( )(
T
P
P
tp
t =1 t '=t +1 p =1 p '=1
t = 1,…, T
=1
(2)
p =1
x ∈ {0,1}T ×P Batasan (2) menandakan bahwa setiap modul t dialokasikan tepat untuk satu prosesor. Bagian pertama dari fungsi objective (1) adalah total execution cost dan bagian kedua adalah total communication cost. 3.2 Metode Pemrograman Linier
Metode ini disusun menjadi 2 tahap. Pertama adalah operasi penurunan rumus dari Q01 . Algoritma yang digunakan untuk penyelesaian penurunan rumus ini adalah DAMATH yang telah terbukti optimal.
)
)
3.2.1 Tahap Penurunan Rumus
Diketahui
(D ) sebagai linear problem : T
(D ) : max ∑ λt t =1
batasan :
3.1 Pemodelan Permasalahan Sebagai Program Kuadratik 0-1
execution cost dari modul dan
T −1
(
Pertama-tama, permasalahan MAPNU harus dimodelkan terlebih dahulu ke dalam program kuadratik 0-1 agar dapat diselesaikan oleh metode pemrograman linier dan pemrograman kuadratik. Kemudian kedua buah metode yang telah dirumuskan diselesaikan dengan menggunakan solver yaitu MILP solver untuk program linear dan MIQP solver untuk program kuadratik.
(
t =1 p =1
Batasan.:
sebagai transpose dari vektor
PERANCANGAN
Diketahui
P
(Q01) : min F (x ) = ∑∑ qtp xtp + ∑ ∑ ∑∑ ctpt ' p' xtp(1) xt ' p '
Jika Q adalah matriks semidefinit positif, maka f(x) adalah fungsi yang konveks. Untuk kasus ini QP memiliki global optimizer jika setidaknya terdapat 1 vector 'x' yang memenuhi batasan. Jika Q definit positif maka QP memiliki global optimizer yang unik. Sedangakan jika Q adalah matriks 0 (zero) maka permasalahan akan berubah menjadi Linear Programing. Dari teori optimasi syarat bagi x untuk menjadi Global minimizer adalah x harus memenuhi kondisi Karush-Kuhn-Tucker (KKT). Convex Quadratic Programming adalah kasus special dari Optimasi Konveks. 3.
dan sebaliknya.
(pertidaksamaan)
o o
xtp sama dengan 1 jika modul t dialokasikan untuk prosesor p yang bernilai 0
dimana
t −1
T
λt − ∑ β t 'tp − ∑ β t 'tp + vtp = qtp t = 1,t… '=1 , T ; p =t '=1t,+… 1 ,P
β tt ' p ' + β t 'tp + δ tpt ' p ' = ctpt ' p ' 1 ≤ t ' < t ≤ T ; p, p' = 1,…, P v ≥ 0, δ ≥ 0
v(D) memiliki nilai optimal. Berdasarkan hasil
pembuktian bahwa solusi optimal lainnya untuk menetapkan atau mempengaruhi D
( )
penurunan dari
(Q01).
Hasil penurunan rumus diatas selanjutnya digunakan untuk menggantikan fungsi obyektif F x dengan persamaan baru (3) , kemudian
()
51
SISFO-Jurnal Sistem Informasi
didapatkan nilai penurunan problem
(
)
sama dengan Q01 . Untuk selanjutnya akan digunakan v.
(Q01r )
ke
tahap
~ xtp = 0 , dengan definisi dari φ tp ,
(4). Jika
batasan (4) dipengaruhi oleh batasan tidak negative. Oleh karena itu, problem Lφ , Q01 r , Q01 , memiliki nilai optimal
( )(
T
P
T −1 P
T
P
F (x ) = v(D ) + ∑ ∑ vtp xtp + ∑∑ ∑ ∑ δ tpt ' p ' xtp xt ' p ' (3) t =1 p =1 t =1 p =1 t '=t +1 p '=1 3.2.2 Fase MILP
Pada teknik linear telah diinisialisasi oleh Glover [7]. Metode ini telah digunakan untuk contoh pada [3] untuk masalah quadratic knapsack. Ide utama, digunakan untuk problem Q01 r untuk menggantikan persamaan
(
)
⎛ T P ⎞ ⎜ ∑ ∑ δ tpt ' p ' xtp xt ' p ' ⎟ dengan variable unik ⎜ ⎟ ⎝ t '=t +1 p '=1 ⎠ htp , dimana t = 1,…, T − 1; p = 1,…, P . Misalkan
φ
T
φtp =
dimana
∑ max (δ
t '=t +1
(L )
T×P
menunjukkan vektor p '=1.. p
tpt ' p '
)
dan misal
digunakan untuk mixed integer linear
φ
problem: P
(L ): min Δ(x, h) = v(D) + ∑ ∑ v φ
t =1 p =1
T −1 P
x + ∑∑ htp
tp tp
t =1 p =1
3.3 Metode Quadratic Programming
Metode ini terdiri dari 2 tahap, tahap pertama ditujukan untuk merubah fungsi tujuan Q01 menjadi fungsi kuadrat konveks. Dimana dengan merubah fungsi tujuan ini akan menghasilkan formula baru yang memiliki tractable continuous relaxation, yang dapat diletakkan pada logaritma branch-and-bound.
(
Algoritma yang referensi [2].
digunakan
berdasar
)
pada
3.3.1 Tahap Reformulasi
Asumsikan (SD) sebagai program semidefinit berikut : (SD):Minimalkan T
P
T −1
T
P
P
∑∑ qtp xtp + ∑ ∑ ∑∑ ctpt' p' X tpt' p' t =1 t '=t +1 p =1 p '=1
Dengan batasan : P
∑X
tpt ' p '
=xtp
t = 1,...,T
t’ = 1,...,T
p '=1
Batasan : P
X tptp
t = 1,…, T
=1
tp
)
yang sama.
t =1 p =1
T
∑x
) (
p = 1,...,P t = 1,...,T = xtp
p = 1,...,P
p =1
T
htp ≥ 0 t = 1,…, T − 1; p = 1,…, P xtp ∈ {0,1} t = 1,…, T ; p = 1,…, P Tiap
solusi
~ x
untuk
solusi optimal
dari
~ h=
( )
t '=t +1 p '=1
x x
tpt ' p ' tp t ' p '
untuk
memperoleh
(L ) φ
P
∑ ∑δ
.Jika
dengan
~ xtp = 1 ,
~ htp memenuhi nilai paling rendah untuk batasan
52
(
*
*
)
)
Asumsikan α ,u adalah solusi optimal dari dual (SD). Kita dapat menghasilkan formulasi kuadratic 0-1 berikut :
(CQ01) : minimalkan
optimal
~ ~ x,h
(4)
(5)
(Q01)r dimungkinkan T
(
P
htp ≥ ∑ ∑ δ tpt ' p ' xt ' p ' − φtp (1 − xtp ) t = 1,… t '=t,+T 1 p '− =11; p = 1, …, P
X adalah matriks simetris (T x P). (SD) dapat dianggap sebagai bagian relaksasi progaram semidefinit dari Q01 . Sebagaimana pada referensi [5], sembarang solusi optimal dari permasalahan dualnya akan menghasilkan formulasi konveks dari fungsi tujuan.
T T P ⎛ P ⎞ T P * * F α u (x ) = F (x ) + ∑∑∑α tpt* ' xtp ⎜⎜ ∑ xt ' p' − 1⎟⎟ + ∑∑ utp* xtp2 − xtp t =1 t '=1 p =1 ⎝ p'=1 ⎠ t =1 p=1 (6) Dengan batasan
(
P
∑x
tp
=1
t = 1,…, T x ∈ {0,1}T ×P
p =1
Problem
(CQ01) sama dengan (Q01).
)
SISFO-Jurnal Sistem Informasi
*
*
F α ,u adalah convex, nilai optimal dari (CQ01) sama dengan nilai (SD).
Fungsi
3.3.2 Fase MIQP
Pada fase ini dapat diselesaikan dengan algoritma branch-and-bound dimana prosesnya dapat dilakukan berdasarkan relaxation continuous. 4. UJI COBA Data yang digunakan untuk uji coba ini diambil dari http://cedric.cnam.fr/oc/TAP/TAP.html, dimana koefisien dari q tp dan c tpt ' p ' adalah hasil dari pembangkitan acak antara interval [50,50]. Data ini berisi sejumlah task, sejumlah prosesor dan koefisien q tp dan c tpt ' p ' Untuk memecahkan masalah yang berbentuk Linear Programming (LPs), Mix Integer Linear Programming (MILPs), Mix Integer Quadratic Programming (MIQPs) Hasil dari uji coba yang dilakukan ditunjukkan pada tabel berikut Tabel 1. Solusi eksak dari instance dengan Linear Programming Instance Tassnu 15-5-1 Tassnu 15-5-2 Tassnu 15-5-3 Ratarata Tassnu 15-5-1 Tassnu 15-5-2 Tassnu 15-5-3 Ratarata Tassnu 15-5-1 Tassnu 15-5-2 Tassnu 15-5-3 Ratarata
T
P
Optimal
SD
Gap(%)
CPU(s)
15
5
-1980
-2362
19
8
15
5
-1568
-2155
36
23
15
5
-1892
-2431
27
16
-2316
27.333
15.67
18
4
-2135
-2657
24
25
18
4
-1936
-2358
22
33
18
4
-2300
-2741
15
16
-2585
20.333
24.67
20
5
-2585
-3561
38
320
20
5
-25811
-3781
46
390
20
5
-2511
-3529
26
755
-3624
36.667
488.3
Tabel 2. Solusi eksak dari instance dengan Quadratik Programming Instance Tassnu 15-5-1 Tassnu 15-5-2 Tassnu 15-5-3 Ratarata Tassnu 15-5-1 Tassnu 15-5-2 Tassnu 15-5-3 Ratarata Tassnu 15-5-1 Tassnu 15-5-2 Tassnu 15-5-3 Ratarata
T
P
Optimal
V(D)
Gap(%)
CPU(s)
15
5
-1980
-2946
48
13
15
5
-1568
-2755
76
19
15
5
-1892
-2946
56
24
-2882
60
18.67
18
4
-2135
-3650
71
50
18
4
-1936
-3459
79
38
18
4
-2300
-3759
63
13
-3623
71
33.67
20
5
-2585
-5040
95
1672
20
5
-25811
-5155
99
1487
20
5
-2511
-4981
77
1765
-5058
90.333
1641
Tabel 1 dan 2 diatas memberikan data hasil dari dua metode pada instance yang digunakan. Tabel 1 menggunakan linear programming dan table 2 Quadratik Programming. menggunakan Pada kolom pertama, yaitu kolom instance, berisi nama instance yang digunakan. Kolom T menunjukkan jumlah dari task atau modul, kolom P menunjukkan jumlah prosesor dan kolom terakhir menunjukkan hasil nilai optimal dari instance tersebut. Kolom gap menyatakan nilai prosentase dari selisih yang terkait dengan kolom bound v(D) pada metode yang berdasarkan Linear Programming dan kolom bound v(SD) pada metode berbasis Quadratik Programming. Dari tabel diatas dapat diketahui bahwa selisih yang dimiliki metode berbasis Quadratik Programming lebih baik dibandingkan selisih metode berbasis linear programming. 5. SIMPULAN 1. Permasalahan MAPNU (Module Allocation Problem with Non-Uniform communication cost) dapat diselesaikan dengan metode linear programming dan Quadratic Programming dimana masing-masing
53
SISFO-Jurnal Sistem Informasi metode mempunyai biaya komputasi yang berbeda. 2. Metode quadratik programming lebih optimal untuk biaya komputasional dari pada metode linear programming. 3. Dilihat dari segi dihasilkan, metode lebih bagus dari programming. Hal selisih gap sebesar sebesar 3 % 6.
gap dan cpu yang quadratik programming pada metode linear ini dapat dilihat dari 32.6% dan selisih CPU
DAFTAR PUSTAKA
A. Billionnet and S. Elloumi. 2001. Best reduction of the quadratic semi-assignment problem. DAMATH: Discrete Applied Mathematics and Combinatorial Operations Research and Computer Science, 109:197–213, 2001. A. Billionnet, S. Elloumi, and M.C. Plateau. 2005. Convex quadratic programming for exact solution of 0-1 quadratic programs. Technical Report 000, CEDRIC. A. Billionnet and E. Soutif. Using a mixed integer programming tool for solving the 0-1 quadratic knapsack problem. Forthcoming in INFORMS Journal on Computing. W. Fernandez de la Vega and M.Lamari. 2003. The task allocation problem with constant communication. Discrete Applied Mathematics, In Press. S. Elloumi. The task assignment problem, a library of instances. [Online], Available at:
Wikipedia. Very Large Scale Integration. [Online], Available at : . Wikipedia. Linear Programming. [Online], Available at : . Wikipedia. Convex Optimization. [Online], Available at : . Wikipedia. Quadratic Programming. [Online], Available at : .
54
