PENGEMBANGAN METODE PENDEKATAN PENCARIAN LAYAK UNTUK MENYELESAIKAN PROBLEMA PROGRAM INTEGER TAK LINIER
TESIS
Oleh
MARLINA SETIA SINAGA 067021005/MT
SEKOLAH PASCASARJANA UNIVERSITAS SUMATERA UTARA MEDAN
2008
2
PENGEMBANGAN METODE PENDEKATAN PENCARIAN LAYAK UNTUK MENYELESAIKAN PROBLEMA PROGRAM INTEGER TAK LINIER
TESIS
Untuk Memperoleh Gelar Magister Sains dalam Program Studi Magister Matematika pada Sekolah Pascasarjana Universitas Sumatera Utara
Oleh
MARLINA SETIA SINAGA 067021005/MT
SEKOLAH PASCASARJANA UNIVERSITAS SUMATERA UTARA MEDAN 2008
Judul Tesis
: PENGEMBANGAN METODE PENDEKATAN PENCARIAN LAYAK UNTUK MENYELESAIKAN PROBLEMA PROGRAM INTEGER TAK LINIER Nama Mahasiswa : Marlina Setia Sinaga Nomor Pokok : 067021005 Program Studi : Matematika
Menyetujui, Komisi Pembimbing
(Prof. Dr. Herman Mawengkang) Ketua
(Dr. Saib Suwilo, M.Sc) Anggota
Ketua Program Studi,
Direktur,
(Prof. Dr. Herman Mawengkang)
(Prof. Dr. Ir. T.Chairun Nisa. B,M.Sc)
Tanggal lulus: 15 Juli 2008
Telah diuji pada Tanggal 15 Juli 2008
PANITIA PENGUJI TESIS
Ketua
: Prof. Dr. Herman Mawengkang
Anggota
: 1. Dr. Saib Suwilo, M.Sc 2. Drs. Opim Salim S., MIkom, PhD 3. Dra. Esther Nababan, M.Sc
ABSTRAK Problema program tak linier pada tesis ini memisahkan antara peubah-peubah linier yang diskrit dengan peubah-peubah tak linier yang kontinu. Strategi yang dikembangkan adalah pelepasan peubah nonbasis dari batasannya dikombinasi dengan metode kendala aktif dan superbasis. Strategi ini digunakan untuk memaksa peubah-peubah basis non-integer bergerak ke daerah integer. Proses pengintegeran ini dilakukan juga dengan studi kriteria pemilihan peubah nonbasis. Berbagai uji problema telah berhasil dengan menggunakan algoritma ini, hingga dapat dikatakan bahwa strategi peng-integer-an mampu untuk mentekel problema program integer campuran. Kata Kunci : Program Taklinier, Superbasis.
i
ABSTRACT The special nonlinear mathematical programming problem which is addressed in this thesis has a structure characterized by a subset of variables restricted to assume discrete values, which are linear and seperable from the continuous variables. The strategy of releasing nonbasic variables from their bounds, combined with the ”active constraint” method and the notion of superbasics, has been developed for efficienty requirements, this strategy is used to force the appropriate non-integer basic variables to move to their neighbourgood integer points. A study of criteria for choosing a nonbasic variable to work with in the integerizing strategy has also been made. Successful implementation of these algorithms was achieved on various test problems. The result show that the proposed integerizing strategy is promosing in tackling certain classes of mixed integer programming problems. Keywords : Nonlinear Program, Superbasics
ii
KATA PENGANTAR Dengan rendah hati, penulis mengucapkan puji dan syukur kepada Tuhan Yang Maha Pengasih atas limpah kasih karunia dan berkatNya sehingga penulis dapat menyelesaikan tesis ini dengan judul ”Pengembangan Metode Pendekatan Pencarian Layak Untuk Menyelesaikan Problema Program Integer Tak Linier”. Tesis ini merupakan persyaratan tugas akhir pada Program Studi Matematika SPs Universitas Sumatera Utara. Pada kesempatan ini dengan tulus penulis mengucapkan terimakasih dan penghargaan yang tinggi kepada: Prof. dr. Chairuddin P. Lubis, DTM&H, Sp.A(K) selaku Rektor Universitas Sumatera Utara. Prof. Dr. Ir. T. Chairun Nisa B., M.Sc selaku Direktur Sekolah Pascasarjana yang telah memberikan kesempatan kepada penulis untuk mengikuti Program Studi Magister Matematika di Sekolah Pascasarjana Universitas Sumatera Utara Medan. Prof.
Dr.
Herman Mawengkang selaku ketua Program Studi Magister
Matematika SPs Universitas Sumatera Utara, dan juga sebagai ketua komisi pembimbing yang telah banyak membantu dalam penulisan tesis ini. Dr. Saib Suwilo, M.Sc selaku sekretaris Program Magister Matematika SPs Universitas Sumatera Utara, dan juga sebagai anggota komisi pembimbing yang telah banyak membantu dalam penulisan tesis ini.
iii
Seluruh staf pengajar pada Program Studi Magister Matematika SPs Universitas Sumatera Utara, yang telah banyak memberikan ilmu selama masa perkuliahan. Seluruh rekan-rekan mahasiswa angkatan kelima tahun 2006/2007 Program Studi Magister Matematika SPs Universitas Sumatera Utara atas kerjasama dan kebersamaan selama masa perkuliahan. Misiani, S.Si selaku staf Administrasi Program Studi Magister Matematika SPs Universitas Sumatera Utara yang telah memberikan pelayanan yang baik; secara khusus penulis menyampaikan rasa terimakasih kepada Bapa tersayang Asmin B. Sinaga dan suami tercinta Parlindungan Manurung, SE atas dukungan doa dan perhatian, serta seluruh keluarga atas semangat yang diberikan; akhirnya dengan penuh rasa haru penulis menyelesaikan tesis ini dengan mengenang semua jasa baik almarhum mama tersayang Tornauli br Situmorang. Semoga tesis ini bermanfaat bagi pembaca dan pihak-pihak yang memerlukannya.
Medan,
Juli 2008
Penulis,
Marlina Setia Sinaga
iv
RIWAYAT HIDUP Marlina Setia Sinaga dilahirkan di Tarutung pada tanggal 27 Mei 1974 dan merupakan anak ke 5 dari 6 bersaudara dari Ayah Asmin B. Sinaga dan Ibu Tornauli br. Situmorang. Menamatkan Sekolah Dasar (SD) St. Antonius V Medan pada tahun 1986, Sekolah Menengah Pertama (SMP) Tri Sakti Medan pada tahun 1989 dan Sekolah Menengah Atas (SMA) Negeri 5 Medan jurusan Fisika pada tahun 1992. Tahun 1992 memasuki Perguruan Tinggi Negeri Universitas Sumatera Utara Fakultas Matematika Ilmu Pengetahuan Alam (FMIPA) jurusan Matematika dan memperoleh gelar sarjana pada tahun 1998. Pada tahun 2005 diangkat menjadi dosen Universitas Nusa Cendana (Undana) Kupang NTT. Pada tahun 2006 menikah dengan Parlindungan Manurung, SE. Pada tahun 2006 mengikuti pendidikan Program Studi Magister Matematika di Sekolah Pascasarjana Universitas Sumatera Utara.
v
DAFTAR ISI Halaman ABSTRAK . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
i
ABSTRACT . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
ii
KATA PENGANTAR . . . . . . . . . . . . . . . . . . . . . . . . .
iii
RIWAYAT HIDUP . . . . . . . . . . . . . . . . . . . . . . . . . .
v
DAFTAR ISI . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
vi
DAFTAR TABEL . . . . . . . . . . . . . . . . . . . . . . . . . . .
ix
DAFTAR GAMBAR . . . . . . . . . . . . . . . . . . . . . . . . .
x
BAB 1 PENDAHULUAN . . . . . . . . . . . . . . . . . . . . . . .
1
1.1 Latar Belakang . . . . . . . . . . . . . . . . . . . . . . .
1
1.2 Perumusan Masalah . . . . . . . . . . . . . . . . . . . .
3
1.3 Tujuan Penelitian . . . . . . . . . . . . . . . . . . . . .
3
1.4 Kontribusi Penelitian . . . . . . . . . . . . . . . . . . . .
3
1.5 Metodologi Penelitian . . . . . . . . . . . . . . . . . . .
3
BAB 2 BEBERAPA MODEL KELAS PROBLEMA OPTIMISASI . . .
5
2.1 Optimum Lokal dan Global . . . . . . . . . . . . . . . . .
5
2.2 Kemulusan . . . . . . . . . . . . . . . . . . . . . . . . .
6
2.3 Kendala . . . . . . . . . . . . . . . . . . . . . . . . . .
6
2.4 Konveks . . . . . . . . . . . . . . . . . . . . . . . . . .
7
2.5 Optimisasi Diskrit . . . . . . . . . . . . . . . . . . . . .
8
2.6 Contoh-contoh Optimisasi . . . . . . . . . . . . . . . . .
8
2.6.1 Fungsi Kuadratik; Kendala dengan Batas Sederhana .
8
vi
2.6.2 Problema Integer Tak linier . . . . . . . . . . . . .
10
2.7 Optimisasi Global . . . . . . . . . . . . . . . . . . . . .
13
2.8 Branch and Bound untuk Problema Tak linier . . . . . . . .
14
2.9 Pendekatan pada Optimisasi Tanpa Kendala . . . . . . . .
16
2.10 Pendekatan pada Optimisasi dengan Kendala-Syarat KuhnTucker . . . . . . . . . . . . . . . . . . . . . . . . . . .
19
2.10.1 Kendala Persamaan Tak linier . . . . . . . . . . . .
20
2.10.2 Kendala Pertidaksamaan Tak Linier . . . . . . . . .
23
2.11 Algoritma yang Tersedia untuk Optimisasi Tak linier Kontinu
25
2.11.1 Metode 1-Dimensi . . . . . . . . . . . . . . . . . .
25
2.11.2 Model Skema Algoritma Descent (Tanpa Kendala) . .
25
2.12 Algoritma yang Tersedia untuk Optimisasi Tak linier Diskrit
30
2.12.1 Algoritma Pendekatan Luar Duran and Grossmann . .
30
2.12.2 Metode Mawengkang and Murtagh . . . . . . . . . .
32
2.12.3 Pendekatan-Pendekatan Lain
. . . . . . . . . . . .
32
BAB 3 HEURISTIK PENCARIAN LANGSUNG . . . . . . . . . . .
34
3.1 Model Problema . . . . . . . . . . . . . . . . . . . . . .
34
3.2 CYCLE1-Mengeluarkan Peubah Integer dari Basis
. . . . .
38
3.3 CYCLE2 Pass1-Sesuaikan Superbasis Tak Layak Integer . . .
44
3.4 CYCLE 2 Pass 2-Sesuaikan Superbasis Layak Integer . . . .
47
3.5 Analisa dan Contoh Penyangkal untuk Algoritma Murtagh
.
48
3.5.1 Contoh 1 . . . . . . . . . . . . . . . . . . . . . .
51
3.5.2 Contoh 2 . . . . . . . . . . . . . . . . . . . . . .
52
3.5.3 Contoh 3 . . . . . . . . . . . . . . . . . . . . . .
56
vii
3.5.4 Ringkasan Hasil Contoh CYCLE1 . . . . . . . . . .
57
BAB 4 KESIMPULAN . . . . . . . . . . . . . . . . . . . . . . . .
59
DAFTAR PUSTAKA . . . . . . . . . . . . . . . . . . . . . . . . .
60
viii
DAFTAR TABEL
Nomor
Judul
Halaman
3.1
Himpunan indeks untuk pembagian simplek yang diperluas
. .
37
3.2
Memindahkan peubah integer dari basis-memilih nonbasis noninteger xj , j ∗ ∈ (JL ∪ JU ) − JI ) dilepaskan dari batasnya. . . .
43
Penyelesaian Problema dengan Pencarian Langsung . . . . . .
58
3.3
ix
DAFTAR GAMBAR
Nomor
Judul
Halaman
2.1
Fungsi Kuadratik dengan Kendala-Kasus 1 . . . . . . . . . .
9
2.2
Fungsi Kuadratik dengan Kendala-Kasus 2 . . . . . . . . . .
9
2.3
Langkah Bebas dan Langkah Gabungan . . . . . . . . . . .
11
2.4
Contoh Integer Kuadratik . . . . . . . . . . . . . . . . . .
12
2.5
Skema Descent . . . . . . . . . . . . . . . . . . . . . . .
26
x
BAB 1 PENDAHULUAN
1.1 Latar Belakang Problema Program Integer Tak Linier (PITL) banyak menarik perhatian para peneliti karena berbagai aplikasinya pada dunia nyata. Aplikasi model PITL pada industri nuklir dengan memaksimumkan efisiensi atau kinerja reaktor nuklir setelah operasi pemuatan (Quist et al., 1997). Dalam industri kertas aplikasi model PITL muncul sebagai problema cutting stock tak linier (Harjunkoski et al., 1998). Sementara aplikasi dalam finansial seperti perencanaan strategis rancangan telekomunikasi, dengan aspek cacah menyajikan jumlah serat optik yang akan ditempatkan dalam pipa dan nonlinearitas muncul dari elastisitas yang berkenaan dengan strategis harga masa datang (Horner, 2000), juga dikemukakan dalam problema alokasi asset pada manajemen dana, dengan fungsi tujuan meminimumkan resiko. Aplikasi dalam bidang optimasi topologi (Sigmund, 2000) peubah biner memodelkan ada atau tidaknya material dalam setiap elemen hingga. PITL merupakan problema optimasi tak linier dengan bentuk umum: min z = f (x, y) kendala g(x, y) ≤ 0 x ∈ X, y ∈ Y dimana X dan Y adalah himpunan bilangan cacah atau biner (0-1). Metode Branch and Bound merupakan metode baku untuk menyelesaikan problema program integer tak linier, akan tetapi secara komputasi metode ini 1
2 tidak efisien karena subproblema harus diselesaikan pada setiap pencabangan. Model di atas tidak mengandaikan bahwa relaksasi kontinu dari problema merupakan problema program konveks. Pada aplikasi tertentu peubah-peubahnya dapat bernilai diskrit dan kontinu, dan jika demikian maka problema tersebut merupakan Program Integer Tak Linier Campuran (PITLC). Model problema yang dibahas pada tesis ini dibatasi hanya untuk peubah-peubah diskrit yang terpisah dengan peubah-peubah kontinu. Dapat dituliskan sebagai berikut: minimum f 0 (xN ) + cT xL n x∈R
dengan kendala f (xN ) + A1 xL = b1
(m1 baris )
A2 x N + A3 x L = b 2
(m2 baris )
(P)
l ≤ x ≤ u (m = m1 + m2) xj integer , j ∈ JI Problema (P) sulit diselesaikan secara efisien dengan metode Branch and Bound, apalagi untuk yang berskala besar. Pada bab 2 dijelaskan bahwa Mawengkang and Murtagh (1986) telah menyelesaikan model problema (P) dengan menggunakan kode MINOS (Modular In-core Nonlinear Optimization System). MINOS dapat digunakan untuk menyelesaikan problema PITL khususnya untuk fungsi tujuan tak linier dan kendala linier. Murtagh (1989) menyelesaikan problema (P) dengan memindahkan semua variabel integer dari basic, akan tetapi karena tidak ada pengakhiran JB ∩ JI = ∅ maka iterasinya menjadi tidak terbatas.
3 Program campuran dengan model problema (P) merupakan model yang paling banyak muncul dalam problema kehidupan nyata. Oleh karena itu maka model problema (P) perlu mendapat perhatian khusus dan layak untuk diteliti.
1.2 Perumusan Masalah Problema Program Integer Tak Linier (PITL) termasuk problema non polynomial yang sulit. PITL dengan model problema (P) banyak muncul dalam berbagai bidang aplikasi. Oleh karena itu maka PITL dengan model problema (P) layak untuk mendapat perhatian.
1.3 Tujuan Penelitian Tujuan dari penelitian ini adalah mengembangkan suatu metode untuk menyelesaikan problema (P).
1.4 Kontribusi Penelitian Diperolehnya suatu metode untuk menyelesaikan problema (P) skala besar.
1.5 Metodologi Penelitian Penelitian ini berdasarkan pada ide yang telah dilakukan oleh Murtagh (1998). Pada awal bab 3 dijelaskan penyelesaian problema (P) dengan linierisasi kendala tak linier menggunakan deret Taylor. Order pertama deret Taylor meng-
4 ganti fungsi kendala tak linier menjadi linier, dan order yang lebih tinggi diadjoined pada fungsi tujuan dengan pengali Lagrange. Selanjutnya kendala linier dibagi menjadi basic, superbasic dan nonbasic: xB Ax = B S N xS = b xN dengan pengasumsian ukuran xS tetap kecil jika peubah tak liniernya kecil, namun pada prakteknya hal itu terjadi hanya jika semua peubahnya tak linier. Problema PITL pada penelitian ini diselesaikan dengan asumsi bahwa ada batas penyelesaian layak pada problema. Diharapkan dengan metode pencarian layak akan lebih efisien karena dapat menetapkan apakah proses branch and bound akan dimulai ataupun tidak. Prosedur pencarian layak dengan menggunakan konsep pada peubah superbasis dapat menghasilkan suboptimal penyelesaian layak integer.
BAB 2 BEBERAPA MODEL KELAS PROBLEMA OPTIMISASI
Problema optimisasi dapat dibagi dalam beberapa kelas. Berbagai algoritma untuk menyelesaikannya telah dikembangkan. Pada penelitian ini kelas yang diteliti adalah kelas yang paling sering muncul dalam aplikasi dunia nyata. Selanjutnya, andaikan fungsi tujuan f memetakan n-dimensi ruang Euclidean Rn ke R.
2.1 Optimum Lokal dan Global Titik x ∈ Rn adalah minimum lokal tanpa kendala dimana setiap titik memiliki fungsi tujuan yang sama. Fungsi mulus dapat digambarkan secara geometri dengan vektor gradient nol dan matrik Hessian positif semi-definit. Metode kelas Newton menggunakan turunan pertama dan kedua sehingga titik-titik dapat ditentukan dengan mudah. Pada problema dengan kendala, titik gradient yang tidak nol adalah minimum lokal. Mungkin saja terdapat beberapa minimum lokal sehingga harus ditentukan minimum lokal yang terbaik ? dengan metode minimisasi global-Ratschek and Rokne (1988). Menentukan minimum global lebih sukar daripada minimum lokal, terutama karena lebih sukar membuktikan minimum global yang telah ditetapkan adalah memang benar minimum global yang sesungguhnya.
5
6 2.2 Kemulusan Fungsi Smooth (mulus) adalah fungsi kontinu dengan order turunan yang cukup tinggi. Untuk optimisasi kontinu ditentukan turunan kontinu sampai pada order kedua. Problema minimisasi dengan fungsi tujuan dan kendala demikian dapat menggunakan kalkulus differensial multivariabel. Banyak metode yang menggunakan gradien dan kurva untuk membantu menentukan minimum lokal termasuk metode Newton atau quasi-Newton (Gill et al. (1981)). Pada fungsi tak mulus, hanya nilai fungsi yang dipakai untuk proses pencarian dengan menggunakan teknik pencarian langsung. Metode simpleks dari Nelder and Mead (1965) merupakan pendekatan yang pertama dikenal, namun belakangan banyak digemari para peneliti yang dikembangkan dengan metode pencarian langsung. Penjelasan detailnya ditulis oleh Dennis and Torczon (1990), dan Torczon (1990). Brent (1973) menulis semua topik minimisasi dengan metode pencarian langsung tanpa penggunaan turunan.
2.3 Kendala Optimisasi tanpa kendala pada fungsi f : Rn → R dengan n peubah, secara komputasi merupakan suatu pencarian pada Rn untuk mengoptimalkan vektor x∗ -kendala sederhana yang membatasi ruang pencarian pada himpunan F , dimana F ⊆ Rn . Selanjutnya untuk optimisasi dengan baatsan dapat ditulis: minimum f (x), x ∈ F Untuk problema tanpa kendala, sebarang titik pada domain f di Rn dapat merupakan titik solusi yakni sebagai minimum lokal. F adalah himpunan dari se-
7 mua titik-titik yang mungkin yang disebut sebagai himpunan layak. Titik x ∈ F adalah titik layak atau vektor layak. Problema dengan kendala yang mengandung batasan, dalam bentuk persamaan atau pertidaksamaan harus puas dengan solusi yang diberikan. Kendala dapat menyusutkan atau mengurangi kemampuan ruang pencarian. Pembatasan lainnya yaitu semua atau beberapa peubah harus diasumsikan integer. Sayangnya hal ini juga menyusutkan kemampuan ruang pencarian, namun dapat diatasi dengan menambahkan kendala linier. Jika m kendala linier yang bebas linier mempengaruhi problema n-dimensi tanpa kendala, maka sebaiknya dipindahkan m dimensi bebas, dari ruang pencarian, selanjutnya dikerjakan pada ruang n−m dimensi. Dengan kata lain, jika syarat integer menyulitkan maka ruang pencarian dikurangi hingga membentuk titik diskrit (pada kasus problema integer murni). Pencarian kemudian menjadi kombinatorial sebab kecil kemungkinan untuk dapat diuji satu persatu.
2.4 Konveks Jika fungsi tujuan konveks dengan persamaan kendala linier maka pertidaksamaan kendala concave dengan bentuk ci (x) ≥ 0, dan optimum lokal adalah juga optimum global-Gill et al. (1981) dan Fletcher (1987). Algoritma yang baik seharusnya memanfaatkan sifat konveks problema jika memang sifat tersebut ada pada problema. (Gill et.al. (1981)).
8 2.5 Optimisasi Diskrit Program integer tak linier, yakni problema optimisasi tak linier dengan batasan diskrit belakangan ini banyak mendapat perhatian. Khususnya problema dengan fungsi tujuan minimum, pertidaksamaan kendala tak linier dan sebagian atau semua peubah dari himpunan terbatas tertentu; elemen himpunan ini tidak perlu integer. Fiacco and McCormick (1968) Sequential Unconstrained Minimization Technique (SUMT) dengan pendekatan klasik fungsi penalty diaplikasikan supaya memenuhi syarat kendala tak linier dan sifat diskrit, Shin et al. (1990), Gerdal and Griffin (1990).
2.6 Contoh-contoh Optimisasi Problema optimisasi yang paling sederhana dengan fungsi tujuan linier tanpa kendala dapat menjadi problema optimisasi yang semakin sulit, hingga akhirnya menjadi problema kuadratik PITL.
2.6.1 Fungsi Kuadratik; Kendala dengan Batas Sederhana Walaupun dengan contoh sederhana, banyak hasil yang mungkin terjadi. Fungsi minimum f (x) = A(x − a)(x − b) Kendala dengan batas sederhana L≤x≤U
9 Kasus 1 A > 0; L < a < b < U x∗ = (a + b)/2 adalah minimum (lokal) pada
Gambar 2.1 : Fungsi Kuadratik dengan Kendala-Kasus 1
interval L ≤ x ≤ U . Karena f konveks, maka x∗ adalah juga minimum global pada interval.
Kasus 2 A < 0
Gambar 2.2 : Fungsi Kuadratik dengan Kendala-Kasus 2
10 Minimum lokal tidak bisa diperoleh karena f ?(x) ≡ −2A. Namun minimum global tetap bisa diperoleh, yang muncul pada titik akhir L atau U . Walaupun untuk fungsi kuadratik yang paling sederhana, banyak kasus yang mungkin dan semua algoritma komputer untuk menyelesaikan problema optimisasi dengan banyak peubah harus mencakup kasus dasar ini.
2.6.2 Problema Integer Tak linier Contoh selanjutnya adalah problema yang univariate dengan grafik fungsi y = f (x). Pada program integer kuadratik sederhana (gambar 2.3-2.4), andaikan problema dengan dua peubah bebas, dan bidang kartesius yang memperlihatkan semua titik-titik layak problema. Meskipun penggunaan diagram tidak bisa diterima untuk membuktikan sebuah titik, namun dapat dimanfaatkan untuk memperjelas titik tersebut. Walaupun contoh ini sangat sederhana dan sangat mendasar namun merupakan batu loncatan yang penting untuk metode pencarian langsung pada program integer yang diberikan pada tesis ini. Ada empat titik pada diagram yakni: 1,2,3,4. Titik 1 dan 4 tidak layak karena terletak di luar kendala linier. Dari diagram dapat dilihat bahwa langkah bebas pada tiap dua arah orthogonal tidak layak berdasarkan kendala linier, akan tetapi langkah gabungan terikat dapat menjadikannya layak, bahkan bisa menjadi optimal lokal. Proses pencarian dimulai dengan membuang paksa basis simpleks peubah integer. Setelah itu, semua integer yang tidak layak harus dimasukkan pada peubah superbasis. Diagram ini harus bisa mewakili, dimana ada penambahan
11 pada peubah superbasis saat pengurangan ruang pencarian. Jika langkah bebas gagal seperti pada contoh ini, maka problema bisa menjadi lebih besar. Sifat kombinatorial program integer tidak dapat diabaikan pada contoh ini bisa meningkatkan kesulitan problema. Gambar 2.3 menunjukkan bahwa dengan langkah bebas terkadang tidak cukup untuk memperoleh integer layak. Pada contoh selanjutnya diperlihatkan bahwa langkah gabungan juga masih bisa gagal. Ada empat titik, dengan titik kelima sebagai penyelesaian dari relaksasi kontinu. Langkah bebas x atau y akan melanggar batas kendala, tetapi langkah ?diagonal? akan berhasil.
Gambar 2.3 : Langkah Bebas dan Langkah Gabungan
Contoh Integer Kuadratik Minimum f (x1 , x2) = (x1 − 3.4)2 + (x2 − 1.6)2
12 dengan kendala x1 − x2 ≥ 1 4x1 − x2 ≤ 16 0 ≤ x1 ≤ 5 0 ≤ x2 ≤ 5 x1, x2 integer Pada contoh ini, dapat dilihat bahwa optimum kontinu adalah 0.0 pada x∗0 = (3.4, 1.6) dan integer layak optimum adalah x∗1 = (4, 2)T , dengan tujuan 0.52. Integer optimum dapat diperoleh dengan proses heuristik pada penyelesaian kontinu. Daerah layak diperlihatkan pada gambar 2.4 dengan tanda asterisk sebagai penyelesaian kontinu, dan noktah bulat sebagai titik layak. Selalu ada optimum lokal kedua pada x2 = (3, 1)T dengan nilai tujuan yang sama yaitu 0.52.
Gambar 2.4 : Contoh Integer Kuadratik
13 2.7 Optimisasi Global Untuk kelas skala besar problema praktis, mustahil untuk melakukan minimisasi global, walaupun pada sejumlah kasus dapat dilakukan-Ratschek and Rokne (1988).
Problema optimisasi pada dunia nyata merupakan optimisasi
global yakni gabungan diskrit dan kontinu, tak linier, multivariate dan tidak konveks, dan tentunya ini merupakan problema yang paling sukar untuk diselesaikan secara matematika!. Untungnya telah dilakukan beberapa kemajuan dengan memanfaatkan model yang sederhana dan bentuk problema yang khusus. Terutama pengembangan aritmatik interval dan analisis interval oleh Moore, Mohd, Ratschek, dan Rokne (1986, 1966, 1988). Beberapa pengembangan metode optimisasi mencoba meniru proses alam. Misalnya pendekatan simulasi annealing; atau juga pendekatan evolusi yang dikenal dengan algoritma genetik. Teknik simulasi annealing lebih menjanjikan untuk problema optimisasi global. Pada tahap paling awal, metode mengijinkan kemerosotan lokal fungsi tujuan (dikurangi secara berkala) dengan harapan bahwa lokal akan menghasilkan ruang yang lebih luas lagi. Ulasan simulasi annealing oleh Press et al. (1988), dengan metode kode FORTRAN dan Pascal pada traveling salesman. Simulasi annealing lebih populer dan menjadi bagian dari heuristik untuk problema penugasan kuadratik (Quadratic Assignment Problem-QAP). Definisi QAP merujuk pada Connoly (1990) atau Mawengkang and Murtagh (1986). Khususnya Connoly (1990), Burkhard and Rendl (1984), dan Wilhelm and Ward (1987) melaporkan pengembangan optimal untuk beberapa problema skala besar.
14 Metode-metode lain yang dapat memberi solusi yang lebih efisien pada problema optimisasi, semuanya dikelompokkan pada metode algoritma genetik. Ide dasarnya adalah sifat biologi; dimana kelompok gen diarahkan pada metode tertentu, dengan mutasi pada persilangan penyelesaian yang mungkin (permutasi sebagian). Penyelesaian yang dihasilkan pada tiap generasi diranking berdasarkan ukuran yang sesuai; pada kasus minimisasi, dihitung nilai fungsi tujuan dengan berbagai metode, dan kemudian diambil metode yang menghasilkan nilai tujuan yang lebih baik. Diharapkan melalui proses evolusi simulasi ini secara bertahap akan muncul penyelesaian terbaik. Artikel algoritma genetik antara lain, Morrow (1991) dan Wayner (1991). Metode genetik diaplikasikan oleh Michalewicz et al. (1990) agar dapat optimal mengontrol problema; pada beberapa kasus akan lebih baik dengan menambahkan kode MINOS Murtagh and Saunders (1988).
2.8 Branch and Bound untuk Problema Tak linier Untuk penjelasan dasar pendekatan branch-and-bound, sejumlah teksbook dapat dirujuk; seperti Nemhauser and Wolsey (1988) (penelitian ini paling umum untuk program integer), Murtagh (1981), dan Ravindran et al. (1987). Hampir semua program linier menggunakan metode branch-and-bound untuk menyelesaikan problema program integer linier. Pendekatannya mudah diadaptasikan pada problema tak linier, dan dijelaskan secara rinci pada tesis ini. Problema dasar diselesaikan sebagai program tak linier kontinu, dengan mengabaikan syarat-syarat. Misalkan penyelesaiannya adalah xj , j ∈ J bukan
15 integer layak. Dibentuk: xj = [xj ] + fj ,
0 ≤ fj < 1
dimana [xj ] integer terkecil yang tidak melebihi xj . Pendekatan dilakukan dengan membentuk dua subproblema baru dengan menambahkan batas lj ≤ xj ≤ [xj ] dan [xj ] + 1 ≤ xj ≤ uj untuk peubah j ∈ J . Proses ini disebut pencabangan. Salah satu dari subproblema baru ini disimpan dalam daftar utama yang nanti akan diselesaikan, sementara subproblema yang lainnya adalah sebagai problema kontinu. Hal ini memperlihatkan pendekatan depth-first pada branch-and-bound. Strategi lain dengan menggunakan heuristik untuk memilih subproblema mana yang akan diselesaikan terlebih dulu. Proses pencabangan dan penyelesaian deretan problema kontinu, diulang untuk peubah integer j ∈ J yang berbeda, dan untuk integer [xj ] yang berbeda. Logika metode ini sering disajikan dalam bentuk tree. Tiap node dari tree mewakili satu penyelesaian subproblema. Pencabangan pada node berakhir jika satu dari ketiga kriteria berikut dipenuhi:
Pengakhiran Kriteria untuk Branch-and-Bound
1. Subproblema tidak mempunyai penyelesaian layak
16 2. Penyelesaian dari subproblema tidak lebih baik dari penyelesaian layak integer terbaik yang sebelumnya. 3. Penyelesaiannya adalah integer layak.
Manfaat pendekatan branch-and-bound adalah pasti tersedia batas atas maupun batas bawah pada penyelesaian integer terbaik yang mungkin,. Asumsikan fungsi tujuan minimum, batas atas diperoleh dari penyelesaian integer layak terbaik saat ini, dan batas bawah diberikan dari penyelesaian terbaik integer parsial dari subproblema lainnya. Biasanya proses branch-and-bound berakhir jika beda di antara dua batas ini berada pada toleransi relative yang ditetapkan. Secara umum, prosedur akan dipengaruhi oleh pemilihan peubah j ∈ J yang akan dicabangkan. Dan juga pada pilihan node yang dilakukan secara mundur, satu pencabangan node tertentu adalah diskontinu. Untuk program integer tak linier, asumsikan problema adalah konveks lokal, setidaknya pada neighbourhood penyelesaian kontinu yang mengandung penyelesaian layak integer. Sebaliknya, batas yang dibahas di atas tidaklah cukup. Tidak bisa mengakhiri pencabangan dengan dua kriteria pengakhiran di atas, dan juga tidak bisa mengakhiri prosedur jika beda antara dua batas masih cukup kecil.
2.9 Pendekatan pada Optimisasi Tanpa Kendala Problema umum minimisai tak linier tanpa kendala dapat ditulis sbb: minimum F (x) n x∈R
17 Model yang digunakan yakni fungsi tujuan kuadratik dengan n peubah dan uji sederhana algoritma untuk menyelesaikan problema pada kelas skala besar. Beberapa algoritma untuk optimisasi tanpa kendala harus berbentuk kuadratik, hingga semua fungsi mulus adalah fungsi kuadratik dari optimum lokal mulus pada neighbourhood yang cukup kecil. Dua teorema dasar pengembangan metode minimisasi tanpa kendala adalah teorema Taylor: 1 F (x + p) = F (x) + g(x)T p + pT H(x + θp) 2 dan teorema nilai rata-rata: g(x + p) = g(x) + H(x + θp) pada kedua persamaan di atas berlaku: 0<θ<1
Diasumsikan bahwa F diturunkan dua kali yakni pada vektor gradient g(x) dan pada matriks Hessian H(x), berikut diberikan elemennya: ∂F (x) ∂xj ∂ 2F (x) Hij (x) = ∂xi∂xj Gj (x) =
Digunakan matriks Hessian dengan positif definite untuk memperoleh minimum lokal. Khususnya untuk fungsi kuadratik, matriks Hessian H adalah konstan. Agar fungsi tujuan cukup mulus, syarat perlu pada problema minimum tanpa kendala adalah g(x∗ ) = 0 dan H(x∗ ) ≥ 0. Syarat cukup adalah g(x∗ ) = 0 dan H(x∗ ) > 0.
18 Notasi H(x∗ ) > 0 menyatakan syarat positif definite matriks Hessian pada turunan parsial. Syarat positif definite berikut semuanya adalah equivalent:
19 Positif Definite Hessian
1. xT Hx > 0;
∀x 6= 0.
2. H memiliki spektrum positif (nilai eigen). 3. Langrange LLT (Cholesky) faktor H dengan elemen diagonal L, lii > 0. 4. Semua pengalian eliminasi Gauss tanpa pivoting adalah positif (baris dan kolom dipertukarkan). 5. Semua principal minor H adalah positif.
2.10 Pendekatan pada Optimisasi dengan Kendala-Syarat Kuhn-Tucker Selanjutnya diringkas beberapa materi dari Gill et al.(1981). Kuhn and Tucker (1951), menemukan syarat kendala untuk titik optimal fungsi f tak linier. Syarat Kuhn-Tucker yang begitu terkenal tersebut disajikan untuk bermacam kelas problema optimisasi dengan kendala kontinu. Teknik tradisional dengan menggunakan pengali Langrange secara teori tetap yang terbaik, dan paling banyak digunakan untuk latihan pada metode analitik maupun numerik.
20 2.10.1 Kendala Persamaan Tak linier Diambil problema dengan kendala persamaan tak linier NEP (Nonlinear Equality-constrained Problem): NEP minimum F (x) n x∈R
dengan kendala cˆi (x) = 0,
i = 1, . . . , t.
Jika pada kasus linier semua kendala pasti linier, tentu tidak demikian jika pada kasus tak linier. Secara umum tidak ada arah layak p seperti cˆi (x∗ +α+αp) = 0 untuk semua α yang cukup kecil. Untuk mempertahankan kelayakan maka harus bergerak ke suatu arah. Suatu arah dapat lebih terarah dengan persamaan x = α(θ) diman α(0) = x∗. Selanjutnya p adalah tangent pada arah ini di x∗. Syarat perlu untuk x∗ optimal: Aˆi (x∗)T p = 0, ∀i yang equivalent dengan AˆT p = 0 Aˆ adalah matriks Jacobian dari kendala-kendala, yang diperoleh dari: aij =
∂ci ∂xj
Vektor p yang menjadi orthogonal pada baris Jacobian di x∗ bukanlah syarat cukup untuk p menjadi tangent pada arah layak. Diperlihatkan pada dua kendala berikut: cˆ1 (x) = (x1 − 1)2 + x22 − 1 cˆ2 (x) = (x1 − 1)2 + x22 − 1 Awalnya hanya titik layak, tanpa arah layak. Tetapi beberapa vektor yang berbentuk p = (0, δ)T menjadi syarat cukup untuk sifat orthogonal Jacobian.
21 Kendala yang dipakai harus tegas untuk menjamin sebagai p tangent pada arah layak. Asumsi selanjutnya dapat mengatasi kesulitan karena adanya kendala, dan dapat dibuat dalam beberapa bentuk. Salah satu adalah kendala gradient di ˆ ∗) x∗ yang bebas linier. Hal ini equivalent dengan pernyataan bahwa matriks A(x memiliki tingkat baris yang penuh. Agar x∗ optimal, F harus stasionary sepanjang arah layak: ∇F (α(θ))|θ=0 = 0 dengan AˆT p = 0 Jika Z(x∗) adalah matriks yang kolomnya membentuk basis untuk nullspace ˆ yaitu himpunan dari vektor orthogonal ke baris A, ˆ maka diperoleh: dari A, Z(x∗)T g(x∗) = 0
Syarat ini analog pada syarat kasus kendala linier, kecuali matriks Z sudah tidak konstant lagi. Vektor Z(x∗)T g(x∗) mengakhiri projection gradient dari F di x∗ . Seperti sebelumnya syarat bahwa projected gradient nol di x∗, adalah ˆ ∗). equivalent dengan syarat g(x∗) harus kombinasi linier dari baris A(x ˆ ∗ ) T λ∗ g(x∗ ) = A(x untuk beberapa vektor t dari pengali Lagrange. Fungsi Lagrange dapat ditulis sebagai berikut: L(x, λ) = F (x) − λT cˆ(x)
22 Syarat perlu untuk x∗ optimal yang selanjutnya dituliskan sebagai x∗ adalah titik stationary dari Lagrange dimana λ = λ∗ . Untuk order kedua syarat perlu diperoleh Hessian dari Lagrangian W (x, λ) ≡ G(x) −
t X
ˆi x λi G
i=1
Diperlukan pT W (x∗ , λ∗ )p ≥ 0 yang equivalent pada Z(x∗)T W (x∗, λ∗ )Z(x∗) = 0 Inilah proyek Hessian dari fungsi Lagrange.
NEP-syarat perlu untuk minimum cˆ(x∗ ) = 0 Z(x∗ )T g(x∗ ) = 0 ˆ ∗ ) T λ∗ g(x∗) = A(x Z(x∗ )T W (x∗ , λ∗ )Z(x∗) ≥ 0 Syarat kedua dan ketiga adalah equivalent, dan memperjelas pertidaksamaan pada proyek Hessian dari Lagrange pada persamaan sebelumnya mengarahkan pada syarat cukup untuk kendala minimum: Z(x∗)T W (x∗, λ∗ )Z(x∗) > 0
23 2.10.2 Kendala Pertidaksamaan Tak Linier Dengan problema: NIP (Nonlinear Inequality-constrained Problem) minimum F (x) n x∈R
dengan kendala cˆi (x) ≥ 0, i = 1, . . . , m Kendala aktif harus diidentifikasi. Kendala ini dapat membatasi gangguan di x∗ . Asumsikan kembali qualifikasi kendala yang ada. Syarat-syarat diberikan berikut ini.
NIP-syarat perlu untuk minimum c(x) > 0 dengan cˆ(x∗ ) = 0 Z(x∗ )T g(x∗ ) = 0 ˆ ∗ ) T λ∗ g(x∗) = A(x λ∗i ≥ 0, i = 1, . . . , t Z(x∗ )T W (x∗ , λ∗ )Z(x∗) ≥ 0 Pengali nol Lagrange menjadi syarat cukup untuk NIP. Pertama tentukan himpunan syarat cukup untuk NIP yang mengabaikan problema dengan asumsi semua pengali Lagrange adalah positif:
24 NIP-syarat cukup untuk minimum c(x) > 0 dengan cˆ(x∗ ) = 0 Z(x∗ )T g(x∗ ) = 0 ˆ ∗ ) T λ∗ g(x∗) = A(x λ∗i ≥ 0, i = 1, . . . , t Z(x∗ )T W (x∗ , λ∗ )Z(x∗) ≥ 0 Jika ada pengali nol Lagrange, maka hambatan pada matriks Hessian fungsi Lagrange merupakan syarat cukup untuk menjamin F menunjukkan kurva positif terikat pada arah layak untuk semua kendala dengan pengali positif Lagrange. Untuk kendala dengan pengali nol Lagrange bisa terikat ataupun tidak terikat. Andaikan Aˆ+ (x∗ ) mengandung koefisien kendala aktif dengan pengali positif Lagrange dan andaikan Z+ (x∗) sebagai matriks kolom yang merentang nullspace dari Aˆ+ (x∗). Pada kasus ini, syarat cukup untuk x∗ menjadi minimum lokal kuat untuk NIP sebagai berikut.
NIP-alternatif syarat cukup untuk minimum c(x) > 0 dengan cˆ(x∗ ) = 0 Z(x∗ )T g(x∗ ) = 0 ˆ ∗ ) T λ∗ g(x∗) = A(x λ∗i ≥ 0, i = 1, . . . , t Z+ (x∗ )T W (x∗ , λ∗ )Z+ (x∗ ) ≥ 0
25 2.11 Algoritma yang Tersedia untuk Optimisasi Tak linier Kontinu Secara umum, metode perbandingan lebih buruk dari metode yang menggunakan turunan. Metode perbandingan digunakan hanya jika turunannya sangat sulit untuk dihitung, tidak nyata atau tidak mungkin sama sekali. Untuk problema dengan fungsi tujuan tak mulus, satu-satunya yang bisa dipakai adalah metode fungsi perbandingan Gill et.al. (1981).
2.11.1 Metode 1-Dimensi Beberapa metode standart untuk fungsi minimisasi dengan peubah tunggal dibagi menjadi dua yakni: metode Brent dengan pencarian Fibonacci, pencarian golden section, interpolasi kuadratik, dan metode Newton (1981). Penelitian awal Brent (1973) untuk implementasi modern pada FORTRAN dan Pascal dapat ditemukan di Press et al. (1988). Pada metode Newton dapat digunakan turunan pertama dan kedua, sementara teknik lainnya hanya menggunakan nilai fungsi.
2.11.2 Model Skema Algoritma Descent (Tanpa Kendala) Spesifikasi umum metode descent pada minimisasi kendala linier yang membangun nullspace matriks Z dan garis pencarian subalgoritma. Gambar 2.5 memberikan detailnya.
26
Gambar 2.5 : Skema Descent
Catatan
1. Algoritma ini menjaga sifat layak. 2. pk akan menjadi arah descent, yakni gkT Zpz < 0. 3. Fungsi tujuan harus menjaga sufficient decrease pada tiap iterasi agar jumlah iterasinya wajar. Tidak cukup hanya syarat F (xk+1) < F (xk ). Banyak contoh yang dapat dibuat untuk deret penurunan yang digenerete tetapi sayangnya penggunaan komputasi praktis masih relatif lambat, Gill et al. (1981).
27 Metode dasar Newton menggunakan model kuadratik yang akurat untuk fungsi mulus yang mendekati minimum lokal. Metode ini dapat membuktikan sudah ”cukup dekat” pada minimum lokal. Metode terbaik adalah variasi metode Newton, dan agar efektif matriks Hessian harus positif definite. Ada beberapa alternatif untuk memilih arah descent p. Yang paling terkenal antara lain steepest descent, metode Newton, kelas metode quasi-Newton, dan metode gradient conjugate. Selajutnya dibahas berikut ini.
Steepest Descent Steepest descent adalah metode lama untuk minimisasi. Pada tiap iterasi xk , mengikuti vektor gradient negatif yang menjamin arah descent kecuali jika telah berada pada titik stasionary. Metode ini banyak dibahas pada text book minimisasi multivariate.
Metode Gradient Conjugate (Metode Turunan Pertama) Ide umum basis orthogonal pada ruang vektor digunakan untuk membangun deretan pencarian non-interfering arah pk . Metode ini awalnya untuk menyelesaikan persamaan linier oleh Hestenes and Stiefel (1952), dan memiliki sifat bahwa fungsi kuadratik dari n peubah yang minimum bisa dimaksimumkan dengan n langkah, salah satu pada setiap arah konjugate,dan yang lainnya tanpa memperhitungkan arah. Pengembangan problema tak linier dikerjakan oleh Fletcher and Reeves (1964). Metode gradient conjugate biasanya digunakan untuk problema skala besar, tidak mungkin berdasarkan faktorisasi matriks sebab matriksnya ter-
28 lalu besar. Pendekatan ini digunakan pada MINOS oleh Murtagh and Saunders (1987).
Metode Newton (Metode Turunan Kedua) Metode Newton didasarkan pada model kuadratik sederhana dengan fungsi mulus yang mirip seperti kuadratik dengan positif definite Hessian pada neighbourhood minimum. Fungsi kuadratik sederhana: 1 F (x + p) = F (x) + g(x)T p + pT G(x)p 2 digunakan pada model fungsi mulus yang berubah-ubah. Mudah untuk memperlihatkan bahwa kuadratik adalah minimum jika p memenuhi Gk pk = −gk dimana gk adalah vektor gradient pada iterasi xk tertentu dan Gk adalah matriks Hessian. Positif definite Hessian menjamin penyelesaian unik pk , yang mengakhiri arah Newton. Jika bentuk kuadratik definit positif (konstan) Hessian G > 0, maka tepat hanya satu iterasi yang diperlukan arah Newton untuk mendapat minimum. Jika G bukan positif definite maka ada berbagai strategi untuk memodifikasi penghitungan Hessian untuk mencari arah decrease F . Suatu modifikasi teknik Newton didasarkan pada faktorisasi matriks untuk memeriksa positif definite Hessian.
29 Dasar dari metode Newton adalah konvergence lokal yang sangat kuat. Hal ini menunjukkan adanya positif definite, sehingga jelas terlihat dari sifat fungsi kuadratiknya dan dari pernyataan Taylor untuk f yang mendekati minimum. Itulah yang dinamakan metode turunan kedua, dimana syarat cukup untuk optimal dapat diperiksa. Model kuadratik pada fungsi minimum bisa tidak akurat sehingga harus lebih hati-hati dalam penggunaannya agar tidak gagal. Variasi dasar Newton selanjutnya menggunakan perbedaan terbatas vektor gradient untuk mencapai pendekatan Hessian. Suatu metode yang mengakhiri perbedaan terbatas metode Newton. Syarat penggunaan metode-metode tersebut jelas merupakan tipe metode Newton yang menggunakan turunan kedua Hessian.
Metode Quasi-Newton (Metode Turunan Kedua) Metode ini didasarkan pada ide membentuk kurva sebagai proses iterasi metode descent, menggunakan nilai fungsi dan vektor gradient. Metode Newton menggunakan Hessian dan menghasilkan kurva pada titik tunggal. Metode quasiNewton didasarkan pada kenyataan bahwa pendekatan pada kurva fungsi tak linier dapat dihitung tanpa membentuk matriks Hessian. Davidon Fletcher Powell (DFP) dan Broyden Fletcher Goldfarb Shanno (BFGS) meningkatkan deret pendekatan matriks Hessian, Gill et al. (1981). Murtagh menggunakan BFGS.
30 Metode Aktif Set Untuk Problema Kendala Linier Pendekatan yang digunakan oleh Murtagh and Sanders pada MINOS (1978) menggunakan peubah superbasis. Pada setiap langkah pada minimisasi, jumlah peubah superbasis ns merupakan ukuran dimensionalitas dari subspace yang dibentuk oleh interseksi kendala aktif. Peubah superbasis tergantung pada derajat bebas pencarian, yakni peubah bebas basis tertentu dan batas yang ditetapkan. Peubah superbasis dapat bebas berubah-ubah diantara batasnya namun tetap menjaga sifat kelayakan himpunan peubah basis saat itu. Pencarian mempunyai dua komponen yang saling berhubungan: problema untuk menemukan himpunan kendala aktif yang tepat, dan problema minimisasi himpunan aktif.
2.12 Algoritma yang Tersedia untuk Optimisasi Tak linier Diskrit Program Integer Tak Linier (PITL) pada hakekatnya adalah problema yang sukar. Scarf (1990) mengatakan bahwa integer programming merupakan problema komplit-Non Polynomial. PITL jauh lebih sulit dari Program Integer Linier. Pada bagian berikut, dipaparkan beberapa algoritma untuk problema PITL.
2.12.1 Algoritma Pendekatan Luar Duran and Grossmann Duran and Grossmann (1986) mengajukan algoritma pendekatan outer untuk menyelesaikan PITL campuran. Problema dibagi menjadi dua yakni master problema yang dibentuk dengan linierisasi, dan subproblema program tak linier.
31 Master problema merupakan outer dan subproblema adalah inner. Subproblema diselesaikan dengan peubah integer tetap kemudian dimasukkan ke master problema, demikian dilakukan berulang-ulang. Pendekatan yang dilakukan adalah dengan cara linierisasi. Metode Duran and Grossmann menggunakan aturan dekomposisi pada model problema, dengan asumsi linier pada peubah integer dan konveks pada bagian tak linier fungsi tujuan dan fungsi kendala. Dengan bentuk umum: minimum cT y + f (x) dengan kendala g(x) + By ≤ 0 x ∈ X ⊆ Rn y ∈ U ⊆ Rm + Fungsi tak linier f : Rn → R dan fungsi vektor g : Rn → Rp harus konveks dan dapat diturunkan. Secara konvensional, domain U peubah integer diasumsikan sebagai himpunan diskrit yang terbatas; biasanya unit hypercube Y = {0, 1}m . Ide utama metode Duran and Grossmann (1986) adalah linieritas peubah diskrit memungkinkan ruang pencarian layak problema yang terpisah antara yang kontinu dengan yang diskrit. Ruang kontinu adalah kumpulan hingga daerah konveks yang semuanya terparameter oleh nilai peubah diskrit. Pendekatan outer himpunan konveks dengan pembagian ruang yang digunakan untuk master LP integer-campuran. Dibandingkan dengan metode dekomposisi relaksasi, metode pendekatan outer menghasilkan batas bawah yang lebih baik pada nilai fungsi tujuan optimal.
32 Hasil uji awal Duran and Grossmann menunjukkan keunggulan metode dengan menyelesaikan subproblema NLP. Leyffer (1991) bekerja dengan ide yang sama.
2.12.2 Metode Mawengkang and Murtagh Penelitian Mawengkang and Murtagh (1986) dan Murtagh (1989) menimbulkan kelas pada PITL. Pada artikel tahun 1986, dijelaskan penggunaan kode MINOS untuk problema program integer tak linier skala besar (tujuan dan kendala tak linier). Prosesnya didasarkan pada peningkatan pencarian kendala dengan menggunakan pendekatan MINOS, dengan aplikasi pada problema penugasan kuadratik (QAP) dan problema desain jaringan pipa gas. QAP dengan order yang lebih tinggi dari 10 atau 15 sukar diselesaikan dengan pendekatan branch-andbound, sehingga digunakan pendekatan pencarian langsung yaitu subset peubah integer diperlakukan sama dengan peubah superbasis pada algoritma MINOS. Untuk mempertahankan kelayakan maka peubah integer yang boleh berubah selama pencarian hanya yang diskrit, sama seperti peubah superbasis pada MINOS yang boleh menambah derajat yang bebas untuk problema tak linier.
2.12.3 Pendekatan-Pendekatan Lain Teknik linierisasi telah umum dikenal. Beberapa program integer dapat dibentuk menjadi problema 0-1 (Nemhauser and Wolsey (1988)). Jika fungsi tujuan dan kendala polynomial, maka problema dapat dibentuk menjadi problema integer linier (Garfinkel and Nemhauser (1972)). Beberapa teknik menambah
33 peubah 0-1 yang baru dan kendala yang baru yang tentu akan menambah waktu komputasi. Balas and Mazzola (1984) dengan pendekatan linierisasi mengganti fungsi tak linier peubah 0-1 dengan pertidaksamaan linier. Teknik ini menggunakan linierisasi tanpa menambah peubah. Hansen (1979) dengan metode PITL 0-1 mengatakan bahwa hanya sebagian kecil algoritma yang benar-benar telah diuji dan diimplementasikan; dengan algoritma network flow yang dapat digunakan pada kelas tertentu program kuadratik 0-1; dan formula Boolean PITL 0-1 dapat digunakan sebagai teknik pembuktian pada algoritma ini. Tesis Myers (1984) membandingkan strategi branch-and-bound pada relaksasi Lagrange dengan strategi optimisasi subgradient untuk kendala linier integer campuran PITL. Myers menyarankan strategi pencabangan. Dua metode terkenal untuk problema PITL adalah metode dekomposisi Benders dan program dinamik Bellman. Gupta and Ravindran (1983) dan Cooper (1981) menyebutkan bahwa beberapa pendekatan telah dipaparkan pada literature dan review sebelum tahun 1981.
BAB 3 HEURISTIK PENCARIAN LANGSUNG
Bab ini mengupas secara detail algoritma pencarian langsung PITL dengan analisa dan pengembangan metode. Diharapkan modifikasi pendekatan ini akan lebih fleksibel dan lebih cepat mendapatkan penyelesaian layak integer yang dapat digunakan untuk memulai ataupun tidak, proses branch-and-bound.
3.1 Model Problema Bentuk umum problema PITL yang diselesaikan dengan metode yang ditawarkan dalam tesis ini dapat dilihat pada model di bawah. Asumsikan bahwa ada batas penyelesaian layak pada problema ini. Formulasi Murtagh (1981), hanya berbeda sedikit dengan Murtagh (1998). minimum f 0 (xN ) + cT xL n x∈R
dengan kendala f (xN ) + A1 xL = b1
(m1 baris )
A2 x N + A3 x L = b 2
(m2 baris )
(P)
l ≤ x ≤ u (m = m1 + m2) xj integer , j ∈ JI Beberapa bagian dari peubah x asumsikan tak linier pada fungsi tujuan dan atau kendala, dan beberapa bagian dari peubah harus bernilai integer. Anggap peubah tak linier jika terdapat sifat tak linier pada rumusan problema baik pada fungsi tujuan maupun kendala. 34
35 Model yang sama, tanpa syarat integer merupakan awal dari kode MINOS skala besar program tak linier (Murtagh and Saunders (1982, 1987)). Pada iterasi yang besar, dilakukan linierisasi dengan memakai suku linier dari deret Taylor, dimana order pertama deret Taylor mengganti fungsi kendala tak linier menjadi linier, dan order yang lebih tinggi diadjoined pada fungsi tujuan dengan estimasi pengali Lagrange. Himpunan kendala linier (tidak termasuk batasnya) dapat ditulis: xB Ax = B S N xS = b xN B adalah m × m dan non-singular, xN adalah peubah non-basis pada batasnya. xB dan xS adalah peubah basis dan superbasis. Agar tetap layak, maka setiap langkah berikutnya harus memenuhi: B∆xB + S∆xS = 0 atau untuk basis yang non-singular dapat ditulis: ∆xB = −B −1 S∆xS
(3.1)
Untuk meningkatkan fungsi tujuan harus ditentukan non basis mana yang naik atau turun menuju batas lainnya, dimana superbasis dapat bebas dirubah. Himpunan layak bisa dirubah karena superbasis harus ada diantara batas-batas tetapi tidak menjadi batas. Karena persamaan (3.1), maka superbasis menggerakkan langkah ∆xS yang menentukan seluruh langkah δx. Kunci sukses algoritma MINOS (Murtagh and
36 Saunders (1978)) adalah pengasumsian ukuran xS tetap kecil. Hal ini dapat dijamin berdasarkan penghitungan Murtagh (1989), jika peubah tak liniernya kecil, namun pada prakteknya hal itu terjadi jika semua peubah tak linier. Asumsi yang sama akan dibuat pada model program integer tak linier. Diasumsikan bahwa bagian dari peubah integer adalah kecil. Pendekatan Murtagh menghasilkan penyelesaian (suboptimal) layak integer melalui prosedur pencarian langsung dengan menggunakan konsep peubah superbasis. Aplikasinya pada artikel CTAC89 (Murtagh (1989) termasuk proses dan teknik pembuatan optimal power flow (1200 kendala, 1500 peubah-semua tak linier), yang merupakan pengembangan ide Mawengkang and Murtagh (1986), pada aplikasi problema penugasan kuadratik. Keempat himpunan yang pertama pada tabel 3.1 membagi seluruh himpunan indeks {1, 2, . . . , n}, yakni JB ∪ JS ∪ JL ∪ JU = {1, 2, . . . , n} dan Jα ∩ Jβ = ∅, α 6= β. Himpunan JI sebagai peubah integer diasumsikan kecil, dan m + nS + nL + nU = n. Pendekatan mengasumsikan bahwa problema kontinu diselesaikan, dan dicari penyelesaian layak integer pada neighbourhood terdekat dari penyelesaian kontinu. Membiarkan peubah integer non basis pada batasnya masing-masing (dan juga nilai integer) dan mengarahkan pencarian pada ruang terbatas basis, superbasis, dan peubah kontinu nonbasis, j ∈ JI . Metode Murtagh dapat diringkas sebagai berikut:
1. Mencari penyelesaian relaksasi kontinu dengan menggunakan kode MINOS.
37 2. CYCLE1: keluarkan peubah integer dari basis dengan memindahkan nonbasis yang tepat dari batasnya. Tujuannya agar peubah basis tak layak integer menjadi layak integer, kemudian dipivotkan ke dalam superbasis; nonbasis selanjutnya menjadi basis. Diperlukan beberapa notasi dengan syarat indeks pada tabel 3.1.
Tabel 3.1 : Himpunan indeks untuk pembagian simplek yang diperluas Nama JB JS JL JU JI
Arti Himpunan peubah basis Himpunan peubah supebasis Himpunan peubah nonbasis pada batas bawah Himpunan peubah nonbasis pada batas atas Himpunan peubah integer
Kardinalitas |JB | = m |JS | = nS |JL | = nL |JU | = nU |JI | = nI
3. CYCLE2, pass1: sesuaikan superbasis tak layak integer menjadi layak integer. 4. CYCLE2, pass2: sesuaikan superbasis layak integer. Tujuan dari tahap ini untuk memeriksa optimal lokal dengan mengarahkan pencarian pada lokasi neighbourhood yang luas-Scarf (1986).
CYCLE1, CYCLE2 Pass1, CYCLE2 Pass2, dan algoritma Murtagh dapat dilihat pada contoh berikut. Metode ini menggunakan prosedur branch-and-bound pada pencabangan subproblema yang berakhir jika salah satu dari ketiga kriteria ini dipenuhi:
1. Subproblema tidak memiliki penyelesaian layak
38 2. Penyelesaian dari subproblema tidak lebih baik dari penyelesaian layak integer sebelumnya. 3. Penyelesaian sudah layak integer (berdasarkan tingkat toleransi)
Karena prosedur Murtagh memperoleh penyelesaian optimal lokal pada neigbourhood penyelesaian kontinu, maka ada baiknya untuk mencoba dulu prosedur branch-and-bound untuk melihat semua penyelesaian integer yang mungkin. Penyelesaian yang diperoleh dengan prosedur diatas memberikan batas yang jelas dan membatasi proses pencabangan dengan cepat pada kriteria 2.
3.2 CYCLE1-Mengeluarkan Peubah Integer dari Basis Pada problema CYCLE1 diberikan beberapa asumsi agar dapat berjalan sesuai dengan yang diharapkan. Anggap penyelesaian kontinu peubah integer adalah basis pada nilai non-integer xi0 = xi0 + fi0 ,
0 < fi0 < 1
Selanjutnya, anggap pilihan non-basis peubah non-integer xi0 dilepaskan dari batas bawahnya. Peubah integer yang diasumsikan kecil, menjadi kunci penjamin operasi penggantian dapat dilakukan; untungnya beberapa problema praktis mengandung karakter ini. Dan tentu juga asumsi terdapat peubah slack. Penelitian Mawengkang and Murtagh (1986) memberikan pilihan yang lebih
39 baik untuk i0 sebagai berikut: min(fi0 , 1 − fi0 ) ≤ min(fi0 , 1 − fi ) i ∈ JI
40 Pilihan i0 ini agar perubahan yang terjadi pada fungsi tujuan seminimal mungkin, dan karena basis integer layak yang terkecil. Pendekatan ini dapat dilakukan hanya apabila komponen dari penurunan vektor gradient, sebanding secara keseluruhan. Pada langkah CYCLE1, pemilihan nonbasis (kontinu) j ∗ , Murtagh juga menawarkan kriteria yang lebih baik untuk nilai j: min ∈ (JL ∪ JU ) − JI |αi0 j j
λj 6= 0 α i0 j
dimana λj merupakan komponen ke-j dari pemisahan nonbasis dari vektor reduce gradient atau vektor reduce cost λN , αi0 j = (B −1 aj )i0 dan aj adalah kolom A pada nonbasis xj . Kenyataannya, tidak mudah memperoleh penyelesaian basis integer dengan sifat layak integer terkecil. Pada saat nonbasis j ∗ berpindah sebaiknya tidak memilih nonbasis yang bisa memaksa basis terpilih bergerak ke arah yang salah. Artinya heuristik sebaiknya diperbaiki untuk memilih j ∗ . Kenyataannya λ = gN − N T π dan π = (B T )−1 gB -Murtagh and Saunders (1978). Kriteria ini dapat mengukur keburukan nilai fungsi tujuan per unit perubahan pada peubah basis xi0 . Syarat αi0 j dihitung dengan lebih dulu membentuk vektor zT = ei0 B −1 (baris i0 dari B −1 ), kemudian menghitung hasil kali dalam αi0 j = zT aj . Jika j ∗ telah
41 dipilih maka vektor αJ ∗ = B −1aj ∗ dihitung untuk uji ratio pada persamaan (3.2)(3.4). Sebagai nonbasis terpilih xj ∗ bergerak menuju batas lain, empat kejadian yang mungkin muncul adalah: Kejadian 1. Peubah basis xi1 , i1 6= i0 mengenai batas bawah pertamanya Kejadian 2. Peubah basis xi2 , i2 6= i0 mengenai batas atas pertamanya Kejadian 3. Peubah basis integer xi3 , i3 ∈ JB ∩ JI menjadi layak integer. Kejadian 4. Non basis xj ∗ mengenai batas pertama yang lainnya.
Catatan
1. Kemungkinan i1 = i0 bukan merupakan kejadian 1 dan i2 = i0 bukan merupakan kejadian 2., Jika xi0 mengenai suatu batas maka hal itu merupakan kejadian 3, dimana kemungkinan i3 = i0 yang akan muncul. Hasil yang diharapkan tentunya kejadian 3. 2. Untuk layak integer perlu peubah integer pada batas.
Keempat kejadian yang mungkin tersebut saling berhubungan, nilainya dihitung: xi − li θ1 = min ∈ JB − {i }|αij ∗ > 0 i αij ∗ ui − xi 0 θ2 = min ∈ JB − {i }|αij ∗ < 0 i −αij ∗ 1 − fi fi θ3 = min min , min i∈JI ∩JB |αij∗ <0 −αij ∗ i∈JI ∩JB |αij∗ >0 αij ∗ 0
θ4 = uj ∗ − lj ∗
(3.2) (3.3) (3.4)
42 dimana αij = (B −1 aj )i dan aj adalah kolom A pada nonbasis xj . Sehingga diperoleh θ∗ = min(θ − 1, θ2 , θ3, θ4 ) Jika θ∗ = θ1 maka peubah basis xi1 menjadi nonbasis pada li1 dan xj ∗ menggantikannya di B. xi0 tetap sebagai basis dengan nilai yang baru (non-integer). Jika θ∗ = θ2 maka xi2 menjadi nonbasis pada ui2 dan xj ∗ menggantikannya di B seperti diatas. Jika θ∗ = θ3 maka xi3 dibuat sebagai superbasis pada nilai integer dan xj ∗ menggantikannya di B. Jika θ∗ = θ4 maka xj ∗ tetap sebagai nonbasis, tetapi pada batas atasnya, dan tetap sebagai basis dengan nilai yang baru (non-integer). Ratio yang sama dapat dihitung untuk kasus xj ∗ yang dilepaskan dari batas atasnya.
Biasanya dapat diperoleh semua kemungkinannya (lepas dari batas
bawah dan atas), dan dengan menemukan indikator arah untuk CYCLE1, 1, duplikasi kode dapat dihindari sebagai berikut. Jika xj ∗ terlepas dari batas bawahnya (j ∈ JL ) maka σ1 = 1. Jika xj ∗ terlepas dari batas atasnya (j ∈ JU ) maka σ1 = −1. Maka σ1 = signum (∆xj ∗ ), dimana ∆xj ∗ merupakan langkah pada nonbasis xj ∗ , j ∗ ∈ (JL ∪ JU ) − J1 . Kedua kasus tersebut dirangkum pada tabel berikut ini:
43
Tabel 3.2 : Memindahkan peubah integer dari basis-memilih nonbasis non-integer xj , j ∗ ∈ (JL ∪ JU ) − JI ) dilepaskan dari batasnya.
44 Catatan untuk CYCLE1 1. αij = (B −1 aj )i dan aj adalah kolom A pada nonbasis (xN )j . 2. Langkah nonbasis maksimum θ∗ = min(θ1, θ2 , θ3, θ4). Pada CYCLE1, θs bisa tidak ada, karena indeks seperti α∗ij > 0 mungkin saja kosong. Basis setidaknya mempunyai satu peubah integer karena θ4 dan θ3 selalu ada. Artinya basis akan selalu terdiri dari setidaknya satu peubah integer pada CYCLE1 karena syarat utama untuk mengakhiri CYCLE1 adalah tidak ada peubah integer yang tersisa pada basis. Jaminan kedua adalah limit iterasi. 3. Pada saat pengkodean algoritma CYCLE1, jika dua atau lebih kejadian muncul secara simultan, usahakan untuk memilih kejadian 3. Tujuan utama CYCLE1 adalah untuk memaksa sebanyak mungkin peubah integer tak layak menjadi non-basis atau superbasis.Tentunya kejadian 3 adalah kejadian yang paling diharapkan pada tiap iterasi CYCLE1. 4. Jika kejadian 3 tidak muncul untuk pilihan i0 dan j ∗ , maka dapat dieksplore penggunaan multiple pricing untuk memilih alternatif j ∗ s agar kejadian 3 muncul. Inilah yang menjadi elaborasi metode.
3.3 CYCLE2 Pass1-Sesuaikan Superbasis Tak Layak Integer Langkah 1 Pilih superbasis tak layak integer yang terkecil, yaitu j 0 ∈ JS sebagai nilai j, dimana akan muncul: ζ0 = min min(fj , 1 − fj ) j∈JS
45 JS adalah himpunan indeks untuk superbasis. Jika 1 − fj 0 ≤ fj maka dilakukan langkah maju, dan langkah mundur jika selain itu.
Dikerjakan dengan cara
berikut. Tentukan j1 sebagai indeks dari peubah superbasis dengan komponen pembagian terkecil yakni: fj1 = min fj j∈JS
Sama halnya dengan j2 sebagai indeks dari peubah superbasis dengan komponen pembagian terbesar, yakni: fj2 = max fj j∈JS
Tentunya nilai j1 dan j2 mungkin saja tidak unik namun tetap dicoba untuk menyelesaikan ulang perubahan-perubahan yang tidak terkendali. Mungkin kemudian hari metode ini akan diperbaiki-seperti misalnya untuk mengatasi sifat ambiguity dengan memilih satu dari peubah superbasis yang berhubungan yaitu reduce cost terkecil. Minimum integer-infeasibility dinyatakan dengan ζ0 = min(fj1 , 1 − fj1 ) Dan muncul pada j = j1 jika fj1 < 1 − fj1 selebihnya akan muncul pada j = j2 jika fj1 > 1 − fj1 . Usaha mencapai integer layak pada xj 0 bisa jadi mustahil karena batas sederhana pada basis bisa dilanggar. Hal ini diringkas pada persamaan (3.5) dan (3.6). Langkah mundur terbatas, ∆xj 0 < 0 diberikan oleh: ∆xj 0 = − min fj 0 ,
min i∈JB |αij0 <0
(xB ) − 1i −αij 0
,
min i∈JB |αij0 >0
ui − (xB )i αij 0
(3.5)
46 Langkah maju terbatas ∆xj 0 > 0 diberikan oleh: (xB ) − 1i ui − (xB )i ∆xj 0 = min 1 − fj 0 , min , min i∈JB |αij0 >0 i∈JB |αij0 <0 αij 0 −αij 0
(3.6)
Demi untuk menghindari duplikasi kode, penggunaan persamaan (3.5) dan (3.6) akan dipaparkan lebih jelas berikut ini. Tentukan arah indikator untuk CYCLE2, σ2: −1; fj < 1 − fj 1 2 σ2 = +1; fj1 > 1 − fj2
σ2 hanya merupakan symbol dari langkah yang diharapkan yaitu ∆xj 0 , sementara batasan dari langkah ditentukan oleh batas sederhana yang diberikan oleh: ζ1 =
min i∈JB |σ2α
ij 0
ζu =
>0
min i∈JB |σ2α
ij 0
<0
xi − 1i σ2αij 0
ui − 1i −σ2αij 0
(3.7)
(3.8)
Langkah 2. Perlu diperhatikan apakah dapat dibuat langkah pembagian (maju atau mundur) untuk membuat integral xj 0 . Semua basis harus dipastikan tetap layak. Pada bagian ini, basis jangan ditukar, artinya tidak ada pivot, karena superbasis integer dipisah bagian yang menjadi integer tak layak. Nilai baru basis tentunya harus diikuti, karena tak bebas linier pada superbasis dan nonbasis. Jika memungkinkan ambil langkah penuh maju atau mundur untuk superbasis j 0 yaitu |∆x| = ζ pada integer terdekat. Namun jika tidak, ambil langkah sejauh mungkin tanpa melanggar batas sederhana basis.
47 Selanjutnya ditentukan il sebagai nilai i yang minimum pada (3.7); iu sebagai nilai i yang minimum pada (3.8); dengan syarat masing-masing himpunan indeks tidak kosong (pada beberapa kasus, iu , il mungkin tidak ada). Langkah 2 CYCLE2 dapat ditulis sebagai berikut: ∆xj 0 = σ2 min(ζ0 , ζ1, ζu )
Apakah mungkin langkah ∆xj 0 menjadi nol? Jawabannya tidak, karena hal ini berarti basis telah berada pada batas, yakni himpunan batasan-batasan telah memburuk. Keadaan ini dapat diabaikan dengan asumsi non-degeneracy. Untuk memperoleh σ2 harus sangat hati-hati. Sebagai contoh, jika integer tak layak = 0.5 langkah mana yang akan diambil? Pada contoh 3 bagian 3.5.3 jika dipilih arah yang salah (σ2 = +1) maka integer tak layak akan = 0.
3.4 CYCLE 2 Pass 2-Sesuaikan Superbasis Layak Integer Superbasis dapat dirubah untuk menjaga agar peubah basis layak. Pencarian pada neighbouhood membuktikan optimal (lokal) dari penyelesaian integer layak yang diperoleh, Scarf (1986).
Langkah 1 Berdasarkan satu-dimensi steepest descent. Pilih j 0 ∈ JI . Kriteria pemilihan j 0 akan memaksimumkan reduced cost λj . Langkah 2 Hitung αj 0 . Tentukan arah perpindahan-periksa tanda λj 0 .
48 Langkah 3 Periksa apakah memungkinkan untuk bergerak ke satu unit. ui − xi ≥ 1∀i |i ∈ JB |αij 0 > 0 +αij 0 xi − l i ≥ 1∀i |i ∈ JB |αij 0 < 0 −αij 0 Langkah 4 Bergerak dengan 1 unit; pastikan ada kemajuan pada fungsi tujuan, yakni pencarian pada neighbourhood yang ditemukan oleh Scarf (1986).
3.5 Analisa dan Contoh Penyangkal untuk Algoritma Murtagh Data Problema Syarat untuk memulai CYCLE1:
1. Problema terdiri dari fungsi tujuan, koefisien untuk batasan linier, batas bawah dan batas atas, dan peubah-peubah integer. 2. Perbedaan antara nonbasis pada batas bawah dengan nonbasis pada batas atas, dijelaskan oleh indeks vector hb, dan status vektor hs Murtagh sebagai berikut: Tentukan hbj sebagai indeks natural peubah ke-j, dimana 1 < j < m + nS . Perhatikan peubah natural ke-j. Selanjutnya diperoleh status indicator
49 hsj berikut:
hsj =
0; jikanonbasispadabatasbawah 1; jikanonbasispadabatasatas 2; jikasuperbasis 3; jikabasis
Range indeks untuk peubah basis adalah 1 j perbasis adalah m + 1 j
m, dan untuk peubah su-
m + nS .
Pembagiannya dapat diilustrasikan sebagai berikut:
B 1≤j ≤m
S
NL
NU
m + 1 ≤ j ≤ m + ns
Catatan: karena nonbasis tidak langsung terindeks, berada pada suatu batas, maka nilainya dapat diketahui secara mutlak. 3. Nilai sekarang dari peubah superbasis 4. Beberapa toleransi Sekarang CYCLE1 mempunyai cukup syarat untuk diproses. Program kuadratik batasan linier integer campuran pada (3.9)-(3.13). Bentuk Umum Contoh Penyangkal 3 X
γi (xi − τi )2
(3.9)
dengan kendala 1x1 + 0x2 + ω1 x3 ≤ b1
(3.10)
0x1 + 1x2 + ω2 x3 ≤ b2
(3.11)
1≤x≤u
(3.12)
x2 integer
(3.13)
Minimum f =
i=1
50 Parameter γi , τi , ω)1, ω2 , b1 , b2 dan batas sederhana l, u cukup untuk mengilustrasikan problema dengan CYCLE1 algoritma Murtagh (1989). Diberikan slacks x4 , x5 pada bentuk umum , dan γi = 1.0 dan τ1 = 1.2, τ2 = 2.5, τ3 = 0.0, diperoleh:
Bentuk Umum Contoh Penyangkal dengan Slacks minimum f =
3 X
γi (xi − τi )2
i=1
dengan kendala 1x1 + 0x2 + ω1 x3 ≤ b1 0x1 + 1x2 + ω2 x3 + 0x4 + 1x5 ≤ b2 1≤x≤u x2 integer
Relaksasi dan Optima Layak Integer Untuk fungsi tujuan di atas, kontinu tanpa batasan optimum adalah x = τ = (1.2, 2.5, 0, 0, 0)T . Titik x = (1.2, 2, 0, 0, 0.5)T memenuhi syarat batasan umum (linier), batas sederhana, dan juga integer layak. Pada fungsi kuadratik sederhana, tentu juga sebagai optimum lokal.
Persamaan Umum Jika xB adalah vektor peubah basis dan αj = (B −1 N )j , maka dapat ditulis: xB = β −
X j∈JL
αj 1j −
X j∈JU
α j uj −
X j∈JS
α j xj
51 Jika i ∈ JB maka dapat ditulis: xi = βi −
X
αij 1j −
j∈JL
X
αij uj −
j∈JU
X
αij xj
j∈JS
Bentuk Umum Contoh Penyangkal Untuk menguji metode Murtagh (1989), diperlihatkan sejumlah contoh sederhana berdasarkan kelas problema sebelumnya. Untuk dua contoh pertama, andaikan bahwa optimum kontinu untuk problema ini memiliki basis x1, x2, nonbasis x3, dan superbasis x4 , x5. Persamaan pada titik ini: x1 = b1 − ω1 x3 − x4 x2 = b2 − ω2 x3 − x5
3.5.1 Contoh 1 Mungkin saja interval [l3, u3] sangat kecil hingga x3 melanggar batas atas sebelum kejadian 1, 2 atau 3 dari CYCLE1 muncul. Hal ini dimungkinkan dengan membuat u3 − l3 sekecil mungkin. Karena x3 merupakan satu-satunya nonbasis maka CYCLE1 tidak akan berakhir (x3 akan berkisar diantara batasnya). Diilustrasikan pada contoh 1. Definisi Contoh 1 minimum
f = (x1 − 1.2)2 + (x2 − 2.5)2 + x23 dengan kendala 1.0x1 + 0.0x2 − 1.0x3 + 1.0x4 + 0.0x5 = 1.2
52 0.0x1 + 1.0x2 − 0.1x3 + 0.0x4 + 1.0x5 = 2.5 (0, 0, 0, 0, 0)T ≤ x ≤ ((5, 5, 1, 100, 100))T x2 integer yakni JI = {2} Penyelesaian kontinu vektor dan partisi: x∗ = (1.2, 2.5, 0.0, 0.0, 0.0)T JB = {1, 2} JS = {4, 5} JL = {3} JU = ∅
Hasil untuk contoh 1 Dengan persamaan: x1 = 1.2 + 1.0x3 − 1.0x4 x2 = 2.50.1x3 − 1.0x5 Nilai x3 meningkat dari 0.0 ke batas atas 1.0, dan semua basis layak integer kecuali peubah x2 yang tidak layak integer. Kejadian 4 muncul yakni x3 → u3. Sebagai satu-satunya nonbasis, iterasi selanjutnya CYCLE1 akan mengusahakan x3 kembali pada batas bawah. Jelas bahwa deretan ini akan berulang terus menerus sampai tak hingga.
3.5.2 Contoh 2 Kesulitan lain yang mungkin terjadi adalah peubah basis bisa berputar di dalam dan di luar basis. Untuk melihat hal ini, anggap x1 melanggar batas atas x3 yang meningkat dari l3. Maka harus dipilih ω1 < 0. Pilih ω2 yang cukup kecil
53 sehingga x2 bisa menjadi integer layak ataupun melampaui batas.
54 Dengan memberi nilai pada parameter dapat mengilustrasikan hal tersebut, seperti pada contoh 2, yang mirip dengan contoh 1, kecuali batas atas pada x3 yang diperluas:
Definisi contoh 2 minimum
f = (x1 − 1.2)2 + (x2 − 2.5)2 + x23
dengan kendala
1.0x1 + 0.0x2 − 1.0x3 + 1.0x4 + 0.0x5 = 1.2 0.0x1 + 1.0x2 − 0.1x3 + 0.0x4 + 1.0x5 = 2.5 (0, 0, 0, 0, 0)T ≤ x ≤ ((5, 5, 5, 100, 100))T x2 integer yakni JI = {2}
Penyelesaian kontinu vektor dan pembagian: x∗ = (1.2, 2.5, 0.0, 0.0, 0.0)T JB = {1, 2} JS = {4, 5} JL = {3} JU = ∅
55 Hasil untuk contoh 2 Dengan persamaan sebagai berikut: x1 = 1.2 + 1.0x3 − 1.0x4 x2 = 2.5 − 0.1x3 − 1.0x5 x3 nonbasis pada l3 = 0. Nilai x3 meningkat. Sementara x2 menjadi integer layak pada x2 = 2 jika x3 mencapai 5, tentunya x1 melanggar batas atas sebelumnya yaitu u1 = 5 pada x3 = 3.8. Maka x1 → nonbasis pada u1 = 5 x3 → basis (pada 3.8) Operasi pivot memberikan persamaan berikut: x3 = −1.2 + 1.0x1 − c4 x2 = 2.6 − 0.1x1 − 0.1x4 − x5 Karena x1 = 5, maka x2 = 2.12 dan x3 = 3.8 Selanjutnya lepaskan x1 dari batas atas 5, karena hanya itu satu-satunya nonbasis (non integer). Tentunya pada proses ini terjadi cycling karena x1 menurun dari 5, x3 melanggar l3 = 0 saat x1 = 1.2 tetapi x2 tidak menjadi integer layak. Tidak ada pilihan lain karena x1 adalah satunya-satunya nonbasis.
56 3.5.3 Contoh 3 Contoh 3 mempunyai model yang sama dengan contoh 1 dan 2 kecuali partisi awal yang berbeda.
Definisi contoh 3 minimum f = (x1 − 1.2)2 + (x2 − 2.5)2 + x23 dengan kendala
1.0x1 + 0.0x2 − 1.0x3 + 1.0x4 +
0.0x5 = 1.2 0.0x1 + 1.0x2 + 0.1x3 + 0.0x4 + 1.0x5 = 2.5 (0, 0, 0, 0, 0)T ≤ x ≤ (5, 5, 1, 100, 100)T x2 integer yakni JI = {2}
Penyelesaian kontinu vektor dan pembagian: x∗ = (1.2, 2.5, 0.0, 0.0, 0.0)T JB = {1, 2} JS = {3} JL = {4, 5} JU = ∅
Hasil untuk contoh 3 Dengan persamaan sebagai berikut: x1 = 1.2 + 1.0x3 − 1.0x4 x2 = 2.5 − 0.1x3 − 1.0x5 x4 dan x5 nonbasis pada 0. Karena x2 adalah atu-satunya peubah integer basis
57 maka i0 = 2, dimana i = 2 merupakan calon tunggal untuk i0. Sama halnya dengan heuristik untuk menentukan j ∗ , j = 5 adalah calon tunggal untuk j ∗ (j = 4 tidak memenuhi syarat karena α24 = 0). Agar x5 berada di NL, mudah bagi CYCLE1 Murtagh untuk memindahkan peubah integer x2 dari basis. Berlawanan dengan contoh 1, pengakhiran CYCLE1 Murtagh tergantung pada pembagian awal.
3.5.4 Ringkasan Hasil Contoh CYCLE1 Dapat dilihat pada tabel 3.3.
58
Tabel 3.3 : Penyelesaian Problema dengan Pencarian Langsung
BAB 4 KESIMPULAN
Untuk pencarian layak yang dikembangkan dalam tesis ini berdasarkan peningkatan peubah basis dari batasannya sehingga diperolehnya penyelesaian integer terhadap peubah basis. Dalam kelanjutannya ditinjau nilai reduced cost untuk melakukan pencarian agar dapat memperbaiki nilai fungsi objektif. Kedua proses utama ini dinyatakan dalam CYCLE1 dan CYCLE2 berturut-turut. CYCLE1 merupakan usaha untuk memindahkan semua peubah integer dari basis. Iterasi dapat berakhir jika tidak ada lagi peubah yang tersisa pada basis. Kejadian 3 adalah kejadian yang diharapkan muncul, yakni variabel basis integer menjadi layak integer. Namun apabila semua nonbasis telah penjadi peubah integer tetapi CYCLE1 tetap tidak berakhir, maka dengan teknik merubah peubah nonbasis menjadi superbasis, yang tetap berada pada batasnya, iterasi CYCLE1 dapat berakhir. Dengan kata lain, untuk j ∗ peubah yang dipilih bukan nonbasis melainkan superbasis tak layak integer. Pada CYCLE2 yang dilakukan adalah menyesuaikan superbasis tak layak integer. Superbasis yang dipilih adalah yang terkecil. Namun dari pada hanya memperhatikan superbasis minimum ada baiknya untuk mencoba langkah penuh pada integer layak. Dengan catatan, batas sederhana pada basis tidak boleh dilanggar sebab jika dilanggar maka mustahil untuk mencapai integer layak pada xj .
59
DAFTAR PUSTAKA
Balas, E. and Mazzola, J.B. Nonlinier 0-1 Programming: I. Linearization Techniques II, Dominance Relations and Algorithm, Math. Progr. 30:1, 1984. Brent, R.P. Algorithms for minimization without derivatives, Prentice-Hall, 1973. Burkhard, R.E. and Rendl, F. A thermodynamically motivated simulation procedure for combinatorial optimization problems. European journal of Operations Research 17:169-174, 1984. Cooper, M.W. A Survey of Methods for Pure Nonlinier Integer Programming. Management Science 27:353-361, 1981. Dennis, J. and Torczon, V. Direct search methods on parallel machines. Rice University, Dept of Mathematical Sciences. Technical Report TR90-19, 1990. Duran, M.A. and Grosmann, I.E. An Outer-Approximation Algorithm for a Class of Mixed-Integer Nonlinier Programs. Mathematical Programming 36:307339, 1986. Fletcher, R. Practical methods of optimization. Wiley, 1987. Fletcher, R. and Reeves, C.M. Function minimization by conjugate gradients. Computer Journal, 7:149-154, 1964. Fiacco, A. and McCormick, G. Nonlinier programming: sequential unconstrained minimization techniques. Wiley, 1968. Garfinkel, R.S. and Nemhauser, G.L. Integer programming. Wiley, 1972. Gill, P.E., Murray, W. and Wright, M.H. Practical Optimization. Academic Press. ISBN 0-12-283952-8., 1981. Gill, P.E., Murray, W., Saunders, M.A. and Wright, M.H. GAMS/MINOS User Manual, Scientific Press, 1988. Goux, Jean-Piere, and Leyffer. S. Solving Large MINLPs on Computational Grids. Num. Analysis report NA/200, Department of Math. University of Dundee, 2001. Gupta, O.K. and Ravindran, A. Nonlinier integer programming algorithms:A Survey. OPSEARCH 20:189-206, 1983. Hansen, P. Methods of 01 nonlinear programming. Annals of Discrete Mathematics 5:53-70, 1979. Harjunkoski, I., Westerlund, T., Prn, R. and Skrifvars, H. Different transformations for solving non-convex trim-loss problems by MINLP. European Journal of Operational Research, 105:594-603,1998.
60
61 Hestenes, M.R. and Stiefel, E. Methods of conjugate gradients for solving linier systems. J. Res. N.B.S 49:409-436, 1952. Horner, P. Something to crowe about. OR/MS today, 38-44, 2000. Kuhn, H.W. and Tucker, A.W. Nonlinier programming.Proceedings of the second Berkeley symposium on mathematical statistics and probability, 481-492, Berkeley, University of California Press, 1951. Leyffer, S. Private communication. 1991. Mawengkang, H. and Murtagh, B.A. Solving Nonlinear Integer Programs with Large-Scale Optimization Software, Annals of Operations Research, 5.425437, 1986. Michalewicz, Z., Krawczyk, J.B., Kazemi M. and Janikow, C.Z. Genetic algorithms and optimal control problems. Proc. 29th IEEE Conference on Decision and Control, 1664-1666, 1990. Mohd, I.B. Global optimization using interval arithmetic. PhD dissertation, University of St Andrews, 1986. Moore, R.E. Interval analysis, Prentice-Hall, 1966. Morrow, M. Genetic algorithms. Australian Personal Computer 12:4, 85-93, 1991. Murtagh, B.A. Advanced Linear Programming: McGraw-Hill. ISBN 0-07-044095-6, 1981.
Computation and Practice.
Murtagh, B.A. Nonlinear Integer Programming with Applications in Manufacturing and Process Engineering. Proceeding of the Computational Techniques and Applications Conference.103-113, 1989. Murtagh, B.A. and Saunders, M.A. A Projected Lagrangian Algorithm and its Implementation for Sparse Nonlinear Constraints. Mathematical Programming Study 16:84-117, 1982. Murtagh, B.A. and Saunders, M.A. Large-Scale Linearly Constrained Optimization. Mathematical Programming 14:41-72, 1978 Murtagh, B.A. and Saunders, M.A. MINOS 5.1 Users Guide. Report SOL 83-2OR, Stanford University, December 1983 (revised January 1987), 1987. Myers, D.C. The design of branch and bound, Lagrangian relaxation and subgradient strategies for mixed integer programming problems. PhD dissertation. Virginia Polytechnic Institute and State University, 1984. Nelder, J.A. and Mead, R. A simplex method for function minimization. Computer Journal 7:308-313, 1965. Nemhauser, G.L. and Wolsey, L.A. Integer and Combinatorial Optimization. Wiley.ISBN 0-471-82819-X, 1988.
62 Press, W.H., Flannery, B.P., Teukolsky, S.A. and Vetterling, W.T. Numerical Recipes. Cambridge University Press, 1988. Quist, A.J., van Geemert, R., Hoogenboom, J.E., Ills, T., de Kler, E., Roos, C. and Terlaky, T. Optimization of a nuclear reactor core reload pattern using nonlinear optimization and search heuristics. Draft paper, Delft University of Technology, Faculty of Applied Mathematics, Department of Operation Research, Mekelweg 4, 2628 CD Delft, The Netherlands, September 1997. Ratschek, H. and Rokne, J. New computer methods for global optimization. Halstead Press, 1988. Ravindran, A., Phillips, D.T. and Solberg, J.J. Operations Research, Principles and Practice. 2nd edition. Wiley, 1987. Scarf, H.E. Mathematical programming and economic theory. Operations Research, 38:377-385, 1990. Scarf, H.E. Neighbourhood Systems for Production Sets with Indivisibilities. Econometrica 54:507-532, 1986. Scarf, H.E. Testing for optimality in the absence of convexity. Social Choice and Publish Decision Making. Chapter 6. Cambridge University Press 1986. Edited by Heller, W.P., Starr, R.P. and Starrett, D.A., 1986. Shin, D., Gerdal Z. and Griffin, O. A penalty approach for nonlinear optimization with discrete design variables. Engineering optimization 16:29-42, 1990. Sigmund, O. A 99 line topology optimization code written in matlab. Structural Optimization, 2000. Torczon, V. Multi-directional search: a direct search algorithm for parallel machines. PhD dissertation. Rice University, Dept of Mathematical Sciences. Techical Report TR90-7, 1990. Wayner, P. Genetic algorithms. BYTE 16:1, 361-368, 1991. Wilhelm, M.R. and Ward, T.L. Solving quadratic assignment problems by simulated annealing. IIE Transactions 19:1, 107-119, 1987.
