PENGEMBANGAN ALGORITMA PENCARIAN UNTUKMENYELESAIKAN PROBLEMA PROGRAM
TAKLINIER INTEGER CAMPURAN
TESIS
Oleh
JUANDI SIDABUTAR
067021019/MT
SEKOLAH PASCASARJANA
UNIVERSITAS SUMATERA UTARA
MEDAN
2008
Juandi Sidabutar: Pengembangan Algoritma Pencarian Untuk Menyelesaikan Problema Program Taklinier Integer Campuran, 2008. USU e-Repository © 2008
PENGEMBANGAN ALGORITMA PENCARIAN UNTUKMENYELESAIKAN PROBLEMA PROGRAM
TAKLINIER INTEGER CAMPURAN
T E S I S
Untuk Memperoleh Gelar Magister Sains Dalam
Program Studi Magister Matematika Pada Sekolah Pascasarjana
Universitas Sumatera Utara
Oleh
JUANDI SIDABUTAR
067021019/MT
SEKOLAH PASCASARJANA
UNIVERSITAS SUMATERA UTARAMEDAN
2008
Juandi Sidabutar: Pengembangan Algoritma Pencarian Untuk Menyelesaikan Problema Program Taklinier Integer Campuran, 2008. USU e-Repository © 2008
Judul Tesis : PENGEMBANGAN ALGORITMA PENCARIAN UNTUKMENYELESAIKAN PROBLEMA PROGRAMTAKLINIER INTEGER CAMPURAN
Nama Mahasiswa : Juandi SidabutarNomor Pokok : 067021019Program Studi : Magister Matematika
Menyetujui,
Komisi Pembimbing
(Prof. Dr. Herman Mawengkang) (Dr. Saib Suwilo, MSc)Ketua Anggota
Ketua Program Studi Direktur
(Prof. Dr. Herman Mawengkang) (Prof. Dr. Ir. T.Chairun Nisa. B,M.Sc)
Tanggal lulus: 5 Juni 2008
Juandi Sidabutar: Pengembangan Algoritma Pencarian Untuk Menyelesaikan Problema Program Taklinier Integer Campuran, 2008. USU e-Repository © 2008
Telah diuji pada
Tanggal 5 Juni 2008
PANITIA PENGUJI TESIS
Ketua : Prof. Dr. Herman Mawengkang
Anggota : Dr. Saib Suwilo, MSc
Dr. Iryanto, MSi
Dr. Sutarman, MSc
Juandi Sidabutar: Pengembangan Algoritma Pencarian Untuk Menyelesaikan Problema Program Taklinier Integer Campuran, 2008. USU e-Repository © 2008
ABSTRAK
Problema matematika khususnya program nonlinier pada tesis ini mempunyaistruktur yang mengkarakteristikkan pada subhimpunan variabel yang dibatasidan diasumsikan pada nilai diskrit yang linier dan dapat dipisahkan dari variabelkontinu. Strategi pengeluaran variabel nonbasis dari batasnya, dikombinasikandengan metode ”kendala aktif” dan gagasan dari superbasis, yang dibangun un-tuk memecahkan efesien problema dengan tidak memperhatikan kesatuan syarat.Strategi ini digunakan untuk membuat variabel basis noninteger yang tepat se-hingga bergerak pada titik integer sekitarnya. Studi criteria untuk memilih varia-bel nonbasis yang bekerja dengan strategi integer juga telah dilakukan. Implemen-tasi yang sukses dari algoritma ini dicapai pada bermacam pengujian problem.Hasilnya menunjukkan bahwa pengajuan strategi integer sedang dipromosikandalam mencegah klas tertentu dari problema Program Integer Campuran.
Kata Kunci : Algoritma, Program Taklinier Integer, Program Taklinier IntegerCampuran
i
Juandi Sidabutar: Pengembangan Algoritma Pencarian Untuk Menyelesaikan Problema Program Taklinier Integer Campuran, 2008. USU e-Repository © 2008
ABSTRACT
The special nonlinear mathematical programming problem which is addressed inthis paper has a structure characterized by a subset of variables restricted to as-sume discrete values, which are linear and separable 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 forefficiently tackling such a problem by ignoring the integrality requirements, thisstrategy is used to force the appropriate non-integer basic variables to move totheir neighbourhood integer points. A study of criteria for choosing a nonbasicvariables to work with in the integerizing strategy has also been made. Successfulimplementation of these algorithms was achieved on various test problems. Theresult show that the proposed integerizing strategy is promosing in tackling cer-tain classes of mixed integer programming problems.
Keyword : Algorithm, Integer Nonlinear Programming, Mixed Integer NonlinearProgramming
ii
Juandi Sidabutar: Pengembangan Algoritma Pencarian Untuk Menyelesaikan Problema Program Taklinier Integer Campuran, 2008. USU e-Repository © 2008
KATA PENGANTAR
Penulis mengucapkan puji syukur kepada Tuhan Yang Maha Esa atas berkat
dan karuniaNya sehingga penulisan tesis yang berjudul ”Pengembangan Al-
goritma Pencarian untuk Menyelesaikan Problema Program Taklinier
Integer Campuran” dapat dirampungkan. Tesis ini merupakan tugas akhir
pada Sekolah Pascasarjana Program Studi Magister Matematika, Universitas Su-
matera Utara. Pada kesempatan ini, penulis menyampaikan ucapan terima kasih
dan penghargaan yang sebesar-besarnya kepada :
Gubernur Sumatera Utara dan Kepala Bappeda Propinsi Sumatera Utara
beserta stafnya yang telah memberikan beasiswa kepada penulis dan Kepala Di-
nas Pendidikan Kota Medan yang telah memberi izin kepada penulis untuk
mengikuti perkuliahan di Sekolah Pascasarjana Program Studi Magister Mate-
matika, Universitas Sumatera Utara.
Prof. dr. Chairuddin P. Lubis, DTM&H, Sp. Ak selaku Rektor Universitas
Sumatera Utara dan Prof. Dr. Ir. T. Chairun Nisa B, M.Sc selaku Direktur
Sekolah Pascasarjana Universitas Sumatera Utara yang telah memberikan kesem-
patan kepada penulis untuk mengikuti perkuliahan pada Sekolah Pascasarjana
pada Program Magister Matematika Universitas Sumatera Utara, Medan.
Prof. Dr. Herman Mawengkang, selaku Ketua Program Studi Matematika
SPs USU dan juga sebagai pembimbing-I yang dengan penuh kesabaran memo-
tivasi dan membimbing penulis serta memberikan buku dan jurnal-jurnal yang
berkaitan dengan penelitian yang penulis lakukan sehingga tesis ini dapat selesai.
iii
Juandi Sidabutar: Pengembangan Algoritma Pencarian Untuk Menyelesaikan Problema Program Taklinier Integer Campuran, 2008. USU e-Repository © 2008
Dr. Saib Suwilo, M.Sc, selaku Sekretaris Program Studi Matematika SPs
USU dan juga sebagai pembimbing-II yang dengan penuh kesabaran memberikan
dukungan moril, kritik dan saran sehingga penulis dapat menyelesaikan tesis ini.
Dr. Sutarman, M.Sc dan Drs. Iryanto, M.Si selaku pembanding yang
telah banyak memberikan saran, masukan dan arahan yang membangun terhadap
kesempurnaan penulisan tesis ini.
Seluruh Staf Pengajar pada SPs USU yang dengan sungguh-sungguh telah
berusaha memberikan ilmunya kepada penulis selama mengikuti perkuliahan.
Seluruh Staf Administrasi SPs USU, teristimewa Sdri. Misiani, S.Si dan
Sdri. Sri Rayani Tanjung, SSi yang telah memberikan bantuan dan pelayanan
yang baik kepada penulis.
Rekan-rekan seperjuangan, mahasiswa angkatan kedua, atas kerja sama,
kebersamaan dan bantuannya dalam mengatasi berbagai masalah selama perku-
liahan berlangsung.
Secara khusus penulis ingin menyampaikan terima kasih dan sayang yang
mendalam kepada orang tua Gr. St. Mayang Redikson Sidabutar (Alm)
dan Panamotan Br Samosir gelar Op. Sahdo; mertua Gr. Mula Hamzah
Naibaho, BA dan Vtrn. Pinta Omas Bunga br. Siburian gelar Op. Ma-
ngasi; Istri tercinta Junita Naibaho, S.Pd dan Ananda tersayang Eko Sahdo
Immanuel Yohan Clinton Sidabutar yang senantiasa mendoakan, mendorong
dan melayani dengan penuh kasih, sabar serta memberikan pengorbanan yang
tidak terbatas kepada penulis selama mengikuti perkuliahan.
iv
Juandi Sidabutar: Pengembangan Algoritma Pencarian Untuk Menyelesaikan Problema Program Taklinier Integer Campuran, 2008. USU e-Repository © 2008
Pada kesempatan ini penulis menyampaikan terima kasih kepada seluruh
Keluarga Besar Perguruan Kristen Immanuel Medan yang terus men-
doakan dan memotivasi serta membantu penulis selama mengikuti pendidikan di
SPs Program Studi Magister Matematika Universitas Sumatera Utara, Medan.
Semoga tesis ini bermanfaat bagi pembaca dan pihak-pihak yang memer-
lukannya.
Medan, 20 Juni 2008
Penulis,
Juandi Sidabutar
v
Juandi Sidabutar: Pengembangan Algoritma Pencarian Untuk Menyelesaikan Problema Program Taklinier Integer Campuran, 2008. USU e-Repository © 2008
RIWAYAT HIDUP
Juandi Sidabutar, dilahirkan di Kabupaten Simalungun pada tanggal 11
September 1958, merupakan anak kedua dari tujuh orang bersaudara anak dari
Alm. Gr. St. Mayang Redikson Sidabutar dan Panamotan Br Samosir gelar Op.
Sahdo. Menamatkan pendidikan SD Negeri Jorlang Hataran pada tahun 1971,
SMP Negeri Tiga Balata pada tahun 1974 dan SMA Negeri 3 Pematang Siantar
pada tahun 1977. Tahun 1978 bebas testing di Institut Keguruan dan Ilmu Pen-
didikan (IKIP) Negeri Medan dan memperoleh gelar Sarjana Muda Pendidikan
Matematika pada tahun 1981, selama perkuliahan mendapat beasiswa Pelita dan
pada tahun 1980 diterima menjadi Mahasiswa Beasiswa Ikatan Dinas pada Pen-
didikan Guru Sekolah Lanjutan Atas (PGSLA / D3-A3) dan lulus pada tahun
1981. Pada tahun 1982 penulis menjadi tenaga pengajar sukarela di SMA Negeri
Sumbul Kabupaten Dairi. Pada tahun 1983 menjadi Calon Pegawai Negeri Sipil
(CPNS) di SMA Negeri Aek Kanopan Labuhan Batu. Menjadi Pegawai Negeri
Sipil (PNS) tahun 1984. Mengikuti Pendidikan S-1 Transfer di Institut Keguruan
dan Ilmu Pendidikan (IKIP) Negeri Medan tahun 1985. Tahun 1986 Wakil Kepala
SMA Swasta Pelita Aek Kanopan Labuhan Batu dan mengikuti Pelatihan Profesi
Guru Matematika di BPG Sunggal Medan 6 (enam) bulan tahap pertama. Tahun
1987 mengikuti Pelatihan Profesi Guru Matematika di BPG Sunggal Medan 6
(enam) bulan tahap kedua. Tahun 1988 menjadi Kepala SMA Swasta Abdi Karya
Nusantara Aek Kanopan Labuhan Batu. Tahun 1989 memasuki Universitas Ter-
buka cabang Medan. Tahun 1990 diangkat menjadi Guru Diperbantukan (Dpk)
di SMA Swasta Kristen Immanuel Medan. Tahun 1989/1990 diangkat menjadi
penatar (guru inti) Guru Matematika Provinsi Sumatera Utara dan Daerah Is-
timewa Banda Aceh. Menyelesaikan Pendidikan Sarjana di STKIP Pelita Bangsa
vi
Juandi Sidabutar: Pengembangan Algoritma Pencarian Untuk Menyelesaikan Problema Program Taklinier Integer Campuran, 2008. USU e-Repository © 2008
tahun 2006. Tahun 1997 sampai tahun 2008 dipercaya menjadi unsur pimpinan
di SMA Swasta Kristen Immanuel Medan.
Penulis menikah dengan Junita Naibaho, S.Pd pada tahun 1986 dan telah
dikaruniai Tuhan satu orang anak Eko Sahdo Immanuel Yohan Clinton Sidabutar
yang saat ini telah tamat dari Sekolah Menengah Pertama (SMP) Immanuel.
Pengalaman berorganisasi : Ketua OSIS SMA Negeri 3 Pematang Siantar
tahun 1976. Anggota Senat Mahasiswa IKIP Negeri Medan tahun 1978/1979.
Ketua Badan Perwakilan Mahasiswa IKIP Negeri Medan tahun 1980/1981. Ke-
tua Panitia Olimpiade Matematika antar Pelajar SMA Se-Sumatera Utara Im-
manuel ke-I tahun 2000, Immanuel ke-2 tahun 2001 dan Immanuel ke-3 tahun
2002. Sekretaris Umum Assosiasi Guru Matematika SMA/MA Sumatera Utara
tahun 2007/2010, Ketua 3 Himpunan Matematika Indonesia Wilayah Nangro
Aceh Darussalam dan Sumatera Utara (IndoMS NAD-SUMUT) tahun 2008/2010.
Pada tahun 2006 diperkenankan mengikuti pendidikan Program Studi Ma-
gister Matematika di Sekolah Pascasarjana Universitas Sumatera Utara dengan
program beasiswa dari Bappeda Propinsi Sumatera Utara.
vii
Juandi Sidabutar: Pengembangan Algoritma Pencarian Untuk Menyelesaikan Problema Program Taklinier Integer Campuran, 2008. USU e-Repository © 2008
DAFTAR ISI
Halaman
ABSTRAK . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . i
ABSTRACT . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ii
KATA PENGANTAR . . . . . . . . . . . . . . . . . . . . . . . . . iii
RIWAYAT HIDUP . . . . . . . . . . . . . . . . . . . . . . . . . . vi
DAFTAR ISI . . . . . . . . . . . . . . . . . . . . . . . . . . . . . viii
DAFTAR TABEL . . . . . . . . . . . . . . . . . . . . . . . . . . . x
DAFTAR GAMBAR . . . . . . . . . . . . . . . . . . . . . . . . . xi
BAB 1 PENDAHULUAN . . . . . . . . . . . . . . . . . . . . . . . 1
1.1 Latar Belakang . . . . . . . . . . . . . . . . . . . . . . 1
1.2 Perumusan Masalah . . . . . . . . . . . . . . . . . . . . 5
1.3 Tujuan Penelitian . . . . . . . . . . . . . . . . . . . . . 5
1.4 Kontribusi Penelitian . . . . . . . . . . . . . . . . . . . 6
1.5 Metodologi Penelitian . . . . . . . . . . . . . . . . . . . 6
BAB 2 TINJAUAN PUSTAKA . . . . . . . . . . . . . . . . . . . . 8
BAB 3 PROGRAM LINIER DAN TAKLINIER . . . . . . . . . . . . 11
3.1 Program Linier . . . . . . . . . . . . . . . . . . . . . . 11
3.1.1 Dualitas . . . . . . . . . . . . . . . . . . . . . . 13
3.1.2 Metode Simplex . . . . . . . . . . . . . . . . . . . 14
3.2 Program Integer Linier . . . . . . . . . . . . . . . . . . 16
3.3 Program Taklinier . . . . . . . . . . . . . . . . . . . . . 20
3.4 Program Taklinier Integer . . . . . . . . . . . . . . . . . 21
viii
Juandi Sidabutar: Pengembangan Algoritma Pencarian Untuk Menyelesaikan Problema Program Taklinier Integer Campuran, 2008. USU e-Repository © 2008
3.4.1 Teknik Linieritas . . . . . . . . . . . . . . . . . . 24
3.4.2 Pendekatan Branch and Bound . . . . . . . . . . . 29
3.4.3 Teknik Enumerasi Implisit . . . . . . . . . . . . . . 34
3.4.4 Pendekatan Program Dinamik . . . . . . . . . . . . 37
3.4.5 Metode Dekomposisi Benders . . . . . . . . . . . . 39
3.4.6 Metode-metode Lainnya . . . . . . . . . . . . . . . 42
3.4.7 Metode Outer-Approximation . . . . . . . . . . . . 43
BAB 4 PENGEMBANGAN ALGORITMA PENCARIAN PADA PRO-BLEMA PROGRAM TAKLINIER INTEGER CAMPURAN . . 56
4.1 Kerangka Dasar Metode Penyelesaian . . . . . . . . . . . 56
4.2 Algoritma dari Metode . . . . . . . . . . . . . . . . . . 61
4.3 Contoh Kasus Masalah Problema Sintesa dalam Design ProsesKimia . . . . . . . . . . . . . . . . . . . . . . . . . . 64
4.3.1 Contoh 1. Problema Perencanaan Kecil . . . . . . . 64
4.3.2 Contoh 2. Problema Proses Sintesa Sistem . . . . . . 67
4.3.3 Contoh 3. Problema Sintesa Flowsheet . . . . . . . . 70
BAB 5 KESIMPULAN DAN SARAN . . . . . . . . . . . . . . . . . 72
5.1 Kesimpulan . . . . . . . . . . . . . . . . . . . . . . . . 72
5.2 Saran . . . . . . . . . . . . . . . . . . . . . . . . . . . 73
DAFTAR PUSTAKA . . . . . . . . . . . . . . . . . . . . . . . . . 74
ix
Juandi Sidabutar: Pengembangan Algoritma Pencarian Untuk Menyelesaikan Problema Program Taklinier Integer Campuran, 2008. USU e-Repository © 2008
DAFTAR TABEL
Nomor Judul Halaman
4.1 Hasil Contoh 1 . . . . . . . . . . . . . . . . . . . . . . . . 66
4.2 Hasil Contoh 2 . . . . . . . . . . . . . . . . . . . . . . . . 70
4.3 Hasil Contoh 3 . . . . . . . . . . . . . . . . . . . . . . . . 71
x
Juandi Sidabutar: Pengembangan Algoritma Pencarian Untuk Menyelesaikan Problema Program Taklinier Integer Campuran, 2008. USU e-Repository © 2008
DAFTAR GAMBAR
Nomor Judul Halaman
4.1 Struktur Super pada Contoh 1 . . . . . . . . . . . . . . . . 65
4.2 Struktur Super pada Contoh 2 . . . . . . . . . . . . . . . . 67
4.3 Struktur Super pada Contoh 3 . . . . . . . . . . . . . . . . 71
xi
Juandi Sidabutar: Pengembangan Algoritma Pencarian Untuk Menyelesaikan Problema Program Taklinier Integer Campuran, 2008. USU e-Repository © 2008
BAB 1
PENDAHULUAN
1.1 Latar Belakang
Solusi algoritma untuk Program Taklinier Integer Campuran (Mixed Inte-
ger Non Linear Programmings (MINLP)) telah menjadi penelitian yang sering
dilakukan. Penelitian ini diharapkan memiliki kemajuan yang terus menerus
dalam pengembangan dan implementasi yang baik dari algoritma Program Linier
Integer Campuran (Mixed Integer Linear Programmings (MILP)) dan Program
Taklinier (Non Linear Programmings (NLP)), baik dengan cara mengkombinasi
keahlian dari field dan hasil yang signifikan. Penelitian ini memperkenalkan se-
buah kerangka algoritma pencarian untuk MINLP dari kolaborasi ini. Untuk
MINLP dengan relaksasi konvex, kerangka ini adalah algoritma yang tepat, akan
tetapi dapat juga diaplikasikan pada MINLP yang tidak konvex sebagai heuristik.
Program Taklinier Integer Campuran (MINLP) dapat dinyatakan sebagai
berikut:
P
min f(x, y)
s.t.
g(x, y) ≤ 0
x ∈ X ∩ Zn, y ∈ Y
(1.1)
dimana X dan Y adalah polyhedral subset dari Rn dan Rp berturut-turut,
dan X adalah terbatas (bounded). Fungsi f : X × Y → R dan g : X × Y → Rm
adalah kontinu dengan differentiable dua kali. Ketika f dan g adalah fungsi
1
Juandi Sidabutar: Pengembangan Algoritma Pencarian Untuk Menyelesaikan Problema Program Taklinier Integer Campuran, 2008. USU e-Repository © 2008
2
konvex, P dikatakan konvex.
Problema program taklinier integer muncul dalam beragam pemakaian. Pe-
makaian dalam bidang kimia teknik mencakup proses sintesis, penjadwalan siklik,
dan rancangan kolom destilasi. Problema program taklinier integer juga muncul
sebagai problema Cutting Stock taklinier dalam industri kertas dan dalam opti-
masi konfigurasi pompa. Pemodelan struktur model simultan dan spektroskopi
infra merah membentuk problema program taklinier integer campuran kuadratik
berskala besar.
Baru baru ini, perhatian dalam model program taklinier integer telah juga
dimotivasi oleh aplikasi dari industri nuklir. Problemanya adalah memaksimumkan
efisiensi atau kinerja reaksi nuklir setelah operasi pemuatan. Suatu bidang pe-
makaian yang baru dan menarik adalah optimasi topologi dimana peubah biner
memodelkan ada atau tidaknya material dalam setiap elemen hingga.
Aplikasi lainnya muncul dalam rancangan jaringan air, dimana arah ali-
ran melalui suatu pipa dimodelkan oleh disjunksi. Aplikasi berikutnya adalah
dalam financial seperti perencanaan strategis dalam rancangan jaringan teleko-
munikasi, dimana aspek integer menyajikan jumlah serat optik yang akan ditem-
patkan dalam pipa, nonlinieritas muncul dari elastisitas yang berkenaan dengan
strategi pemberian harga di masa akan datang. Pemakaian model financial juga
baru-baru ini dikemukakan dalam problema alokasi asset pada manajemen data,
yang objektifnya meminimumkan resiko.
Problema (P ) demikian ini banyak menarik perhatian para peneliti disam-
ping karena pemakaiannya yang banyak serta dalam berbagai bidang kehidupan
nyata, tetapi juga karena ia termasuk dalam problema sulit non polynomial (NP
Juandi Sidabutar: Pengembangan Algoritma Pencarian Untuk Menyelesaikan Problema Program Taklinier Integer Campuran, 2008. USU e-Repository © 2008
3
Hard Problema).
Dua ide utama yang diajukan untuk menyelesaikan MINLP konvex, yang
pertama adalah pendekatan Branch and Bound (BB), dimana batas bawah untuk
sub problema P adalah :
P
min f(x, y)
s.t.
g(x, y) ≤ 0
x ∈ X ∩ Zn, y ∈ Y
(1.2)
dengan polyhedral subset X dari X, dihitung dengan menyelesaikan re-
laksasi kontinu dari PX , dan yang lain P ditulis relaksasi kontinu dari asosiasi
problema P yaitu :
PX
minf(x, y)
s.t.
g(x, y) ≤ 0
x ∈ X, y ∈ Y
(1.3)
dengan catatan bahwa batas bawah dari pendekatan BB dapat diperkuat de-
ngan cutting planes seperti penelitian yang terdahulu ( R. Stubbs and S. Mehrotra,
1999).
Branch and Bound merupakan algoritma umum yang telah dipakai pada
berbagai problema dalam optimisasi kombinatorial dan program integer. Land
and Doig (1960) mula-mula menerapkan algoritma Branch and Bound untuk pro-
blema perjalanan penjaja. Namun perlu dicatat bahwa pemakaian algoritma ini
Juandi Sidabutar: Pengembangan Algoritma Pencarian Untuk Menyelesaikan Problema Program Taklinier Integer Campuran, 2008. USU e-Repository © 2008
4
dalam menyelesaikan program integer akan memberikan pengertian bahwa dise-
tiap buhul percabangan harus diselesaikan problema program kuadratik. Dengan
demikian algoritma demikian ini secara komputasi tentunya tidak efisien.
Alternatif kedua adalah dengan pendekatan antara penyelesaian MILP dan
NLP yang konvex. Dua algoritma yang berbeda ini dapat diikuti oleh pen-
dekatan berikut: Generalisasi Dekomposisi Benders dan Outer Approximation
(OA). MILP diselesaikan dengan dua pendekatan ini diperoleh dari P dengan
menukar fungsi nonlinier oleh polyhedral outer approximation. Dikatakan (x, y)
adalah solusi optimal dari MILP, NLP yang konvex adalah P dengan x tetap ke
x(PX). Catatan bahwa pendekatan yang berhubungan adalah algoritma cutting-
plane secara luas yang mengandalkan solusi yang berturut-turut dari problema
MILP.
Kerangka perhitungan dalam penelitian ini menggunakan outer approkxi-
mation dan relaksasi sub problema PX ke perhitungan batas bawah, dan PX
menghitung batas atas dalam pola branch and cut yang fleksibel. Ketika hanya
relaksasi problema PX digunakan untuk menghitung batas bawah, maka kita akan
mempunyai algoritma BB klasik. Ketika Outer Approximation dan PX digunakan
bergantian pada akar buhul (node), maka kita akan mendapatkan algoritma OA
klasik.
Oleh Karena cukup banyaknya problema dunia nyata yang dapat difor-
mulasikan dalam model (P ) ditambah lagi dengan sulitnya mengatasi problema
tersebut secara analitis, maka perlu dikembangkan suatu prosedur atau algoritma
sedemikian hingga problema (P ) dapat diselesaikan secara efisien.
Juandi Sidabutar: Pengembangan Algoritma Pencarian Untuk Menyelesaikan Problema Program Taklinier Integer Campuran, 2008. USU e-Repository © 2008
5
1.2 Perumusan Masalah
Branch and Bound sebagai suatu algoritma yang biasa dipakai untuk menye-
lesaikan problema program integer linier sulit diterapkan pada problema program
taklinier integer terhadap kondisi yang tidak konveks. Namun perlu dicatat bahwa
pemakaian algoritma ini dalam menyelesaikan program integer akan memberikan
pengertian bahwa disetiap buhul percabangan harus diselesaikan problema pro-
gram kuadratik. Dengan demikian algoritma demikian ini secara komputasi ten-
tunya tidak efisien. Oleh karena itu perlu dikembangkan suatu algoritma untuk
menyelesaikan problema tersebut.
1.3 Tujuan Penelitian
Adapun tujuan dalam penelitian ini adalah mengembangkan suatu algoritma
untuk menyelesaikan secara efisien problema program taklinier integer campu-
ran serta penerapannya dalam situasi komersial dimana kebutuhan kemampuan
integer merupakan syarat penting dari model. Dengan adanya algoritma dan
terciptanya perangkat lunak diharapkan dapat banyak membantu dunia indus-
tri dan perguruan tinggi yang bergumul dengan model seperti pada problema
(P ). Pengembangan algoritma yang akan dihasilkan dari penelitian ini juga mem-
berikan kontribusi penting dalam bidang program integer dan program taklinier
integer.
Juandi Sidabutar: Pengembangan Algoritma Pencarian Untuk Menyelesaikan Problema Program Taklinier Integer Campuran, 2008. USU e-Repository © 2008
6
1.4 Kontribusi Penelitian
Model problema banyak terdapat pada berbagai problema dunia nyata seperti
problema sintesa dalam rancangan proses kimia, investasi, sistem manajemen pe-
ngawasan, mutu air, pemasaran produk baru. Dengan adanya algoritma yang
efisien untuk menanggulangi model problema demikian, sehingga akan banyak
membantu para peneliti ataupun para pengambil keputusan yang bergumul de-
ngan model seperti pada program. Sehingga terdapat suatu algoritma untuk
menyelesaikan problema dalam skala yang luas. Melalui algoritma ini akan da-
pat digali keuntungan sifat linearitas dari variabel diskrit dan konveksitas fungsi
berharga kontinu.
1.5 Metodologi Penelitian
Penelitian ini membahas tentang pengembangan algoritma pencarian untuk
menyelesaikan problema program taklinier integer campuran. Sebagai langkah
awal dibicarakan konsep dasar program linier, integer linier, taklinier dan takli-
nier integer. Selanjutnya dibahas beberapa teknik dan pendekatan menyelesaikan
program taklinier integer. Pada bagian akhir dibahas mengenai pengembangan al-
goritma pencarian untuk menyelesaikan problema program taklinier integer cam-
puran yang terdiri dari kerangka dasar penyelesaian, algoritma dari metode, dan
tiga contoh kasus masalah problema sintesa dalam design proses kimia.
Problema program matematika nonlinier pada penelitian ini mempunyai
karakteristik struktur dengan subhimpunan variabelnya yang diasumsikan berni-
lai diskrit yang linier dan dapat dipisahkan dari variabel kontinu. Strategi dari
pembebasan variabel nonbasis dari batasannya, dikombinasikan dengan metode
Juandi Sidabutar: Pengembangan Algoritma Pencarian Untuk Menyelesaikan Problema Program Taklinier Integer Campuran, 2008. USU e-Repository © 2008
7
”kendala aktif” dan gagasan dari superbasis yang telah dibangun untuk meme-
cahkan efisiensi problema dengan tidak memperhatikan syarat kesatuan. Strategi
ini digunakan untuk menguatkan variabel basis non-integer yang tepat terhadap
titik-titik integer disekitarnya.
Penelitian dari criteria untuk memilih variabel nonbasic pada strategi kesa-
tuan juga telah dibuat. Implementasi yang sukses dari algoritma ini dicapai pada
bermacam-macam tes problema. Hasilnya menunjukkan bahwa tujuan strategi
kesatuan diajukan untuk memecahkan klas tertentu dari problema program inte-
ger campuran.
Juandi Sidabutar: Pengembangan Algoritma Pencarian Untuk Menyelesaikan Problema Program Taklinier Integer Campuran, 2008. USU e-Repository © 2008
BAB 2
TINJAUAN PUSTAKA
Beberapa algoritma telah diajukan untuk menyelesaikan program taklinier
integer campuran (MINLP). Di bawah ini disampaikan beberapa algoritma terse-
but sebagai suatu kajian literatur.
Bonami et al. (2005), mengajukan sebuah kerangka algoritma yang konvex
pada program taklinier integer campuran. Penelitiannya dimotivasi pada kenya-
taan bahwa MINLP adalah sebuah daerah yang penting dan sulit, yang mem-
butuhkan pengembangan metode dan software baru untuk menyelesaikan pro-
blema dalam skala yang luas. Penelitian ini merepresentasikan langkah pertama
dalam projek yang terus menerus dilakukan pada lingkungan, dan mengajukan
COIN-OR sebagai software optimisasi. Algoritma yang diajukan untuk diim-
plementasikan adalah algoritma klas dari hybrid, yang Branch and Bound dan
polyhedral outer approximation.
Pedroso (2004), mengajukan beberapa algoritma yang mengkombinasi enu-
mirasi parsial dengan meta-heuristik untuk solusi umum MILP. Enumirasi ini
didasarkan pada nilai primal yang dapat menentukan variabel integer dari pro-
blema. Penelitian ini juga membangun beberapa algoritma untuk integrasi dan
mengujinya menggunakan himpunan dari tanda-tanda problema yang dikenal.
Borchers and Mitchell (1994), menggambarkan code Branch and Bound un-
tuk 0-1 pada MINLP dengan fungsi objektif dan kendala yang konvex. Code terse-
but menggunakan heuristik untuk mendeteksi subproblema, dan menciptakan dua
8
Juandi Sidabutar: Pengembangan Algoritma Pencarian Untuk Menyelesaikan Problema Program Taklinier Integer Campuran, 2008. USU e-Repository © 2008
9
subproblema baru untuk menyelesaikan problema yang penting menjadi optimal.
Hasil perhitungan dari contoh problema menunjukkan bahwa heuristik ini dapat
menurunkan waktu solusi untuk beberapa problem secara signifikan.
Exler and Schittkowski (2006), mengajukan sebuah modifikasi metode dari
rangkaian program kuadratik untuk menyelesaikan problem MINLP. Penelitian
ini mengasumsikan bahwa variabel integer mempunyai pengaruh yang halus pada
model fungsi. Algoritma ini distabilisasikan dengan metode daerah terpercaya de-
ngan koreksi Yuan dua kali. Hessian dari fungsi Lagrange diapproksimasi dengan
rumus kuasi Newton kepada variabel integer dan kontinu. Hasil yang mengejutkan
bahwa jumlah dari fungsi yang dievaluasi, banyak criteria kinerja yang penting
kurang dari jumlah fungsi yang dibutuhkan untuk menyelesaikan problema tanpa
variabel integer.
Mawengkang and Murtagh (1985), mengajukan penyelesaian program tak-
linier integer dengan software optimisasi yang skala luas menggunakan MINOS.
Teknik ini dipresentasikan untuk memperluas pencarian kendala untuk menye-
lidiki solusi integer yang layak sehingga solusi optimal kontinu diperoleh. Perhi-
tungan menggunakan pendekatan ini digambarkan untuk dua klas problema yaitu
problema kuadratik dan desain jaringan problema.
Balas dan Mazzola (1984), mengajukan suatu teknik linearisasi yang cukup
efisien untuk menyelesaikan program taklinier integer dengan semua peubahnya
bernilai 0 atau 1. Begitupun, teknik linearisasi akan mengakibatkan terjadinya
penambahan jumlah peubah dan kendala. Dari pengalaman komputasi, metode
demikian ini hanya berlaku untuk problema berskala kecil. Teknik linearisasi yang
juga mentransformasi problema (P) menjadi polynomial konveks 0-1 diajukan
Juandi Sidabutar: Pengembangan Algoritma Pencarian Untuk Menyelesaikan Problema Program Taklinier Integer Campuran, 2008. USU e-Repository © 2008
10
oleh Stubbs dan Mehrotta (1999), Mawengkang (1996) juga mengajukan suatu
teknik linearisasi untuk menyelesaikan masalah (P) untuk rute kenderaan (vehicle
Routing).
Mawengkang (1991), mengajukan algoritma outer approximation untuk me-
nyelesaikan klas MINLP. Dalam model variabel diskrit adalah linier dan terpisah
dari variabel kontinu yang muncul sebagai fungsi konvex linier dan nonlinear.
Algoritma ini menggali secara efektif struktur tertentu dari problema dan terdiri
dari menyelesaikan barisan terbatas subproblema program nonlinier tereduksi dan
program relaks linier integer campuran.
Juandi Sidabutar: Pengembangan Algoritma Pencarian Untuk Menyelesaikan Problema Program Taklinier Integer Campuran, 2008. USU e-Repository © 2008
BAB 3
PROGRAM LINIER DAN TAKLINIER
3.1 Program Linier
Problema program linier melibatkan optimisasi dari fungsi objektif linier, de-
ngan subjeknya adalah persamaan linier dan kendala merupakan pertidaksamaan.
Program linier mencoba mendapatkan keluaran terbaik (contoh : memaksimumkan
laba, mengurangi biaya, dan lain-lain) dengan memberikan beberapa daftar kendala
(contoh : hanya bekerja 30 jam/minggu, tidak melakukan hal yang illegal, dan
lain-lain), menggunakan model matematika linier.
Contoh lainnya ada pada polytope (contoh : polygon dan polyhedral) dan
nilai riil fungsi affine
f(x1, x2, · · · , xn) = a1x1 + a2x2 + a3x3 + b
didefinisikan pada polytope, tujuannya adalah menemukan titik pada polytope
dimana fungsinya mempunyai nilai terkecil atau terbesar. Titik mungkin tidak
ada, tapi jika dicari sepanjang vertex polytope maka digaransi menemukan paling
sedikit satu darinya.
Program linier adalah problema yang dapat diekspresikan dalam bentuk
kanonik :
maximize cTx
subject to Ax ≤ b
where x ≥ 0
11
Juandi Sidabutar: Pengembangan Algoritma Pencarian Untuk Menyelesaikan Problema Program Taklinier Integer Campuran, 2008. USU e-Repository © 2008
12
x direpresentasikan vektor variabel, c dan b adalah koefisien vektor dan A
adalah koefisien matriks. Ekspresi untuk memaksimumkan atau meminimumkan
disebut fungsi objektif (cTx). Persamaan Ax ≤ b adalah fungsi kendala yang
khususnya polyhedral konvex yang fungsi objektifnya dioptimisasi.
Program linier dapat diaplikasikan untuk bermacam-macam field. Lebih
diperluas, program linier digunakan dalam situasi bisnis dan ekonomi, tetapi da-
pat juga dimanfaatkan untuk beberapa masalah teknik. Beberapa industri meng-
gunakan model program linier dalam transportasi, energi, telekomunikasi dan
manufaktur. Dan dibuktikan juga pada problema dalam perencanaan, rute, jad-
wal, tugas dan desain.
Problema dari sistem penyelesaian persamaan linier muncul setelah elimi-
nasi Fourier-Motzkin. Program linier muncul sebagai model matematika yang
dibangun selama Perang Dunia ke-II untuk merencanakan pengeluaran dan pen-
dapatan dalam mengurangi biaya untuk tentara dan meningkatkan kerugian dari
musuh. Ini tetap menjadi rahasia sampai tahun 1947. Setelah perang berakhir
banyak industri menemukan dan menggunakannya dalam perencanaan mereka.
Penemu dari program linier adalah George B. Dantzig yang memperkenalkan
metode simplex tahun 1947, John Von Neumann yang membangun teori dualitas
dan Leonid Kantorovich, matematika Rusia yang menggunakan teknik yang sama
pada bidang ekonomi sebelum Dantzig dan memenangkan penghargaan Nobel
tahun 1975 dalam bidang ekonomi.
Contoh Dantzig dalam menemukan tugas terbaik dari 70 orang pada 70
pekerjaan menunjukkan kegunaan dari program linier. Kekuatan perhitung meng-
haruskan pengujian semua permutasi untuk memilih tugas yang terbaik; jumlah
Juandi Sidabutar: Pengembangan Algoritma Pencarian Untuk Menyelesaikan Problema Program Taklinier Integer Campuran, 2008. USU e-Repository © 2008
13
konfigurasi yang mungkin melebihi jumlah partikel diseluruh bidang; kemudian
menemukan solusi optimum dengan mengajukan problem ini dan pengaplikasian
algoritma simplex.
Program linier merupakan salah satu teknik operasi riset yang digunakan
paling luas dan diketahui dengan baik. Problema khusus dari program seperti
aliran jaringan (network flow) dan aliran multicomodity dianggap cukup pen-
ting untuk dibangun dan diteliti algoritma yang khusus untuk solusinya. Ter-
dapat sejumlah algoritma untuk problema optimisasi dalam penyelesaian pro-
gram linier diantaranya adalah dualitas, dekomposisi, convexity dan generalisa-
sinya. Demikian juga program linier ini juga sangat sering digunakan dalam
microekonomi dan manajemen bisnis, yaitu memaksimumkan pendapatan atau
meminimumkan biaya dari produksi. Contoh lainnya pada manajemen perse-
diaan, portfolio, manajemen keuangan, sumberdaya manusia, dan merencanakan
iklan perusahaan.
3.1.1 Dualitas
Setiap program linier disukai sebagai problema primal, dapat dikonversi ke
dalam problema dual yang menyediakan batas atas nilai optimal dari problema
primal. Dalam bentuk matriks dapat diekspresikan sebagai berikut:
maximize cTx
subject to Ax ≤ b, x ≥ 0
Juandi Sidabutar: Pengembangan Algoritma Pencarian Untuk Menyelesaikan Problema Program Taklinier Integer Campuran, 2008. USU e-Repository © 2008
14
problema dual yang tepat adalah :
maximize bTx
subject to ATy ≥ c, y ≥ 0
dimana y digunakan sebagai pengganti variabel vektor.
Terdapat dua ide mendasar untuk teori dualitas. Salah satunya adalah dual
dari program linier dual semula adalah program linier primal. Penambahannya
adalah setiap solusi yang layak untuk program linier memberikan batas pada nilai
optimal dari fungsi objektif dualitas. Kelemahan teorema dualitas bahwa nilai
fungsi objektif dari dual pada solusi yang layak lebih baik atau sama dengan nilai
fungsi objektif dari primal untuk solusi yang layak. Teorema dualitas yang kuat
pada saat primal mempunyai solusi optimal x∗ maka dual juga mempunyai solusi
optimal y∗ sehingga cTx∗ = bTy∗.
Program linier dapat juga tidak terbatas dan tidak layak. Teori dualitas
mengatakan bahwa jika primal tidak terbatas maka dual tidak layak. Demikian
juga jika dual tidak terbatas maka primal harus tidak layak. Atau mungkin juga
untuk keduanya dual dan primal tidak layak.
3.1.2 Metode Simplex
Karena kesulitan menggambarkan grafik berdimensi banyak maka penyele-
saian masalah program linier yang melibatkan lebih dari dua variabel menjadi
tidak praktis atau tidak mungkin. Dalam keadaan ini kebutuhan metode solusi
yang lebih umum menjadi nyata. Metode umum ini dikenal dengan nama Al-
goritma Simplex yang dirancang untuk menyelesaikan seluruh masalah program
Juandi Sidabutar: Pengembangan Algoritma Pencarian Untuk Menyelesaikan Problema Program Taklinier Integer Campuran, 2008. USU e-Repository © 2008
15
linier, baik yang melibatkan dua variabel maupun lebih dua variabel.
Penyelesaian masalah program linier menggunakan metode simplex ini melalui
perhitungan ulang (iteration) dimana langkah langkah perhitungan yang sama di-
ulang berkali-kali sebelum solusi optimum dicapai.
Dalam penyelesaian masalah program linier dengan grafik, telah dinyatakan
bahwa solusi optimum selalu terletak pada titik pojok ruang solusi. Metode sim-
plex didasarkan pada gagasan ini, dengan langkah-langkah sebagai berikut:
1. Dimulai pada suatu titik pojok yang layak, biasanya titik asal (yang disebut
sebagai solusi awal).
2. Bergerak dari suatu titik pojok layak ke titik pojok yang lain yang berdekatan,
pergerakan ini akan menghasilkan nilai fungsi tujuan yang lebih baik (me-
ningkat untuk masalah maksimasi dan menurun untuk masalah minimasi).
Jika solusi yang lebih baik telah diperoleh, prosedur simplex dengan sendirinya
akan menghilangkan semua solusi-solusi lain yang kurang baik.
3. Proses ini dilakukan berulang-ulang sampai suatu solusi yang lebih baik tak
dapat ditemukan. Proses simplex kemudian berhenti dan solusi optimum
diperoleh.
Mengubah bentuk baku model program linier ke dalam bentuk tabel akan
memudahkan proses perhitungan simplex. Langkah-langkah perhitungan dalam
algoritma simplex adalah :
1. Berdasarkan pada bentuk baku, tentukan solusi awal, dengan menetapkan
(n−m) variabel nonbasis sama dengan nol. Dimana n jumlah variabel dan
Juandi Sidabutar: Pengembangan Algoritma Pencarian Untuk Menyelesaikan Problema Program Taklinier Integer Campuran, 2008. USU e-Repository © 2008
16
m banyaknya kendala.
2. Pilih sebuah entering variabel diantara yang sedang menjadi variabel non-
basis, yang jika dinaikkan di atas nol dapat memperbaiki nilai fungsi tujuan.
Jika tak ada, berhenti berarti solusi sudah optimal. Jika tidak dilanjutkan
ke langkah 1.
3. Pilih sebuah leaving variabel diantara yang sedang menjadi variabel basis
yang harus menjadi nonbasis (nilainya menjadi nol) ketika entering variabel
menjadi variabel basis.
4. Tentukan solusi yang baru dengan membuat entering variabel dan leaving
variabel menjadi nonbasis. Kembali ke langkah 2 .
3.2 Program Integer Linier
Jika variabel tak diketahui diharuskan integer maka problema ini disebut
program integer atau program linier integer. Perbedaan dengan program linier
adalah dapat diselesaikan lebih efesien pada kasus yang buruk. Problema pro-
gram integer banyak terjadi pada situasi praktis (dengan variabel terbatas) NP
hard. Program integer 0-1 adalah kasus yang khusus dari program integer dimana
variabel diharuskan 0 atau 1. Masalah ini juga diklasifikasikan sebagai masalah
yang sulit non polynomial.
Jika hanya beberapa variabel tak diketahui diharuskan integer maka pro-
blema ini disebut program integer campuran. Hal ini juga merupakan masalah
sulit non polynomial. Bagaimanapun terdapat beberapa subklas dari program in-
teger dan program integer campuran bahwa dapat diselesaikan dengan efesien,
Juandi Sidabutar: Pengembangan Algoritma Pencarian Untuk Menyelesaikan Problema Program Taklinier Integer Campuran, 2008. USU e-Repository © 2008
17
khususnya masalah di mana matriks kendalanya unimodular dan sisi sebelah
kanan dari kendala adalah integer.
Program Integer adalah bentuk dari program linier dimana asumsi divisi-
bilitasnya melemah atau hilang sama sekali. Bentuk ini muncul karena dalam
kenyataaannya tidak semua variabel keputusan dapat berupa bilangan pecahan.
Asumsi divisibilitas melemah artinya sebagian dari nilai variabel keputusan
harus berupa bilangan bulat (integer) dan sebagian lainnya boleh berupa bilangan
pecahan. Persoalan program integer dimana hanya sebagian dari variabel keputu-
sannya yang harus integer disebut sebagai persoalan Mixed Integer Programming.
Tetapi jika seluruh variabel keputusan dari suatu persoalan program linier harus
berharga integer, maka persoalan tersebut disebut sebagai persoalan Pure Integer
Programming. Dalam hal ini asumsi divisibilitas dari program linier hilang sama
sekali.
Contoh
Maksimumkan z = 8x1 + 5x2
Kendala x1 + x2 ≤ 6
9x1 + 5x2 ≤ 45
x1, x2 ≥ 0, x2 integer
Tampaknya cukup untuk mendapatkan solusi integer dari masalah program
linier dengan menggunakan metode simpleks biasa dan kemudian membulatkan
nilai-nilai pecahan solusi optimum. Hal ini bukan tugas mudah untuk membu-
latkan nilai-nilai pecahan variabel basis yang menjamin tetap memenuhi semua
Juandi Sidabutar: Pengembangan Algoritma Pencarian Untuk Menyelesaikan Problema Program Taklinier Integer Campuran, 2008. USU e-Repository © 2008
18
kendala dan tidak menyimpang cukup jauh dari solusi bulat yang tepat. Karena
itu perlu prosedur yang sistematis untuk mendapatkan solusi bulat optimum ter-
hadap masalah itu. Ada beberapa pendekatan solusi terhadap masalah program
integer yaitu salah satu diantaranya adalah pendekatan dengan cutting plane.
Dalam program linier, metode simpleks didasari oleh pengenalan bahwa pe-
mecahan optimum terjadi di titik ekstrim dari ruang solusi. Hasil yang penting
ini pada intinya mengurangi usaha pencarian pemecahan optimum dari sejum-
lah pemecahan yang tidak terbatas menjadi sejumlah yang terbatas. Sebaliknya
Program Linier Integer memulai dengan sejumlah titik pemecahan yang terbatas.
Tetapi sifat variabel yang berbentuk bilangan bulat mempersulit perancangan se-
buah algoritma yang efektif untuk mencari secara langsung di antara titik integer
yang layak dari ruang penyelesaian.
Terdapat dua metode untuk menghasilkan batasan-batasan khusus yang
akan memaksa pemecahan optimum dari masalah program linier yang dilong-
garkan untuk bergerak ke arah pemecahan integer yang diinginkan yaitu metode
Bidang Pemotong (Gomory Cutting Plane) dan metode Branch and Bound.
Algoritma lanjutan untuk menyelesaikan program linier integer adalah :
a. Metode Cutting Plane
b. Metode Branch and Bound
c. Metode Branch and Cut
d. Metode Branch and Price
Dalam penelitian ini hanya dibahas tentang metode cutting plane.
Juandi Sidabutar: Pengembangan Algoritma Pencarian Untuk Menyelesaikan Problema Program Taklinier Integer Campuran, 2008. USU e-Repository © 2008
19
Metode Gomory (Cutting Plane Algorithm)
Suatu prosedur sistematik untuk memperoleh solusi integer optimum terhadap
program integer murni pertama kali dikemukakan oleh R. E. Gomory pada tahun
1958. kemudian prosedur ini diperluas untuk menangani kasus yang lebih sulit
yaitu, mixed integer programming.
Langkah-langkah prosedur Gomory yang dilakukan sebagai berikut :
1. Selesaikan masalah program integer dengan menggunakan metode simpleks.
Jika masalahnya sederhana, dapat diselesaikan dengan pendekatan grafik,
sehingga pendekatan kurang efisien.
2. Periksa solusi optimum yang telah diperoleh. Jika variabel keputusan yang
diharapkan telah memenuhi persyaratan integer, penyelesaian optimum mixed
integer telah diperoleh dan proses penyelesaian berhenti. Jika tidak demikian
maka diteruskan ke tahap 3.
3. Buatlah suatu kendala Gomory (suatu bidang pemotong atau cutting plane)
dan cari solusi optimum melalui metode dual simpleks. Selanjutnya kembali
ke tahap 2.
Pembentukan kendala Gomory adalah begitu penting sehingga memerlukan
perhatian khusus. Misalkan tabel optimum masalah program linier yang disaji-
kan berikut merupakan solusi optimum kontinu. Secara historis, metode bidang
pemotong adalah metode pertama kali yang diperkenalkan dalam literature OR.
Oleh karena itu, maka yang disajikan dalam tulisan ini adalah bagaimana mene-
Juandi Sidabutar: Pengembangan Algoritma Pencarian Untuk Menyelesaikan Problema Program Taklinier Integer Campuran, 2008. USU e-Repository © 2008
20
mukan penyelesaian optimal yang integer dengan menggunakan algoritma bidang
pemotong.
Gagasan dari algoritma bidang pemotong adalah mengubah himpunan cem-
bung dari bidang pemecahan sehingga titik ekstrem yang sesuai menjadi semuanya
integer. Perubahan seperti ini dalam batas ruang pemecahan masih tetap meng-
hasilkan sebuah himpunan cembung. Juga perubahan ini harus dilakukan tanpa
mengiris setiap pemecahan integer yang layak dari masalah semula.
3.3 Program Taklinier
Program Taklinier adalah proses dari penyelesaian sistem persamaan dan
pertidaksamaan yang memiliki kendala. Himpunan dari variabel real yang tidak
diketahui sepanjang fungsi objektifnya memaksimumkan atau meminimumkan de-
ngan beberapa kendala atau fungsi objektif disebut nonlinier. Problema ini dapat
disederhanakan sebagai berikut ;
max /min f(x) untuk memaksimumkan atau meminimumkan fungsi objektif di-
mana f : Rm → R dan X ⊆ Rm
Jika fungsi objektif f adalah linier dan ruang kendala adalah polytope, pro-
blema ini adalah problema program linier yang dapat diselesaikan dengan meng-
gunakan solusi program linier. Jika fungsi objektif adalah konkaf/konveks dan
himpunan kendala adalah konveks maka metode yang umum dari optimisasi kon-
veks dapat digunakan.
Beberapa metode dalam penyelesaian problema non-konveks. Salah satu
pendekatannya menggunakan formula yang khusus dari problema program linier.
Juandi Sidabutar: Pengembangan Algoritma Pencarian Untuk Menyelesaikan Problema Program Taklinier Integer Campuran, 2008. USU e-Repository © 2008
21
Metode lain meliputi penggunaan teknik Branch and Bound dimana program
ini dibagi dalam subklas untuk diselesaikan dengan aproksimasi linier dari batas
bawah pada keseluruhan biaya sampai subdivisi. Dengan divisi berikut, bebe-
rapa titik solusi aktual akan diperoleh jika biaya sama atau lebih rendah dari
batas bawah terbaik. Untuk solusi aproksimasi, solusi ini optimal meskipun tidak
mungkin tunggal. Algoritma dapat berhenti cepat dengan jaminan bahwa solusi
terbaik tidak lebih dari persentase tertentu yang lebih baik dari solusi yang dite-
mukan. Hal ini khususnya berguna bagi problema yang sulit dan luas. Dengan
biaya atau nilai yang tak pasti dimana ketidakpastian tersebut dapat diestimasi
dengan estimasi kelayakan yang tepat.
3.4 Program Taklinier Integer
Program taklinier integer pada hakekatnya adalah masalah yang sulit. Metode
yang biasa untuk menyelesaikan program taklinier integer berdasarkan bermacam
rangkaian linierisasi dari problema dan beberapa variasi pada strategi Branch
and Bound. Bagaimanapun dibeberapa kasus kegunaan khusus dapat diambil
dari struktur pada problema. Problema umum dari program taklinier integer
khususnya skala luas dikenal luas sebagai persoalan yang sangat sulit dan da-
pat diselesaikan dengan membangun rangkaian solusi untuk program linier yang
beberapa pengertian aproksimasi pada program taklinier.
Duran and Grossmann (1986) mengemukakan secara detail dari algoritma
outer aproksimasi untuk menyelesaikan MINLP. Pendekatan meliputi konstruksi
dan solusi dari rangkaian bolak balik pada master problem program linier dan
sub problema pada program taklinier. Subproblema sekarang diselesaikan dengan
Juandi Sidabutar: Pengembangan Algoritma Pencarian Untuk Menyelesaikan Problema Program Taklinier Integer Campuran, 2008. USU e-Repository © 2008
22
variabel integer yang tetap dan master problema yang dibentuk dengan linierisasi
fungsi pada solusi dari subproblema.
Metode Duran dan Grossmann menggunakan prinsip dekomposisi untuk
mengeksploitasi struktur problema yang diasumsikan pada bentuk berikut : li-
nier pada variabel integer dan konveks pada porsi taklinier dari fungsi objektif
dan kendala. Bentuk umum dari klas problema berikut ditulis :
minimize cTy + f(x)
subject to g(x) = By ≤ 0
x ∈ X ⊆ Rn
y ∈ U ⊆ Rm+
fungsi taklinier f : Rn → R dan fungsi vektor g : Rn → Rp diharuskan
differensial kontinu dan konvex pada domain yang kompak. Seperti biasanya, do-
main U dari variabel integer diasumsikan pada himpunan diskrit yang berhingga.
Linieriti dari variabel diskrit membolehkan karakteristik bebas dari ruang
pencarian yang layak diskrit dan kontinu dari problema. Ruang kontinu dieks-
presikan sebagai irisan daerah konvex kompak dan berhingga, tiap-tiapnya di-
parametrik dengan nilai dari variabel diskrit. Outer Approksimasi dari himpunan
konveks dengan irisan dari ruang bagian yang mendukung yang digunakan untuk
mendefinisikan master program linier integer-campuran. Penulis membandingkan
metode mereka dengan metode dekomposisi Benders yang tergeneralisasi dan se-
bagai catatan kedua teknik ini cenderung menghasilkan batas bawah lebih baik
pada nilai optimal fungsi objektif.
Juandi Sidabutar: Pengembangan Algoritma Pencarian Untuk Menyelesaikan Problema Program Taklinier Integer Campuran, 2008. USU e-Repository © 2008
23
Sebelumnya hasil yang diperoleh Duran and Grossmann memperlihatkan
janji pada metodenya, dimana penulis mengindikasikan akan cocok pada masalah
dalam subproblema program taklinier yang sulit untuk diselesaikan.
Beberapa hasil dari Mawengkang and Murtagh (1985/6) telah memberikan
hasil untuk membuat bentuk umum dan sering digunakan pada kelas program tak
linier dimana proporsi dari variabel integer dan variabel taklinier keduanya kecil.
Mawengkang and Murtagh (1985), mengajukan penyelesaian program taklinier
integer dengan software optimisasi yang skala luas menggunakan MINOS. Teknik
ini dipresentasikan untuk memperluas pencarian kendala untuk menyelidiki solusi
integer yang layak sehingga solusi optimal kontinu diperoleh. Perhitungan meng-
gunakan pendekatan ini digambarkan untuk dua klas problema yaitu problema
kuadratik dan desain jaringan problema.
Secara umum, kebanyakan tujuan dari penelitian pemograman matematika
adalah untuk membentuk teori yang mengacu pembuatan algoritma untuk digu-
nakan secara modern, komputasi digital kecepatan tinggi. Metode survei yang
baik digunakan untuk menyelesaikan masalah Program taklinier dapat ditemukan
dan digolongkan kedalam katagori-katagori berikut:
1. Teknik Linierisasi
2. Pendekatan Branch and Bound
3. Teknik Enumerasi Implisit
4. Pendekatan Program Dinamik
5. Metode-Metode Lainnya
Juandi Sidabutar: Pengembangan Algoritma Pencarian Untuk Menyelesaikan Problema Program Taklinier Integer Campuran, 2008. USU e-Repository © 2008
24
3.4.1 Teknik Linieritas
Pertimbangan problema NLIP dimana J ′ = J dan anggap fungsi objektif F
dan fungsi kendala f adalah polinomial. Teknik linierisasi secara luas digunakan
untuk problema-problema seperti ini. Semua dasar untuk masalah non biner,
teknik seperti ini terdiri dari dua langkah transformasi. Langkah pertama adalah
dengan mengubah formulasi non biner menjadi formulasi biner atau formula 0-1.
Dengan kata lain, variabel integer x digantikan oleh biner y. Asumsikan bahwa
masing-masing xj memiliki batas atas terhingga yaitu uj, persamaan untuk x
dapat ditulis sebagai :
xj =
tj∑
i=0
2iyij
yij = 0, 1 i = 0, . . . , tj
(3.1)
Dimana tj adalah integer positif terkecil, u ≤ 2tj+1 − 1.
Langkah kedua adalah mereduksi program polinomial 0-1 ke program li-
nier 0-1 dengan memperkenalkan variabel 0-1 yang baru untuk menggantikan
bagian-bagian cross product. Dimana bentuk yn (dimana y = 0 atau 1) dapat
disederhanakan menjadi y.
Ambil Q sebagai variabel himpunan 0-1, kemudian setiap perbedaan hasil
Πj∈Qyj dari variabel 0-1 akan digantikan dengan variabel 0-1 yang baru yaitu yQ.
Untuk membuktikan yQ = 1 jika dan hanya jika Πj∈Qyj = 1, kita mengambil dua
bentuk kendala baru
−∑
j∈Q
yj + yq + q − 1 ≥ 0 (3.2)
Juandi Sidabutar: Pengembangan Algoritma Pencarian Untuk Menyelesaikan Problema Program Taklinier Integer Campuran, 2008. USU e-Repository © 2008
25
dan
−∑
j∈Q
yj − qyQ ≥ 0 (3.3)
yQ = 0 atau 1 (3.4)
dimana q jumlah elemen pada Q.
Masalah kelinieran dapat disederhanakan dengan menggunakan beberapa
anggota standart, seperti algoritma Balas.
Bagaimanapun, program linier 0-1 yang baru di formulasikan pada harga
yang signifikan. Untuk setiap bagian cross product, sebuah variabel biner harus
ditambahkan dua pembuktian. Dimana harga variabel dan bukti akan naik secara
merata untuk program nonlinier 0-1 yang kecil.
Hasil Linierisasi Alternatif yang linier 0-1, program polynomial telah diusulkan
oleh Glover dan Woolsey (1973,1974), di dalam suatu usaha untuk memperluas
cakupan permasalahan nonlinier di mana pendekatan linier yang diubah terbukti
efektif. Karena kesukaran memprogram permasalahan bilangan bulat (dan mixed-
integer) sering dipertahankan pada banyaknya bilangan bulat variabel, mereka
menggantikan polynomial terminologi perkalian oleh kontinu variabel yQ ∈ [0, 1]
sebagai ganti 0-1 variabel. Batasannya
Yj ≥ yq, ∀j ∈ Q (3.5)
ditambahkan untuk membuktikan (3.3)
Bentuk (3.5) menentukan harga 0 sampai yQ dimana yj = 0 untuk semua
j ∈ Q, dan dari (3.2), yQ = 1 untuk semua j ∈ Q.
Juandi Sidabutar: Pengembangan Algoritma Pencarian Untuk Menyelesaikan Problema Program Taklinier Integer Campuran, 2008. USU e-Repository © 2008
26
Bagaimanapun, dalam kaitan dengan (3.5), banyaknya batasan akan me-
ningkat secara drastis, walaupun variabel yang biner akan tinggal yang sama
dalam jumlah. Dalam rangka mengalahkan situasi ini, mereka mempunyai petun-
juk lebih lanjut bahwa mungkin untuk memberi masing-masing yQ status suatu
variabel kontinu di dalam suatu pertunjukan economical lebih jauh.
MisalkanKj menandakan satuan himpunan berisi yj, dan misalkan nj menan-
dakan banyaknya unsur-unsur di Kj, kemudian batasan format
Njyj ≥∑
Q∈Kj
yQ (3.6)
mungkin mengganti persamaan (3.3). Adalah mudah untuk menunjukkan bahwa
persamaan (3.6) akan memberi lebih sedikit batasan dibanding persamaan (3.3).
Glover (1975) mempunyai prosedur diberi lebih lanjut untuk mengurangi
banyaknya batasan dan variabel baru yang diperkenalkan untuk mengakomodasi
cross product. Ia telah menunjukkan variabel kontinu tunggal wj boleh meng-
gantikan satu himpunan kwadrat xi
n∑j=1
cijxj di mana xi = 0 atau 1, untuk semua
i ∈ N = 1, . . . , n. Oleh karena itu, batasan
Dixi ≥ wi ≥ D¯ ixi (3.7)
dan∑
j
dijxj − D¯ i(1 − xj) ≥ wi ≥
∑
j
dijxj − Di(1 − xj) (3.8)
dimana
D¯ i
n∑
j=1
min(dij, 0)
dan
Di
n∑
j=1
max(dij , 0)
Juandi Sidabutar: Pengembangan Algoritma Pencarian Untuk Menyelesaikan Problema Program Taklinier Integer Campuran, 2008. USU e-Repository © 2008
27
ditentukan bahwa
wi jika xi = 0
dan
wi =∑
dijxj jika xi = 1
Ini adalah suatu peningkatan luas bandingkan dengan Teknik Watters, ketika
kita dapat mengamati bahwa hanya n variabel kontinu baru dan 4n batasan tam-
bahan akan ditambahkan jika teknik ini telah diberlakukan bagi suatu standard
program bilangan bulat kwadrat. Bagaimanapun, lebih kecil, seperti perumusan
secara khas menyediakan relaksasi berlanjut agak lemah dan pemusatan adalah
lambat (Mcbride Dan Yormark, 1980a,b).
Fungsi multilinier hanya menyatakan ulang nilai dari fungsi g(x) dalam
variabel 0 dan 1. Secara aljabar, fungsi multilinier f(x) dapat ditulis dalam
bentuk :
G(x) =∑
t∈N
atΠj∈Ntxj, xj = 0 atau 1, j ∈ N (3.9)
dimana at, t ∈ N adalah bilangan real dan Π adalah symbol perkalian. Oleh
karena itu program nonlinier 0 dan 1 melibatkan fungsi dengan bilangan real
yang dapat dinyatakan dalam bentuk multilinier yaitu :
minF (x)|fi(x) ≤ 0, i ∈ K,x biner (3.10)
dimana F dan f adalah fungsi multilinier.
Linearisasi program multilinier tidak membutuhkan variabel baru (Granot
dan Hammer, 1971). Pada awalnya disebut generalized covering problem yang
Juandi Sidabutar: Pengembangan Algoritma Pencarian Untuk Menyelesaikan Problema Program Taklinier Integer Campuran, 2008. USU e-Repository © 2008
28
dapat ditulis dalam bentuk berikut:
Minimize cT x (3.11)
Subject to Axα ≥ 1 (3.12)
0 ≤ x ≤ 1, dan integer (3.13)
dimana A adalah matriks 0-1, x = (1 − x) adalah vektor 0-1 dan xα ≡ (xαjj )
sehingga:
xj =
xαjj if αj = 1
xj if αj = 0
Sebagai alternatif, Granot dan Granot (1980) menggunakan teknik liniearisasi
yang sama, tetapi pada setiap tahap algoritma menyelesaikan problema covering
linier sehingga relaksasi dari problema tersebut kendala yang memiliki subset yang
kecil dari kendala pada problema covering yang sama. Tujuan utama algoritma ini
adalah dapat diatur untuk mencegah produksi kendala covering yang berlebihan.
Yang baru-baru ini, Balas dan Mazzola (1984a,b) sudah memperkenalkan su-
atu linierisasi MLP baru bagi suatu padanan yang dihimpun mencakup masalah,
gunakanlah hanya variabel yang asli, terutama sekali untuk suatu multilinier un-
tuk format
G(x) =∑
i∈N
at
∏
j∈Nt
xj ≤ b, xj = 0 atau j ∈ Nt (3.14)
Mereka menggambarkan suatu famili dari ketidaksamaan linier setara de-
ngan persamaan (3.9) itu berisi linierisasi yang lebih ringkas (atau lebih kecil
jumlah mencakup batasan) tentang yang MLP dibanding yang didasarkan pada
disamaratakan mencakup ketidaksamaan. Perhitungan mengalami regenerasi se-
cara acak menghasilkan multilinier 0-1 program dengan 20 batasan dan 50 variabel
Juandi Sidabutar: Pengembangan Algoritma Pencarian Untuk Menyelesaikan Problema Program Taklinier Integer Campuran, 2008. USU e-Repository © 2008
29
diperkenalkan. Aplikasi ini mendekati ke permasalahan lebih besar memerlukan
penyelidikan lebih lanjut.
3.4.2 Pendekatan Branch and Bound
Branch and Bound untuk memecahkan pemrograman liniar bilangan bulat
(ILP) telah dikembangkan melalui Land dan Doing (1960). Metode, yang secara
langsung dihubungkan dengan simpleks metode untuk pemograman linier (LP),
kemudian dimodifikasi oleh Dakin (1965) dan telah dengan sukses menerapkan
di dalam kitab undang-undang hukum dagang banyak orang untuk memecahkan
permasalahan ILP.
Prinsip metode itu sendiri sungguh sederhana, tetapi meskipun demikian
alat yang sangat bermanfaat untuk memecahkan permasalahan terpisah. Ketika
dipertimbangkan dalam konteks lebih luas, secara teoritis, Branch and Bound
mungkin digunakan untuk memecahkan masalah optimisasi manapun. Efisiensi
algoritma jenis ini sebagian besar tergantung pada detil itu, terutama pada kalku-
lasi Bound bagian atas dan yang lebih rendah, pada separasi menetapkan dan,
akhirnya, pada aturan pilihan yang berbeda menggunakan untuk menentukan
solusi yang berikutnya mulai dipertimbangkan dan variabel yang berikutnya ke
Branch terpasang. Gagasan yang umum digunakan untuk metode untuk ILP
dapat diuraikan sebagai berikut. Pertimbangkan suatu masalah ILP.
maxF (x) = cTx (3.15)
Juandi Sidabutar: Pengembangan Algoritma Pencarian Untuk Menyelesaikan Problema Program Taklinier Integer Campuran, 2008. USU e-Repository © 2008
30
berlaku hanya jika :
Ax = b (3.16)
l ≤ x ≤ u (3.17)
xj integer j ∈ J ′ ⊂ J
DimanaA adalah matrikm×n, cT adalah transpos dari c dan c adalah vektor
n×1, dan J = (1, 2, . . . , n). Proses dari metode awal dengan menyelesaikan (3.15)
(3.17) program linier secara kontinu, abaikan syarat-syarat integral. Andaikan
solusi xj, j ∈ J , tidak semua integer.
xj = [xj] + fj , 0 ≤ fj ≤ 1
untuk beberapa j ∈ J
(3.18)
dimana [xj] adalah komponen integer dari xj, solusi kontinu untuk program linier,
dan fj adalah komponen bagian yang kecil.
Gagasan untuk menghasilkan dua subproblem masing-masing dengan pe-
nambahan pembuktian
Lj ≤ xj ≤ [xj] (3.19)
dan
[xj] + 1 ≤ xj ≤ uj (3.20)
Karena variabel tertentu j ∈ J . Proses menyelesaikan masalah disebut
Branching. Masing-masing ini subproblema dipecahkan lagi sebagai LP kontinu.
Proses dari Branching dan pemecahan suatu sequance dari permasalahan kon-
tinu untuk variabel yang berbeda j ∈ J ′ dan bilangan bulat yang berbeda bxjc.
Secepatnya, kita menyediakan daftar alternatif subproblema untuk diselidiki, de-
ngan LP yang kontinu yang pertama dimasukkan.
Juandi Sidabutar: Pengembangan Algoritma Pencarian Untuk Menyelesaikan Problema Program Taklinier Integer Campuran, 2008. USU e-Repository © 2008
31
Struktur metode yang logis sering diwakili sebagai pohon. Masing-masing
tangkai pohon menghadirkan suatu subproblem. Ketika subproblema manapun,
atau tangkai pohon, diselidiki subproblema manapun yang dihasilkan dihubungkan
kepada tangkai pohon dengan Branch.
Jika salah satu dari tiga ukuran-ukuran di bawah ini dicukupi, Branch dari
tiap tangkai pohon akan berakhir.
1. Subproblema tidak mempunyai solusi fisibel
2. Solusi subproblema tidak ada lebih baik daripada integer-fisibel solusi ter-
baik yang dikenal sekarang.
3. Solusi adalah integer-fisibel, i.e.,xj, j ∈ J ′ mempunyai nilai-nilai bilangan
bulat (menyediakan suatu integer-fisibel, solusi ada). Itu adalah jelas, bahwa
efektivitas dari prosedur seperti itu adalah sangat dependen.
4. Variabel yang mana harus bercabang, dan
5. Subproblema yang mana harus diselidiki berikutnya.
Sebab perhatian kita sebagian besar pada atas permasalahan NLIP, itu
bermanfaat untuk melihat bagaimana di atas pendekatan mungkin sesuai dik-
erjakan seperti permasalahan itu.
Secara teoritis, pendekatan Branch dan Bound tidak mempunyai berbagai
kesulitan untuk memecahkan permasalahan NLIP. Khususnya, akan mudah untuk
mengamati bahwa batas (3.19) dan (3.20) menjauhi linieritas.
Juandi Sidabutar: Pengembangan Algoritma Pencarian Untuk Menyelesaikan Problema Program Taklinier Integer Campuran, 2008. USU e-Repository © 2008
32
Pendekatan yang umum ditujukan di atas untuk ILP dapat secara langsung
diperluas kepada kasus nonlinier, kecuali prosedur untuk memecahkan subprolem
dan masing-masing tangkai pohon. Itu dipahami bahwa permasalahan yang kon-
tinu pada tangkai pohon masing-masing adalah nonlinier yang memprogram per-
masalahan (NLP), yang dihasilkan dengan kebutuhan integralisasi suatu masalah
NLIP. Berbagai kesulitan boleh muncul dalam posisi ini, ketika kita sadar yang
memecahkan suatu masalah NLP tidaklah sangat mudah untuk memecahkan LP,
terutama sekali, dalam menemukan solusi optimal yang global. Oleh karena itu
menghitung kelayakan dari pendekatan ini akan tergantung pada bagaimana kita
memecahkan masalah NLP itu, dengan batasan Bound tambahan (3.19) atau
(3.20) pada tangkai pohon masing-masing.
Bagaimanapun, metode Branch dan Bound mempunyai fleksibilitas untuk
berhubungan dengan suatu variasi yang besar masalah nonlinier, metode yang
ada disediakan untuk memecahkan kontinu nonlinier subproblem yang efesien.
Oleh karena itu tidaklah mengejutkan bahwa banyak peneliti sudah menggunakan
pendekatan ini untuk memecahkan beberapa permasalahan NLIP.
Seperti ditunjukkan di atas suatu pemilihan yang baik variabel Branch,
seperti halnya, subproblem untuk diselidiki berikutnya, akan mempunyai efek
penting pada keseluruhan capaian suatu strategi Branch dan Bound. Gupta dan
Ravindran (1985) sudah menyelidiki strategi yang berikut untuk pemilihan varia-
bel Branch.
1. Variabel bilangan bulat dengan index paling rendah.
2. Kebanyakan variabel bilangan bulat pecahan
Juandi Sidabutar: Pengembangan Algoritma Pencarian Untuk Menyelesaikan Problema Program Taklinier Integer Campuran, 2008. USU e-Repository © 2008
33
3. Penggunaan Pseudo-Cost Konsep Benichou et al. ( 1971). Konsep ini adalah
untuk mengukur rata-rata dari yang diamati ternyata berubah di (dalam)
nilai fungsi objektif dalam kaitannya dengan memaksa suatu non-integer
bagi suatu nilai bilangan bulat. Pilih pseudo-cost yang paling besar.
Mereka sudah menggunakan yang berikut ini untuk pemilihan dari Branch
tangkai pohon:
1. Branch dari tangkai pohon dengan yang terikat paling rendah.
2. Branch dari tangkai pohon yang paling baru.
3. Menggunakan estimasi - estimasi.
Dalam kaitan dengan waktu perhitungan, mereka menyimpulkan bahwa
strategi menggunakan variabel bilangan bulat yang paling kecil adalah yang ter-
baik diantara tiga pilihan untuk memilih variabel yang ber Branch itu. Dan
Branch dari tangkai pohon yang paling baru adalah yang strategi terburuk untuk
memilih tangkai pohon untuk diselidiki berikutnya. Korner (1983) telah mengu-
sulkan aturan Branch lain untuk bilangan bulat yang tidak dibatasi masalah opti-
misasi kuadrat, yaitu ke variabel Branch xj yang pertama jika (Q−1)jj ∈ (Q−1)ii
untuk semua i. Di mana Q adalah matriks simetrik yang positif dan fungsi ob-
jektif yang terbatas. Berrada dan Stecke (1986) menggunakan Branch dan Bound
untuk memecahkan mesin yang memuat masalah dalam fleksibel sistem produksi.
Juandi Sidabutar: Pengembangan Algoritma Pencarian Untuk Menyelesaikan Problema Program Taklinier Integer Campuran, 2008. USU e-Repository © 2008
34
3.4.3 Teknik Enumerasi Implisit
Walaupun ruang solusi programming masalah bilangan bulat mungkin besar,
itu adalah terbatas. Suatu metode secara langsung untuk memecahkan seperti
masalah itu untuk menyebut satu persatu semua poin-poin dengan tegas. Oleh
karena itu, solusi yang optimal ditentukan oleh point(s) itu menghasilkan nilai
fungsi sasaran yang terbaik.
Bagaimanapun, dengan penggunaan teknik di atas, banyaknya solusi poin-
poin boleh menjadi tidak praktis, sebagai konsekuensi jumlah waktu penghitu-
ngan akan menjadi penghalang. Gagasan untuk implisit penyebutan satu per
satu meminta pertimbangan hanya sebagian dari semua menunjuk kemungkinan
pemecahan, secara otomatis sisanya yang bukan peluang dibuang.
Dengan jelas, ide untuk teknik penyebutan satu per satu yang terkandung
adalah serupa pada gambaran metode Branch dan Bound yang bagian sebelum-
nya. Pada pokoknya, penyebutan satu per satu mengandung suatu metode Branch
dan Bound yang dirancang terutama untuk kasus di mana x diperlukan untuk
menjadi garis vektor biner.
Pertimbangkan permasalahan program nonlinear 0-1 kendala batasan akan
bersifat jelas bahwa nilai dari suatu bilangan bulat [xj] selalu nol, untuk semua
j ∈ J . Sebagai konsekuensi, tambahan kendala (3.19) dan (3.20) akan digantikan
oleh penentuan batas.
xj = 0 (3.21)
dan
xj = 1 (3.22)
Juandi Sidabutar: Pengembangan Algoritma Pencarian Untuk Menyelesaikan Problema Program Taklinier Integer Campuran, 2008. USU e-Repository © 2008
35
masing-masing untuk j ∈ J ′
Itu telah jelas bahwa separasi suatu tangkai pohon dilaksanakan dengan
perbaikan tertentu (bebas atau belum dipilih) variabel j ∈ J nol atau kemu-
dian pemecahan masalah yang kontinu. Ukuran-ukuran untuk mengakhiri proses
Branch sama seperti di metode Branch dan Bound.
Penting untuk mempunyai strategi Branch agar supaya menyebut satu per-
satu secara efesien. Ada beberapa aturan Branch yang telah diusulkan. Karena
polynomial tidak dibatasi program 0-1, Hammer (1971) dan Hammer dan Peled
(1972) sudah memilih suatu istilah ct∏
j∈Nt
xj dengan suatu koefisien hal negatif dan
Branch menurut semua xj = 1 untuk j ∈ N atau sedikitnya satu seperti xj = 0.
Proposal lain datang dari Jeroslow (1973), siapa yang memilih sepasang variabel
cuma-cuma xj dan xk dan merobek masalah menurut xj = xk atau xj = 1 − xk,
atau menurut Branch xj ≤ xk atau xj = 1 dan xk = 0. Mcbride dan Yorkmark
(1980a, 1980b) sudah menggunakan konsepsi pseudo-cost pada Benichou et al
(1971) untuk mengevaluasi aturan Branch itu. Variabel yang kecil dengan nilai
pseudo-cost yang besar terpilih untuk Branch. Jika pseudo-cost yang paling besar
dihubungkan dengan pengaturan beberapa variabel ke satu (nol) di dalam proses
Branch mereka akan menetapkan variabel ini ke nol (satu).
Aturan yang paling umum adalah untuk memilih beberapa variabel cuma-
cuma xj, setelah mempertimbangkan derajat tingkat infeasibilitas dan untuk
menyekat menurut xj = 1 atau xj = 0.
Di samping aturan Branch, ada beberapa test untuk dipertimbangkan dalam
rangka mengurangi penyebutan satu per satu. Test ini sering digunakan untuk
memeriksa apakah solusi suatu subproblem telah mencukupi masing-masing dari
Juandi Sidabutar: Pengembangan Algoritma Pencarian Untuk Menyelesaikan Problema Program Taklinier Integer Campuran, 2008. USU e-Repository © 2008
36
akhir ukuran-ukuran, itu harus dipisahkan. Test ini mempunyai banyak versi,
telah dikembangkan oleh beberapa pengarang, seperti, Garfinkel dan Nemhauser
(1972), Laughhunn (1970), Hansen (1972,1979), Taha (1975) dan Salkin (1975).
Suatu penalti P 0j dan P 1
j adalah suatu kenaikan yang mungkin ditambahkan
untuk suatu Bound ketika suatu variabel xj harus mengambil nilai 0 atau 1.
Penalty sering digunakan di dalam test yang bersyarat digunakan dalam algoritma
untuk memperoleh batas lebih ketat atau untuk menunjukkan beberapa varia-
bel harus ditetapkan, diperbaiki. Hansen (1972), dalam memecahkan kwadrat
0-1 memprogram permasalahan, telah mengembangkan apa yang ia terminologi
”penalty aditip”, jika penalty P 0j dan P 1
j , berhubungan dengan perasaan men-
dalam beberapa variabel pada 0 dan beberapa variabel pada 1, mungkin bila di-
jumlahkan, hasil suatu penalty baru sah. Penalty ini adalah terikat ketika koefisien
objektif dan batasan berfungsi. While Mcbride Dan Yorkmark (1980a,1980b) su-
dah menggunakan Tomlin-Style penalty yang digunakan dalam masalah ILP.
Kendati usaha dari banyak peneliti, sejauh ini, untuk memperoleh strategi
mengurangi penyebutan satu per satu (atau proses Branch), satu rangkaian non-
linear berlanjut ke permasalahan dan masih tetap dijadikan pemecahan pada
tangkai pohon masing-masing. Sungguhpun suatu metode mungkin hadir untuk
memecahkan permasalahan yang berlanjut, dari segi pandangan keseluruhan ca-
paian, pendekatan seperti itu masih menjadi penghalang dalam kaitan dengan
menghitung waktu, karena nyaris mempermasalahkan ukuran sederhana.
Juandi Sidabutar: Pengembangan Algoritma Pencarian Untuk Menyelesaikan Problema Program Taklinier Integer Campuran, 2008. USU e-Repository © 2008
37
3.4.4 Pendekatan Program Dinamik
Pendekatan program yang dinamik telah digunakan oleh banyak peneliti
terutama sekali dalam memecahkan permasalahan QIP dengan fungsi objektif
yang dapat dipisah-pisah dan menghambat, seperti, Weinstein dan Yu (1973),
Mitten (1964), Morrin (1978), Morin Dan Marsten (1976), Cooper (1980,1981)
Cooper dan Cooper (1975,1981), Cooper dan Farhagian (1982). Ini tidaklah
mengejutkan sebab keuntungan menggunakan pendekatan seperti itu menghasilkan
suatu jumlah maksimum global dibandingkan dengan optima lokal.
Teori program dinamik dikenalkan oleh Bellman (1957), dirancang untuk
menguraikan langkah-langkah dan masalah keputusan besar ke dalam suatu uru-
tan langkah tunggal yang permasalahan secara berulang dioptimalkan. Pen-
dekatan seperti itu ditemukan untuk dapat secara efektif memecahkan suatu kelas
QIP tertentu jika masalah membuat prinsip optimal oleh Bellman (1957) seperti
halnya separabiliti sasaran berfungsi. Mitten (1984) telah menambahkan pro-
perti monotonik kepada fungsi objektif sebagai syarat cukup suatu kondisi, contoh
fungsi objektif harus monoton yang tidak menurun untuk masalah diperkecil.
Mempertimbangkan masalah QIP dengan suatu fungsi objektif yang tidak
terpisah dan tidak menurun dapat ditulis seperti:
maximize F (x) =n∑
j=1
Fj(xj) (3.23)
subject to fi(x) ≤ 0, i ∈ K (3.24)
l ≤ x ≤ u (3.25)
xj integer j ∈ J
Juandi Sidabutar: Pengembangan Algoritma Pencarian Untuk Menyelesaikan Problema Program Taklinier Integer Campuran, 2008. USU e-Repository © 2008
38
Asumsi bahwa fungsi Fj mencukupi kondisi-kondisi tersebut seperti di atas
dan daerah yang mungkin terikat dan berisi sedikitnya satu bilangan bulat.
Prosedur untuk memecahkan masalah (3.23)-(3.25) oleh Cooper dan Cooper (1975),
dan Cooper (1980) akan diuraikan sebagai berikut.
1. Hitung batas atas F =∑n
j = 1Fj(uj)
2. Ditemukan semua kombinasi xj, j ∈ J , dengan pemecahan
maximize F (x) =n∑
j=1
Fj(xj) (3.26)
subject ton∑
j=1
Fj(xj) = F − k = Fk, k = 0, 1, . . . (3.27)
l ≤ x ≤ u (3.28)
xj integer j ∈ J
3. Apakah uji kelayakan titik bilangan bulat menemukan dua langkah (bila
ada) dengan batasan (3.24) dan (3.25). Jika sedikitnya satu titik bilangan
bulat mungkin ditemukan dapat menjadi suatu solusi optimal dan. Jika
tidak lanjut ke langkah 4.
4. k meningkat oleh 1, yaitu Fk berkurang oleh 1 dan kembali ke langkah 2.
Dari langkah 3, adalah jelas nyata bahwa batasan (3.24) digunakan hanya
untuk uji kelayakan calon suatu solusi. Ini akan menjadi suatu keuntungan poten-
sial diatas metode lain dimana sifat alami batasan menjadi beberapa arti penting.
Teknik Programming yang dinamis digunakan untuk memecahkan persamaan
(3.26)-(3.28) untuk xj pada langkah 2, sebagai F (x), Bellman membuat prinsip
optimal. Oleh karena itu, bergantung efisiensi pada langkah 2.
Juandi Sidabutar: Pengembangan Algoritma Pencarian Untuk Menyelesaikan Problema Program Taklinier Integer Campuran, 2008. USU e-Repository © 2008
39
Bagaimanapun, itu sangat mudah dimengerti, berbagai kesulitan mengenai
pemograman dinamis adalah bahwa mengalikan masalah batasan untuk menga-
likan tabel dimensi untuk program fungsi yang dinamis. Sebagai penyimpanan
komputer konsekwensi dan beban perhitungan solusi menjadi berlebihan bahkan
untuk permasalahan dengan ukuran moderat.
Dalam rangka mengurangi berbagai kesulitan perhitungan dan permasala-
han penyimpanan berlebihan, Aust (1976) telah mengkombinasikan pendekatan
diatas pendekatan dengan metode Branch dan Bound untuk memecahkan per-
masalahan QIP yang terpisah. Suatu batasan masalah disekat ke dalam banyak
subproblem dengan variabel yang sama. Subproblem dibagi menjadi relaksasi
lebih lanjut. Proses Branch dan Bound dikerjakan untuk meningkatkan kondisi
kelayakan secara sekuen. Denardo dan Fox (1979) juga telah menyelidiki ke-
layakan kombinasi teknik Branch dan Bound dengan program dinamis.
3.4.5 Metode Dekomposisi Benders
Metode partisi Benders yang dibangun oleh Geoffrion (1972) menawarkan
strategi pengaturan yang luas untuk problema program integer campuran. Vector
y dianggap vector yang rumit, dalam pengertian jika y sementara merupakan
problema yang tetap dan mudah untuk diselesaikan.
Secara singkat, pendekatan Dekomposisi Benders untuk MINLP dapat digam-
barkan sebagai berikut:
Langkah pertama adalah menetapkan y = y ∈ Y pada problema (P ), subprob-
Juandi Sidabutar: Pengembangan Algoritma Pencarian Untuk Menyelesaikan Problema Program Taklinier Integer Campuran, 2008. USU e-Repository © 2008
40
lema (P (y)) diperoleh :
Minimizex∈X
F (x, y)(P (y))
subject to f(x, y) = 0
Subproblema (P (y)) adalah problema NLP pada x jika nonlinier dari pro-
blema (P ) muncul dalam x dan y secara bersama atau hanya dalam x.
Diasumsikan bahwa F dan f adalah konveks pada himpunan X yang tidak
kosong untuk y yang tetap, dan subproblema (P (y)) mempunyai solusi yang
berhingga dan memiliki vektor perkalian yang optimal. Sehinggga nilai (P (y))
sama dengan dual dari Y , yaitu (Geoffrion, 1972 dan Hoang, 1982) :
Maximum [Minimumx∈X
F (x, y) − uf(x, y)],∀y ∈ Y (3.29)
dimana u adalah vektor dari variabel dual.
Aplikasi subproblema (P (y)) dan dualnya pers (3.21) pada problema (P )
menghasilkan master problema yang sama.
Minimumx∈X,Θ
Θ (3.30)
subject to Θ ≥ Minimumx∈X
[F (x, y)− uf(x, y)],∀u
Bagaimanapun, master problema ini merupakan teori yang menarik karena
dibangun oleh kendala yang banyak. Tetapi dapat diselesaikan secara iterasi de-
ngan menggunakan proses relaksasi sehingga banyaknya kendala bukan meru-
pakan suatu masalah. Andaikan (y∗, θ∗) optimal pada relaksasi dari master pro-
blema. Untuk solusi yang layak pada master problema, sub problema (P (y∗))
kemudian diselesaikan (disediakan (P (y∗)) mempunyai solusi yang layak dan ter-
batas). Solusi (y∗, θ∗) mengacu pada pers (3.30) jika dan hanya jika y∗ ≤ (P (y)).
Juandi Sidabutar: Pengembangan Algoritma Pencarian Untuk Menyelesaikan Problema Program Taklinier Integer Campuran, 2008. USU e-Repository © 2008
41
Sehingga (P (y)) merupakan rata-rata untuk menguji (y∗θ∗) layak pada master
problema. Dalam pengertian (y∗θ∗) tidak layak pada subproblema (P (y∗)) akan
menghasilkan kendala pengganggu sehingga vektor perkalian optimal u∗ yaitu :
Θ∗ < Minimumx∈X
[F (x, y∗) − u∗f(x, y∗)] (3.31)
Pers (3.31) membangun dan menambahkan relaksasi problema melebihi kendala
pengganggu dan menyelesaikannya. Proses ini diulangi sampai solusi relaksasi
problema tercapai untuk semua kendala yang ada.
Jika semua variabel integer adalah linier pada fungsi objektif dan kendala
pada problema (P ) maka master problemanya adalah problema ILP. Kesulitannya
jika beberapa variabel integer tidak linier pada fungsi objektif dan kendala dari
problema (P ). Untuk memcahkan kesulitan ini, Lazimy (1982,1984) mengem-
bangkan formulasi yang sama pada problema asli dengan menggunakan konsep
invers yang digeneralisasi. Pada formulasi baru, variabel integer tidak ada pada
fungsi objektif dan kendala adalah linier. Akibatnya kendala pers (3.30) pada
master problema akan linier dalam variabel integer y.
Karena kemampuan partisi probelma program integer campuran, metode
Dekomposisi Benders memungkinkan peneliti memecahkan beberapa problema
dunia nyata yang dapat diformulasi sebagai problema MINLP. Sebagai contoh,
problema penjadwalan unit pembangunan terminal (Turgeon,1978), problema
pembangunan rencana pada listrik (Noonan dan Giglio, 1977), problema rute
kendaraan (Sexton dan Bodin, 1985), pada problema tugas kuadratik (Bazaraa
dan Sherali, 1980) dan problema sumber rencana kekuatan reaktif (Rouhani et
al, 1985).
Juandi Sidabutar: Pengembangan Algoritma Pencarian Untuk Menyelesaikan Problema Program Taklinier Integer Campuran, 2008. USU e-Repository © 2008
42
3.4.6 Metode-metode Lainnya
Lawler dan Bell (1966) memberi suatu solusi teknik leksikografik untuk yang
non linier 0-1 permasalahan program. Asumsi dasar metode ini adalah bahwa,
suatu masalah minimalisasi, fungsi sasaran harus datar yang tidak menurun dan
fungsi yang mengartikan left-hand sisi batasan yang dibangun seperti perbedaan
antara dua bagian yang monoton.
Algoritma mereka adalah suatu metode enumerasi parsial. Walaupun ba-
nyaknya batasan tidaklah terlalu penting, adalah perlu bahwa banyaknya 0-1
variabel kecil dan oleh karena itu ini membatasi aplikasi. seperti algoritma ke
permasalahan ukuran yang agak kecil. Mao dan Wallingford (1969) memperluas
pendekatan mereka untuk menangani suatu masalah kwadrat, di mana fungsi ob-
jektif tidaklah perlu monoton tetapi dapat diwakili sebagai perbedaan dua fungsi
yang tidak menurun.
Pendekatan fungsi penalty telah dipertimbangkan di (Gisvold dan Moe,
1972) untuk memecahkan program mixed-integer nonlinear di dalam permasala-
han disain. Yang biasanya, gagasan untuk mengubah bentuk masalah dalam
suatu urutan dari permasalahan tidak terbatas dapat tertulis seperti:
minimize Pk(x) = F (x) + λk
∑
i∈K
1
fi(k)+ ρk
∑
j∈J ′
4qj(1 − qj)βk (3.32)
Di mana qj = xj − [xj] ∀j ∈ J ′ dan βk ≥ 1, dan konstanta λk, ρk dan βk dihimpun
berdasarkan prioritas untuk masing-masing k.
Bagaimanapun, algoritma di atas mempunyai beberapa kelemahan. Yang
pertama-tama, mungkin adakalanya sukar untuk menghasilkan suatu titik awal.
Yang yang kedua, yang diperlukan jumlah fungsi evaluasi boleh jadi sangat besar
Juandi Sidabutar: Pengembangan Algoritma Pencarian Untuk Menyelesaikan Problema Program Taklinier Integer Campuran, 2008. USU e-Repository © 2008
43
dalam beberapa hal, berkat kenyataan bahwa sukar untuk dipilih dan akhirnya,
optimalitas tidak terjamin.
Yang sungguh berbeda dari Gisvold dan Moe, baru-baru ini Sinclair (1986)
telah menyamaratakan konsep dari suatu penalty berfungsi dua dalam kaitan
dengan Shmelev (1975), dalam rangka memecahkan permasalahan murni QIP
dengan menetapkan kemungkinan Bound.Gagasan untuk pendekatan ini adalah
untuk mengubah bentuk masalah QIP ke dalam suatu masalah padanan dari
yang ”mempersulit” batasan yang telah dipindahkan, tinggal hanya batasan itu
di mana salah satu dari metode menyebutkan dalam bagian yang sebelumnya
dapat digunakan secara efisien. Beberapa aplikasi telah dilaporkan tetapi tidak
ada memberi hasil perhitungan.
Fox dan Liebman (1981) sudah menggunakan suatu modifikasi metode sim-
pleks nonlinier untuk program bilangan bulat nonlinier di dalam permasalahan
disain rancang-bangun. Sasaran dan fungsi batasan tidaklah perlu ekspresif se-
cara analitis tetapi nilai merekadapat diperhitungkan. Metode simpleks nonlinear
adalah suatu metode pendaratan pencarian langsung berdasar pada suatu petun-
juk geometris, di dalam kasus dari suatu ruang n-dimensional, sebagai suatu sim-
pleks n-dimensional. Ada beberapa test kecil permasalahan telah disajikan.
3.4.7 Metode Outer-Approximation
Dari pandangan konsepsi algoritma yang didasarkan pada metode Outer-
Approximation (Geoffrion, 1972) menggambarkan himpunan penyelesaian dari
suatu program sebagai interseksi kumpulan tak terbatas dari himpunan. Dalam
Juandi Sidabutar: Pengembangan Algoritma Pencarian Untuk Menyelesaikan Problema Program Taklinier Integer Campuran, 2008. USU e-Repository © 2008
44
penelitian ini, outer-approximation yang didasari pada karakteristik hiperplane
penopang akan dipakai untuk mendekati problema MINLP dengan suatu pro-
blema program integer linier campuran dan softwarenya telah tersedia.
Asumsi
Dalam penelitian ini, diandaikan bahwa fungsi taklinier f(x), h(x) dan g(x)
dalam (P ) adalah fungsi konveks kontinu differensiabel. Karena f(x) mempunyai
fungsi objektif yang konveks, maka [f(x), u] juga konveks, dengan u merupakan
variabel scalar. Maka (P ) dapat ditulis dalam program berikut dengan fungsi
objektif linier.
minZ = cTy − µ
kendala f(x) − µ ≤ 0
H(x) ≤ 0
G(x) +B(y) ≤ 0
x ∈ X, y ∈ U
µ ∈ [fL, fU ]
(P0)
Dengan fL = minf(x) : x ∈ X dan fU = maxf(x) : x ∈ X
Juga diandaikan bahwa (P ) memenuhi bentuk kualifikasi kendala slatter,
yaitu terdapat suatu titik x ∈ X sehingga h(x) < 0, g(x) +B(y) < 0∀y ∈ U ∩ V
V = y : y ∈ Y, integer , h(x) ≤ 0, g(x) +B(y) ≤ 0
untuk beberapa x ∈ X
(3.33)
Juandi Sidabutar: Pengembangan Algoritma Pencarian Untuk Menyelesaikan Problema Program Taklinier Integer Campuran, 2008. USU e-Repository © 2008
45
Andaikan F (y) mendefinisikan himpunan yang layak dalam ruang kontinu
problema P0 untuk setiap y ∈ U ∩ V .
F (y) = x, µ : x ∈ X,µ ∈ [fL, fU ]
h(x) ≤ 0, f(x) − µ ≤ 0,
g(x) +B(y) ≤ 0
(3.34)
Jadi F (y) dikandung dalam himpunan konveks polyhedral kompak. Dan
F (y) adalah himpunan konveks tertutup untuk setiap y ∈ U∩V . Karena itu, dise-
babkan keterpisahan variabel diskrit dalam problema (apa yang perlu dilakukan
ialah memindahkan daerah F (y) secara linier dalam ruang), dapat didefinisikan
daerah layak kontinu dari problema P0 dengan himpunan tak hingga ruang sete-
ngah penopang berikut:
0 ≥ f(x) − µ ≥ f(xi) + ∇f(xi)T (x− xi) − µ
0 ≥ h(x) ≥ h(xi) + ∇h(xi)T (x− xi)
0 ≥ g(x) +B(y) ≥ g(xi) + ∇g(xi)T (x− xi) +B(y)
x ∈ X,µ ∈ [fL, fU ], y ∈ U
∀xi ∈ X (3.35)
Disini, ∇f(xi) adalah n-vektor gradient ∇h(xi) dan ∇g(xi) masing-masing
matrix Jacobi n× p dan n× q. Catat bahwa pertidaksamaan dalam (4.3) berlaku
untuk setiap x ∈ F (y). Juga jika xI 6∈ F (y) maka untuk setiap fungsi dalam
(3.35), ψ(xi) > 0, jadi F (y) dan xi terletak pada sisi berlawanan dari hiperplane
ψ(xi) + ∇ψ(xi)T (x− xi) = 0. Himpunan ruang setengah dalam (3.35) berkaitan
dengan pendekatan fungsi konveks dalam f, h, g oleh maksimum titik per titik
dari kumpulan penopang liniernya.
Juandi Sidabutar: Pengembangan Algoritma Pencarian Untuk Menyelesaikan Problema Program Taklinier Integer Campuran, 2008. USU e-Repository © 2008
46
Outer-approximation dari ruang layak kontinu program P0, oleh irisan se-
mua ruang setengah konvergen yang mengandungnya, membawa kepada formulasi
program bilangan integer linier campuran semi-infinit :
minZ = cTy − µ
kendala
f(xi) + ∇f(xi)T (x− xi) − µ ≤ 0
h(xi) + ∇h(xi)T (x− xi) ≤ 0
g(xi) + ∇g(xi)T (x− xi) +B(y) ≤ 0
x ∈ X,µ ∈ [fL, fU ], y ∈ U
∀xi ∈ X (P1)
Lemma 1
Jika asumsi terhadap fungsi dan himpunan dalam problema P0 berlaku,
maka problema P1 dan P0 ekivalen.
3.4.7.1 Master Program.
Walaupun problema P1 adalah program bilangan integer linier campuran,
merupakan program semi-infinit karena kendala pertidaksamaan harus berlaku
untuk sejumlah infinit titik dalam himpunan X. Walaupun ini, secara umum
sulit diselesaikan tapi dari sifat diskrit problema dalam hal penyelesaian terhadap
program P1. Jika terdapat satu, harus dikaitkan (oleh fisibilitas) dengan titik
integer y ∈ U ∩ V , dengan V memiliki representasi ekivalen.
Juandi Sidabutar: Pengembangan Algoritma Pencarian Untuk Menyelesaikan Problema Program Taklinier Integer Campuran, 2008. USU e-Repository © 2008
47
Lemma 2
Andaikan [U = y : y ∈ Y, cacah , A2y ≤ a2] ∩ V ⊂ Rn+ merupakan him-
punan layak diskrit program P1; A2 diandaikan matrix bilangan integer. Bagian
integer dari penyelesaian terhadap program P1 harus suatu elemen dari himpunan
diskrit U ∩ V dan terjadi pada vertex polyhedral yang mencakup himpunan.
Catatan
Setiap himpunan polyhedral tidak kosong dari bentuk P ∗ harus memiliki
sekurang-sekurang satu titik ekstrem dan jumlah titik ekstrem terbatas.
Pentingnya lemma dan catatan diatas ialah bahwa untuk menyelesaikan pro-
gram P dengan master program outer-approximation, ia cukup memformulasikan
problema master ini dengan hanya sejumlah titik terbatas, yaitu terhadap yang
berkaitan dengan titik ekstrem dari polyhedron yang berhubungan dengan convex
hull penyelesaian layak integer C0U ∩ V .
Untuk menentukan titik (xi), yang berkaitan dengan titik potong y ∈ C0U∩
V pada outer-approximation daerah layak kontinu dari program P harus diper-
lihatkan, dapat dipakai konsep projeksi (Geoffrion, 1972). Projeksi problema P
ke y diberikan oleh
miny
[ infx∈X
CT (y) + f(x) dengan h(x) 0, g(x) +B(y) ≤ 0]
Kendala y ∈ U ∩ V(3.36)
Telah diperlihatkan (Geoffrion, 1972) bahwa problema pers (3.36) ekivalen
dengan program P . Nilai fungsi infimum dari problema ”dalam” merupakan harga
optimum dari P untuk yi ∈ U ∩ V tetap akan berkaitan dengan harga optimum
Juandi Sidabutar: Pengembangan Algoritma Pencarian Untuk Menyelesaikan Problema Program Taklinier Integer Campuran, 2008. USU e-Repository © 2008
48
z(yi) dari optimisasi subproblema (program nonlinier konvex).
min z(yi) = CTyi + f(x)
kendala h(x) ≤ 0
g(x) +B(yi) ≤ 0
x ∈ X
(S(y))
Jelas bahwa program P tidak suatu program konvex dalam x dan y, ke-
cuali dengan menetapkan y. Subproblema ini akan didefinisikan untuk semua
yi ∈ U ∩ V , karena untuk yi sebagai calon penyelesaian optimum terhadap pro-
blema P , yi harus sedemikian sehingga subproblema (S(yi)) layak, yaitu yi ∈ V .
Karena itu, seperti diberikan oleh subproblema ini dan hubungannya dengan P ,
himpunan titik kontinu xi untuk outer-epproximation dalam P1, diberikan oleh
titik-titik yang mendefinisikan penyelesaian optimum subproblema S(y) untuk se-
jumlah titik ekstrem terbatas yi ∈ U ∩ V . Jadi, master program dalam bentuk
akhir diberikan oleh program bilangan linier integer campuran berikut :
minZ = CTy + µ
kendala
f(xi) + ∇f(xi)T (x− xi) − µ ≤ 0
h(xi) + ∇h(xi)T (x− xi) ≤ 0
g(xi) + ∇g(xi)T (x− xi) +B(y) ≤ 0
x ∈ X,µ ∈ [fL, fU ], y ∈ U
semua i ∈ T (M)
Dengan
T =
i : xi ∈ X penyelesaian optimum untuk S(yi)
pada titik ekstrem yI ∈ C0U ∩ V
(3.37)
Juandi Sidabutar: Pengembangan Algoritma Pencarian Untuk Menyelesaikan Problema Program Taklinier Integer Campuran, 2008. USU e-Repository © 2008
49
Jelas problema P mempunyai penyelesaian optimum terbatas karena daerah
layaknya diandaikan tidak kosong dan kompak. Dalam hal bahwa syarat ini tidak
berlaku mudah untuk diperlihatkan bahwa problema P tidak layak atau mem-
punyai penyelesaian tak terbatas jika dan hanya jika keadaan yang sama benar
untuk M . Untuk tak terbatas adalah mungkin untuk mengandalkan problema
terhadap daerah yang diketahui mengandung penyelesaian terbatas.
Teorema 1
(x∗, y∗) optimum dalam P jika dan hanya jika (x∗, y∗) optimum dalam M
dengan µ∗ = f(x∗).
Bukti
Andaikan (x∗, y∗) optimum dalam P . Dari Lemma 2, y∗ ∈ C0U ∩ V dan
dari konsep projeksi x∗ ∈ X mencapai infimum dalam pers (3.36), yaitu:
z∗ = CTy∗ + f(x∗) ≤ CTy + f(x) untuk semua x, y
Dari outer-approximation pers (3.35) dan dari definisi M jelas bahwa (x∗, y∗)
layak dalam program M dengan (x, y) = (x∗, y∗). Terutama karena x = x∗ ∈
F (y∗), 0 ≥ f(x∗)−µ ≥ supf(xi)+∇f(xi)T (x− xi)− µ : i ∈ T. Maksimum per
titik harus dicapai pada suatu titik batas (xi, f(xi))), kalau tidak hasil diperoleh
untuk minimum tanpa kendala. y∗ ∈ C0U ∩ V , xi = x∗ optimum dalam S(y∗),
akibatnya bahwa min z = CTy∗+µ∗, µ∗ = f(x∗). Bukti bahwa arah lainnya sama.
Walaupun master program M mencakup outer-approximation hanya pada
jumlah titik terbatas xi , karena sifat kombinatorial problema, bilangan demikian
dapat sangat besar. Jadi untuk menyelesaikan master program dapat dipakai re-
laksasi (Geoffrion, 1972). Andaikan G dan Γk menyatakan daerah layak problema
Juandi Sidabutar: Pengembangan Algoritma Pencarian Untuk Menyelesaikan Problema Program Taklinier Integer Campuran, 2008. USU e-Repository © 2008
50
P0 dan versi relaksasi Mk (pada tahap k) dari master program M .
G = x, y : x ∈ X, y ∈ U, f(x) − µ ≤ 0, h(x) ≤ 0, g(x) +B(y) ≤ 0 (3.38)
Γk = (X × U) ∩ Ωk (3.39)
Dengan
Ωk = x, y :f(xi) + ∇f(xi)T (x− xi) − µ ≤ 0
h(xi) + ∇h(xi)T (x− xi) ≤ 0
g(xi) + ∇g(xi)T (x− xi) +B(y) ≤ 0, semua i ∈ Γk
Γk ∈ Γ, µ ∈ [fL, fU ]
(3.40)
Perhatikan bahwa Γk adalah pendekatan untuk himpunan layak G. Dengan
demikian relaksasi sebagai strategi untuk menyelesaikan master program M , me-
ngakibatkan :
i. Pada iterasi k selesaikan versi relaksMk yang mengabaikan beberapa kendala
(yaitu i ∈ Γ\Γk).
ii. Jika penyelesaian hasil (x, yk+1) tidak memenuhi kriteria penghentian ter-
tentu, maka selesaikan subproblema S(yk+1) untuk menentukan titik kontinu
xk+1 pada outer-approximation.
iii. Bentuk versi relaks baru Mk+1 oleh irisan Γk dan ruang setengah tertutup
yang dikaitkan dengan xk+1, selesaikan lagi dan teruskan dalam cara ini.
Juandi Sidabutar: Pengembangan Algoritma Pencarian Untuk Menyelesaikan Problema Program Taklinier Integer Campuran, 2008. USU e-Repository © 2008
51
Karena itu, versi relaks master program M yang harus diselesaikan pada
iterasi k diberikan oleh
minz¯
k = CTy + µ
kendala (x, y) ∈ Ωk
x ∈ X, y ∈ U,µ ∈ [fL, fU ]
(Mk)
3.4.7.2 Sifat Pembatasan.
Sifat berikut memperlihatkan bahwa setiap pendekatan mengandung him-
punan layak G.
Lemma 3
G ⊆ Γk untuk semua k.
Karena pada penyelesaian optimum dari tiap versi relaks master program,
kesamaan u = f(x) berlaku, akibatnya dari bukti lemma 3 bahwa prosedur outer-
approximation menyelesaikan suatu problema dari bentuk P : minCTy + f(x) :
(x, y) ∈ G dengan mensubstitusikan untuk P barisan problema pendekatan
Mk : minCTy + f(x) : (x, y) ∈ Γk, k = 0, 1, 2, . . . (3.41)
dengan G ⊆ Γk ⊆ Γk−1 ⊆ · · · ⊆ Γ0
Karena itu, dari konsep relaksasi problema (berkendala lebih sedikit) me-
ngakibatkan
minCT y + f(x) : (x, y) ∈ G ≥ minCT y + f(x) : (x, y) ∈ ΓL
≥ · · · ≥ minCT y + f(x) : (x, y) ∈ Γ0(3.42)
Juandi Sidabutar: Pengembangan Algoritma Pencarian Untuk Menyelesaikan Problema Program Taklinier Integer Campuran, 2008. USU e-Repository © 2008
52
yaitu, barisan harga optimum fungsi objektif zk = CTy + f(x) yang diperoleh
pada penyelesaian berurutan dari master problema relaks Mk, harus merupakan
barisan tidak turun monoton dari batas bawah pada harga optimum problema
awal P . Karena subproblema S(y) diperoleh dari program P untuk y ∈ U ∩ V
tetap. S(y) merupakan pembatasan terhadap P dan hal berikut berlaku
minz = CT y + f(x) : (x, y) ∈ G
≤ minz(yi) = CT yi + f(x) : x ∈ X, h(x) ≤ 0, g(x) + B(yi) ≤ 0(3.43)
Untuk semua yi ∈ U ∩ V tetap, yaitu harga optimum fungsi objektif sub-
problema S(yi) untuk setiap yi ∈ U ∩ V memberikan batas atas sah pada harga
optimum problema P . Jelas, barisan harga z(yi) tidak perlu monoton tidak naik,
tapi selalu dapat dipertahankan harga terbaik saat ini z∗, sebagai batas atas
sah. Karena oleh pengandaian daerah layak subproblema S(y) himpunan konvex
kompak, fungsi objektif adalah konvex dan kualifikasi kendala slater berlaku, ini
memastikan syarat perlu dan cukup untuk adanya penyelesaian optimum tunggal
dalam subproblema S(y) untuk semua y ∈ U ∩ V .
Guna memperhitungkan secara eksplisit sifat pembatasan dalam prosedur
untuk implementasi efisien, dan untuk memberikan syarat penghentian dalam
algoritma kendala µ ∈ [fL, fU ] yang mengajukan rentang terhadap harga fungsi
objektif dalam master program, dapat digantikan tanpa adanya perubahan oleh
batas lebih kuat z¯
k−1 ≤ z¯< z∗ dengan
z¯k = minz = CT y + f(x) : (x, y) ∈ G (3.44)
dan z∗ batas atas terbaik saat ini. Walaupun kendala z¯
k−1 ≤ z¯
k berlebihan, karena
ia dipenuhi oleh algoritma outer-approximation, ia diajukan untuk mempertinggi
efisiensi prosedur.
Juandi Sidabutar: Pengembangan Algoritma Pencarian Untuk Menyelesaikan Problema Program Taklinier Integer Campuran, 2008. USU e-Repository © 2008
53
3.4.7.3 Algoritma.
Algoritma outer-approximation dapat dinyatakan berdasarkan seni yang
telah dikemukakan pada bagian terdahulu. Semua hipotesis yang diakibatkan
dalam perkembangan diandaikan berlaku, terutama hipotesis yang memastikan
bahwa P mempunyai penyelesaian optimum terbatas. Algoritmanya adalah seba-
gai berikut:
Definisikan
C(xi) = x, y :f(xi) + ∇f(xi)T (x − xi)− µ ≤ 0,
h(xi) + ∇h(xi)T (x − xi) ≤ 0
g(xi) + ∇g(xi)T (x− xi) + B(y) ≤ 0,
xI , x ∈ X, y ∈ U, µ ∈ R1
Langkah 1
Buat Ω0 = Rn × Rm, batas bawah z0 = −∞, batas atas z∗ = +∞, i = 1 pilih
kombinasi cacah y1 ∈ U atau y1 ∈ U ∩ V jika diketahui.
Langkah 2
Selesaikan subproblema S(yi)) untuk problema yi
minz(yi) = CTyI + f(x)
Kendala h(x) ≤ 0
g(x) +B(yi) ≤ 0
x ∈ X
Juandi Sidabutar: Pengembangan Algoritma Pencarian Untuk Menyelesaikan Problema Program Taklinier Integer Campuran, 2008. USU e-Repository © 2008
54
Salah satu dari hal berikut harus terjadi:
(a) Problema S(yi) mempunyai penyelesaian optimum terbatas (xi, z(yi)) de-
ngan z(yi) adalah batas atas sah terhadap program P . Perbaiki perki-
raan batas atas saat ini : z∗ = minz∗, z(yi). Jika z∗ = z(yi) buat
y∗ = yi, x∗ = xi. Buat Ω = Ωi−1 ∩ C(xi), dan GO TO langkah 3.
(b) Problema S(yi) tidak layak (yaitu yi 6∈ V ) dengan hasil berkaitan xi. Pe-
roleh irisan integer untuk menghilangkan yi dari penyelesaian. Buat Ω =
Ωi−1 ∩ C(xi) dan GO TO langkah 3.
Langkah 3
Buat dan selesaikan master program relaks saat ini M i.
min zi = CTy + µ
(x, y) ∈ Ωi
Kendala zi−1 ≤ zi < z∗ (irisan integer)i
x ∈ X, y ∈ U
(M i)
Salah satu harus berlaku :
(a) Problema M i tidak memiliki penyelesaian layak integer campuran → STOP.
Penyelesaian optimum terhadap program P diberikan oleh batas atas saat
ini z∗ dan vektor variabel (x∗, y∗) dikaitkan dengan sunproblema yang ber-
hubungan dalam langkah 2a.
(b) Problema M i mempunyai penyelesaian optimum terbatas (zI , yi) dengan
zi adalah batas bawah pada harga optimum program P , dan y kombinasi
Juandi Sidabutar: Pengembangan Algoritma Pencarian Untuk Menyelesaikan Problema Program Taklinier Integer Campuran, 2008. USU e-Repository © 2008
55
integer baru yang akan diuji algoritma. Buat yi+1 = y, i = i + 1 untuk
memperlihatkan iterasi baru. KEMBALI ke langkah 2.
Terlihat dari langkah-langkah ini, algoritma terdiri dari penyelesaian barisan
subproblema program nonlinier S(y) dan master problema program integer linier
campuran M i, yang pada umumnya konvergen dalam sejumlah langkah terbatas
terhadap penyelesaian problema P .
Juandi Sidabutar: Pengembangan Algoritma Pencarian Untuk Menyelesaikan Problema Program Taklinier Integer Campuran, 2008. USU e-Repository © 2008
BAB 4
PENGEMBANGAN ALGORITMA PENCARIAN PADAPROBLEMA PROGRAM TAKLINIER INTEGER CAMPURAN
Pada bab berikut, diberikan gambaran tentang kerangka dasar metode penye-
lesaian, ide dasar, dan algoritma dari metode serta contoh kasus masalah problema
sintesa dalam design proses kimia yang terdiri dari tiga contoh kasus yaitu pro-
blema perencanaan kecil, problema proses sintesa sistem dan problema sintesa
flowsheet.
4.1 Kerangka Dasar Metode Penyelesaian
Model rancangan dasar dapat ditulis dalam berikut :
minF (x¯) + d
¯T y¯
kendala f(x¯) +A1y
¯= b
¯1 (m1 baris )
A2(x¯) +A3y
¯= b
¯2 (m2 baris )
l¯≤ (x
¯, y¯)T ≤ u
¯(m1 +m2)
Algoritma berlangsung dengan mengerjakan barisan iterasi utama, dalam
mana kendala di linierisasi pada beberapa titik basis x¯k dan nonlinieritas di
gabungkan dengan fungsi objektif beserta estimasi pengali Lagrange.
Jadi dapat ditulis
f(x¯, x¯k) = f(x
¯k) + J(x¯k)(x¯
− x¯k)
Jl = [J(x¯k)]i,j =
∂fi
∂xj
→ Matriks Jacobi
56
Juandi Sidabutar: Pengembangan Algoritma Pencarian Untuk Menyelesaikan Problema Program Taklinier Integer Campuran, 2008. USU e-Repository © 2008
57
Sehingga subproblema berkendala linier diselesaikan pada iterasi utama ke-k yaitu
minx¯
,y¯
L(x¯, y¯, x¯k, λk, ρ) = F (x
¯) + d
¯Ty¯− λT
k (f − f ) +1
2ρ(f − f )T (f − f )
Kendala Jkx¯
+A1y¯
= b¯1 + Jkx
¯k − f(x¯k)
A2x¯
+A3y¯
= b¯2
l¯≤ (x
¯, y¯)T ≤ u
¯
Fungsi objektifnya merupakan perluasan Lagrange yang dimodifikasi, pa-
rameter pinalti ρ mempercepat konvergensi dari titik estimasi awal yang berada
jauh dari titik optimum. Pengali Lagrange λk diambil sebagai nilai optimal di
penyelesaian subproblema sebelumnya.
Apabila barisan iterasi utama mendekati titik optimum (diukur oleh pe-
rubahan relative dalam estimasi λk dan derajat terhadap non kendala tak linier
dipenuhi x¯k) parameter penalti ρ dikurangi menjadi 0.
Metode yang diajukan menggunakan strategi kendala aktif, yang dapat di-
sajikan dalam bentuk :
Ax¯
=
B S N
I
x¯B
x¯S
x¯N
=
b¯
b¯N
B Himpunan vektor barisS Himpunan vektor superbarisN Himpunan vektor nonbarisI Matriks satuan
Peubah nonbaris x¯N berada pada batasannya dan tetap disana untuk langkah
Juandi Sidabutar: Pengembangan Algoritma Pencarian Untuk Menyelesaikan Problema Program Taklinier Integer Campuran, 2008. USU e-Repository © 2008
58
∆x¯
berikutnya. Jadi dapat dituliskan
Bx¯B + Sx
¯S +Nx¯N = b
¯
x¯N = b
¯N
Dengan b¯N adalah kombinasi batas atas dan batas bawah. Peubah su-
perbasis x¯S bebas bergerak kesembarang asal dan memberikan dorongan untuk
meminimumkan fungsi objektif.
Peubah basis x¯B memenuhi persamaan
B∆x¯B + S∆x
¯S = 0
Jadi ∆x¯
dapat ditulis dalam perubahan pada peubah super basis sehingga
∆x¯
= Z∆x¯S
dengan
Z =
−B−1S
I
0
Disini terlihat bahwa matriks Z bekerja sebagai matriks reduksi dan men-
galikan dari kiri gradien untuk membentuk gradien tereduksi h¯
= ZT g¯
dengan
g¯
= ∂L∂x¯.
Ia juga mengalikan dari kiri dan kanan matriks Hessi dari turunan parsial
kedua untuk menghasilkan langkah seperti Newton dalam ruang tereduksi peubah
superbasis. Implementasi dari metode memakai aproksimasi quasi-Newton RTR
terhadap matriks Hessi tereduksi, dimana R matriks segitiga atas ”sparsity”
dalam kendala dipertahankan dengan menyimpan dan memutakhirkan faktorisasi
LU dari matriks basis B.
Juandi Sidabutar: Pengembangan Algoritma Pencarian Untuk Menyelesaikan Problema Program Taklinier Integer Campuran, 2008. USU e-Repository © 2008
59
Faktorisasi ini memberi arti bahwa Z atau B−1 tidak di komputasikan secara
eksplisit. Langkah quasi-Newton ∆x¯
dihitung dengan langkah berikut :
i. Selesaikan UTLTπ = g¯B
untuk π dimana vector gradient g¯
dipartisi menjadi
(g¯B, g¯S, g¯N
) berkaitan dengan partisi A dan ∆x¯.
ii. Bentuk h¯
= g¯S
− STπ
iii. Selesaikan RTR∆x¯S = −h
¯
iv. Selesaikan LU∆x¯B = −S∆x
¯
Ukuran himpunan superbasis bervariasi ketika algoritma penvairan berlang-
sung. Jika batas peubah dijumpai, peubah tersebut dibuat menjadi nonbasis dan
dipindahkan dari himpunan superbasis (atau basis).
Sedangkan jika konvergensi dicapai dalam suatu subruang, satu atau lebih
peubah nonbasis dijadikan superbasis apabila elemen vector reduce cost terkait
g¯N
−NTπ tak nol dan bertanda sesuai.
Metode penyelesaian program stokastik integer campuran bagian terdahulu
adalah metode/algoritma untuk menyelesaikan program stokastik linier dan takli-
nier. Dan kerangka kerja metode tersebut dikembangkan untuk program stokastik
integer campuran.
Juandi Sidabutar: Pengembangan Algoritma Pencarian Untuk Menyelesaikan Problema Program Taklinier Integer Campuran, 2008. USU e-Repository © 2008
60
Ide dasar
Pandang problema program integer campuran linier (Mixed Integer Linear
Programming (MILP)).
min P = C¯
T x¯
kendala Ax¯≤ b
¯
x¯≥ 0
¯
xj integer untuk beberapa j ∈ J
Komponen vector layak basis (x¯B)k terhadap MILP yang diselesaikan seba-
gai problema kontinu dapat ditulis sebagai
(x¯B)k = βk − αk1(x¯N)1 − · · · − αkj∗ (x¯N )j∗ − · · · − αk,n−m(x
¯N )n−m
Andaikan (x¯B)k peubah bernilai integer dan βk tidak bernilai integer, βk
dipartisi menjadi komponen bulat dan pecahan
βk = [βk] + fk
Jika ingin dinaikkan (x¯B)k ke integer terdekat ([β] + 1), dapat dinaikkan
peubah takbasis, misalnya (x¯N )j∗ diatas batasannya, asalkan αkj∗ yaitu salah
satu elemen vektor αj∗ negatif.
Ambil ∆j∗ yang merupakan sejumlah pergerakan ke peubah nonbasis (x¯N)j∗
sehingga nilai numeric dan skalar (x¯B)k integer. Maka ∆j∗ dapat dinyatakan
sebagai peubah nonbasis lainnya tetap di nol.
∆j∗ =1 − fk
−αkj∗
Juandi Sidabutar: Pengembangan Algoritma Pencarian Untuk Menyelesaikan Problema Program Taklinier Integer Campuran, 2008. USU e-Repository © 2008
61
Jadi setelah diselesaikan ∆j∗ untuk (x¯N )j∗ diperoleh (x
¯B)k = [β]+1. Sekarang
(x¯B)k suatu bilangan integer.
Terlihat jelas peubah tak basis sangat berpengaruh dalam membulatkan
nilai peubah basis terkait. Ide dasar demikian ini dipergunakan untuk menyele-
saikan program stokastik integer campuran.
4.2 Algoritma dari Metode
Setelah menyelesaikan problem relaksasi dengan metode yang diajukan ter-
dahulu untuk program stokastik linier, prosedur perencanaan penyelesaian layak
integer dapat di deskripsikan sebagai berikut.
Andaikan
x = [x] + f, 0 ≤ f < 1
penyelesaian kontinu dari problem relaksasi
Langkah 1. Pilih baris i∗ infisibilitas integer terkecil, sehingga
δi∗ = minfi, 1 − fi
Langkah 2.. Lakukan operasi ’pricing’, yaitu hitung vTi∗ = eT
i∗B−1.
Langkah 3. Hitung σij = vTi∗aj dengan j berkaitan pada minj| di
σij|
I. Untuk nonbasis j di batas bawah
Jika σij < 0 dan σi∗ = fi hitung ∆ = (1−δi∗)−σij
Jika σij > 0 dan σi∗ = 1 − fi hitung ∆ = (1−δi∗)−σij
Juandi Sidabutar: Pengembangan Algoritma Pencarian Untuk Menyelesaikan Problema Program Taklinier Integer Campuran, 2008. USU e-Repository © 2008
62
Jika σij < 0 dan σi∗ = 1 − fi hitung ∆ = δi∗−σij
Jika σij > 0 dan σi∗ = fi hitung ∆ = δi∗σij
II. Untuk nonbasis j di batas atas
Jika σij < 0 dan σi∗ = 1 − fi hitung ∆ = (1−δi∗)−σij
Jika σij > 0 dan σi∗ = fi hitung ∆ = (1−δi∗)σij
Jika σij > 0 dan σi∗ = 1 − fi hitung ∆ = δi∗σij
Jika σij < 0 dan σi∗ = fi hitung ∆ = δi∗−σij
Jika tidak pergi ke nonbasis atau superbasis j berikutnya (jika ada). Jadi
nilai j∗ dinaikan dari batas bawahnya atau diturunkan dari batas atasnya. Jika
tidak ada pergi ke i∗ berikutnya.
Langkah 4. Hitung αj∗ = B−1aj∗ yaitu selesaikan Bαj∗ = aj∗ untuk αj∗
Langkah 5. Uji kelayakan, terdapat 3 kemungkinan untuk peubah basis tetap
layak karena pelepasan peubah nonbasis j∗ dari batasnya.
Jika j∗ dibatas bawah
Ambil
A = mini′ 6=i∗ |αij∗>0
xBi′ − li′
αij∗
B = mini′ 6=i∗ |αij∗<0
ui′ − xBi′
−αij∗
C = ∆
gerak maksimum dari j∗ tergantung pada θ∗ = min(A,B,C)
Juandi Sidabutar: Pengembangan Algoritma Pencarian Untuk Menyelesaikan Problema Program Taklinier Integer Campuran, 2008. USU e-Repository © 2008
63
Jika j∗ di batas atas.
A′ = mini′ 6=i∗ |αij∗>0
xBi′ − li′
−αij∗
B ′ = mini′ 6=i∗ |αij∗>0
ui′ − xBi′
αij∗
C ′ = ∆
Gerak maksimum dari j∗ tergantung pada θ∗ = min(A′, B′, C ′)
Langkah 6. Pertahankan basis untuk ke 3 kemungkinan
1. Jika A atau A′
(a) xBi′ menjadi nonbasis di batas bawah li′
(b) xj∗ menjadi basis (menggantikan xBi′ )
(c) xi∗ tetap basis (tak integer)
2. Jika B atau B ′
(a) xBi′ menjadi nonbasis di batas atas ui′
(b) xj∗ menjadi basis (menggantikan xBi′ )
(c) xi∗ tetap basis (integer)
3. Jika C atau C ′
(a) xj∗ menjadi basis (menggantikan xi∗)
(b) xi∗ menjadi superbasis bernilai integer.
Ulangi dari langkah 1.
Juandi Sidabutar: Pengembangan Algoritma Pencarian Untuk Menyelesaikan Problema Program Taklinier Integer Campuran, 2008. USU e-Repository © 2008
64
4.3 Contoh Kasus Masalah Problema Sintesa dalam Design ProsesKimia
Pada bagian ini akan diselesaikan tiga contoh yang berhubungan dengan
optimisasi pada masalah sistem proses sistesa. Proses sintesa dapat didefinisikan
sebagai seleksi, pembentukan dan operasi dari proses unit untuk mencapai hasil
optimal. Dari diberikan struktur super dari design proses kimia akan dihitung kon-
figurasi dari hasil optimal yang diinginkan. Lihat Duran dan Grossman (1986a),
untuk deskripsi dari masalah. Penulis telah membuat formulasi dari kelas masalah
MINLP dengan variabel integer (y) berdasarkan bilangan biner.
4.3.1 Contoh 1. Problema Perencanaan Kecil
A. KALIMAT MATEMATIKA UNTUK PROBLEMA
Problema berdasarkan Kocis dan Grossman (1986), adalah untuk memilih
konfigurasi terbaik dari struktur super yang diberikan dari skema proses
kimia.(lihat gambar) adalah untuk memproduksi produk C dari material
A dan B. Fungsi objektifnya adalah untuk memaksimumkan keuntungan
yang diberikan bahwa terdapat batas atas dari produksi C. Berdasarkan
Kocis dan Grossman (1986), formulasi program matematika dari masalah
diturunkan dari struktur super yang dapat ditulis dalam model MINLP.
Juandi Sidabutar: Pengembangan Algoritma Pencarian Untuk Menyelesaikan Problema Program Taklinier Integer Campuran, 2008. USU e-Repository © 2008
65
Gambar 4.1 : Struktur Super pada Contoh 1
Minimize F = 3.5y1 + y2 + 1.5y3 + 7b1 + b2 + 1.2b3 + 1.8a− 11c
Subject to b2 − ln(1 + a2) = 0
b3 − 1.2ln(1 + a3) = 0
c− 0.9b = 0
− b+ b1 + b2 + b3 = 0
a− a2 − a3 = 0
b− 5y1 ≤ 0
a2 − 5y2 ≤ 0
a3 − 5y3 ≤ 0
c ≤ 1
b2 ≤ 5
0 ≤ yj ≤ 1 dan integer, untuk j = 1, 2, 3
a, a2, a3, b, b1, b2, b3, c ≥ 0
Juandi Sidabutar: Pengembangan Algoritma Pencarian Untuk Menyelesaikan Problema Program Taklinier Integer Campuran, 2008. USU e-Repository © 2008
66
Fungsi objektif dari formulasi diatas adalah untuk meminimumkan keuntu-
ngan negatif. Terdapat 3 variabel biner dari formulasi, 8 variabel kontinu, 2
persamaan nonlinier, 3 persamaan linier, 3 ketaksamaan dan 2 batas atas.
B. DISKUSI HASIL
Karena problema mengandung hanya tiga variabel biner, maka hal ini tidak
cukup untuk menggunakan strategi integer untuk menyelesaikan problema.
Dengan demikian dapat digunakan pencarian integer. Berdasarkan pro-
blema struktur super, maka tidak diperlukan untuk menyelesaikan problema
relaksasi. Kita melompat ke langkah 4 untuk mencari fungsi objektif. Hal
ini digunakan untuk menghasilkan produk C. Variabel biner y1 tidak harus
bernilai nol (lihat struktur super). Bagaimanapun perubahan diskrit dapat
berakibat hanya untuk y2 dan y3. Hasil diberikan pada tabel 4.1. Nilai ob-
jektif telah sesuai dengan hasil dari metode Kocis dan Grossmann (1986).
Tabel 4.1 : Hasil Contoh 1
Variabel Aktivitas Setelah PencarianInteger
a 1,52420a2 0,0a3 1,52420b 1,11111b1 0,0b2 0,0b3 1,11111c 1,0y1 1,0y2 1,0y3 0,0
Harga Obj (F) -1,92310
Juandi Sidabutar: Pengembangan Algoritma Pencarian Untuk Menyelesaikan Problema Program Taklinier Integer Campuran, 2008. USU e-Repository © 2008
67
4.3.2 Contoh 2. Problema Proses Sintesa Sistem
A. MODEL MATEMATIKA DARI PROBLEMA
Contoh ini berdasarkan pada Duran and Grossmann (1983,1986b), adalah
satu simultan perhitungan dari struktur optimal dan operasi parameter un-
tuk proses berdasarkan spesifikasi design yang diberikan. Variabel keputu-
san telah didefinisikan terlebih dahulu.
y adalah variabel biner yang berarti berhubungan dengan setiap unit proses
(bagian dari alat-alat) sebagai eksistensi potensial dalam konfigurasi optimal
akhir. x adalah variabel kontinu yang merepresentasikan parameter seperti
aliran dari material.
Secara umum, fungsi objektif adalah untuk meminimumkan biaya, termasuk
investasi dan biaya operasi. Struktur super dari problema sintesa dapat
dilihat pada gambar. Formulasi MINLP berdasarkan Duran dan Grossmann
(1983,1986b)
Gambar 4.2 : Struktur Super pada Contoh 2
Juandi Sidabutar: Pengembangan Algoritma Pencarian Untuk Menyelesaikan Problema Program Taklinier Integer Campuran, 2008. USU e-Repository © 2008
68
Minimum F = 5y1 + 8y2 + 6y3 + 10y4 + 6y5 + 7y6 + 4y7 + 5y8
− 10x3 − 15x5 + 15x10 + 80x17 + 25x19 + 35x21 − 40x9
+ 15x14 − 35x25 + exp(x3) + exp(x5/1.2)
− 65 ln(x10 + x17 + 1) − 90 ln(x19 + 1) − 80 ln(x21 + 1) + 120
kendala − 1.5 ln(x19 + 1) − ln(x21 + 1) − x14 ≤ 0
− ln(x10 + x17 + 1) ≤ 0
− x3 − x5 + x10 + 2x17 + 0.8x19 + 0.8x21 − 0.5x9 − x14 − 2x25 ≤ 0
− x3 − x5 + 2x17 + 0.8x19 + 0.8x21 − 2x9 − x14 − 2x25 ≤ 0
− 2x17 − 0.8x19 − 0.8x21 + 2x9 + x14 + 2x25 ≤ 0
− 0.8x19 − 0.8x21 + x14 ≤ 0
− x17 + x9 + x25 ≤ 0
− 0.4x19 − 0.4x21 + 1.5x14 ≤ 0
0.16x19 + 0.16x21 − 1.2x14 ≤ 0
x10 − 0.8x17 ≤ 0
− x10 + 0.4x17 ≤ 0
exp(x3) − 10y1 ≤ 1
x9 − 10y3 ≤ 0
0.8x19 + 0.8x21 − 10y4 ≤ 0
2x17 − 2x9 − 2x25 − 10y5 ≤ 0
x19 − 10y6 ≤ 0
x21 − 10y7 ≤ 0
Juandi Sidabutar: Pengembangan Algoritma Pencarian Untuk Menyelesaikan Problema Program Taklinier Integer Campuran, 2008. USU e-Repository © 2008
69
x10 + x17 − 10y8 ≤ 0
y1 + y2 = 1 , y4 + y5 ≤ 1
− y4 + y6 + y7 = 0
y3 − y8 ≤ 0
0 ≤ yj ≤ 1 , j = 1, ..., 8
l ≤ x ≤ u , x = (xj : j = 3, 5, 10, 17, 19, 21, 9, 14, 25) ∈ R9
lT = (0, 0, 0, 0, 0, 0, 0, 0, 0), uT = (2, 2, 1, 2, 2, 2, 2, 1, 3)
Formulasi di atas terdiri dari 8 variabel biner, 9 variabel kontinu terbatas,
23 kendala ketaksamaan. ketaklinieran ada pada fungsi objektif dan dalam
4 ketaksamaan.
B. DISKUSI HASIL
Solusi optimal kontinu diperoleh menggunakan software MINOS. Hanya satu
variabel biner adalah integer (pada batas bawah) dari solusi kontinu.Variabel
biner Y7 adalah himpunan super basis dengan nilai tak integer. Kemu-
dian kita pindahkan variabel ke integer terdekat menggunakan strategi pe-
motongan dan mempertahankan super basis. Kita harus memeriksa ke-
layakan berdasarkan variabel basis dalam pemindahan ini. Kita integrasikan
sisa variabel biner non-integer menggunakan strategi integrasi yang telah
diperkenalkan. Hasil kontinu dan integer dapat dilihat pada tabel 4.2 di
bawah ini
Hasil kita telah sesuai dengan hasil dari Duran dan Grossmann (1986b).
Total waktu komputasi dengan menggunakan metode ini adalah 16.78 de-
tik. Komputasi ini lebih baik dari Duran dan Grossmann (1983,1986b) yang
membutuhkan waktu 26 detik dari waktu CPU (DEC-20) untuk menyele-
Juandi Sidabutar: Pengembangan Algoritma Pencarian Untuk Menyelesaikan Problema Program Taklinier Integer Campuran, 2008. USU e-Repository © 2008
70
saikan masalah.
Tabel 4.2 : Hasil Contoh 2
Variabel Aktifitas pada Aktifitas SetelahSolusi Kontinu Proses Integer
x3 1,90293 0,0x5 2,0 2,0x10 0,52752 0,46784x17 0,65940 0,58480x19 2,0 2,0x21 1,08333 0,0x9 0,65940 0,0x4 0,41111 0,26667x25 0,0 0,58480y1 0,57055 0,0y2 0,42945 1,0y3 0,06594 0,0y4 0,30833 1,0y5 0,0 0,0y6 0,2 1,0y7 0,10833 0,0y8 0,11869 1,0
Nilai Objektif (F) 15,08219 68,00974
4.3.3 Contoh 3. Problema Sintesa Flowsheet
A. MODEL MATEMATIKA PROBLEMA
Pada contoh 1, problema untuk memilih konfigurasi terbaik berdasarkan
beberapa alternatif untuk memproduksi produk C dari bahan A dan B.
Struktur super dapat dilihat pada gambar dibawah ini.
Problema ini, dapat dibentuk dalam MINLP yang mengandung 4 varia-
bel biner, 128 variabel kontinu (81 nonlinier dan 47 linier), 111 kendala
kesamaan (56 nonlinier dan 55 linier) dan 14 kendala ketaksamaan linier.
Karena problema sangat besar, model matematika dari problema ini tidak
Juandi Sidabutar: Pengembangan Algoritma Pencarian Untuk Menyelesaikan Problema Program Taklinier Integer Campuran, 2008. USU e-Repository © 2008
71
dapat dijelaskan secara eksplisit pd bagian ini. Subroutines CALCFG dan
CALCON dari paket MINOS digunakan untuk menyelesaikan problema.
Gambar 4.3 : Struktur Super pada Contoh 3
B. DISKUSI HASIL
Terdapat tiga variabel biner bernilai integer (y1, y2, y3) pada solusi optimal
kontinu. Lihat tabel sebagai hasil.(Kita hanya menampilkan variabel biner
dalam tabel).
Tabel 4.3 : Hasil Contoh 3
Variabel Biner Aktifitas pada Aktifitas SetelahSolusi Kontinu Proses Integer
y1 0.16364 1.0y2 0.0 0.0y3 1.0 1.0y4 0.0 0.0
Nilai Objektif (F) -2174.20801 -2174.20999
Juandi Sidabutar: Pengembangan Algoritma Pencarian Untuk Menyelesaikan Problema Program Taklinier Integer Campuran, 2008. USU e-Repository © 2008
BAB 5
KESIMPULAN DAN SARAN
5.1 Kesimpulan
Strategi pembebasan variabel nonbasic dari batasannya, dikombinasikan de-
ngan metode ”kendala aktif” dan gagasan superbasis telah dibangun untuk me-
mecahkan problema program nonlinier integer campuran yang efisien. Setelah
pemecahan problema dengan tidak memperhatikan syarat kesatuan. Strategi ini
digunakan untuk menguatkan variabel basis integer yang tepat terhadap titik-titik
integer disekitarnya. Perhitungan pengujian prosedur dikenalkan dalam penelitian
ini telah didemonstrasikan dan merupakan pendekatan yang aktif pada problema
dalam skala luas.
Jumlah langkah integer akan terbatas jika jumlah variabel integer diletakkan
pada problema yang terbatas. Bagaimanapun, akan dicatat perhitungan waktu
dari proses integer tidak penting tetapi tergantung pada jumlah variabel integer.
Strategi ini berdasarkan metode Simplex dari program linier. Variabel nonbasis
diambil dari batasannya. Solusi integer yang layak merupakan suboptimal karena
diturunkan dari solusi optimal kontinu.
Pada pemecahan problema linier, solusi suboptimal yang terdiri variabel
interger adalah nilai integer, dapat diperoleh langsung setelah proses integer.
Bagaimanapun, situasi nonlinier sangat berbeda. Karena properties nonlinier dari
fungsi Langrang, yang nilai variabel kontinunya diperoleh setelah proses integer
tidak dapat diharapkan sebagai nilai proper yang disetujui kendala problema.
72
Juandi Sidabutar: Pengembangan Algoritma Pencarian Untuk Menyelesaikan Problema Program Taklinier Integer Campuran, 2008. USU e-Repository © 2008
73
5.2 Saran
Dari hasil yang diperoleh disarankan untuk mengajukan prosedur integer
sebagai strategi efisien untuk memecahkan problema MINLP. Meskipun, akan
sulit jika muncul pada problema yang mempunyai jumlah kendala kesamaan dan
ketaksamaan yang banyak dan atau jumlah variabel integer lebih banyak daripada
kendala atau jumlah variabel nonbasis nonintegernya sedikit.
Juandi Sidabutar: Pengembangan Algoritma Pencarian Untuk Menyelesaikan Problema Program Taklinier Integer Campuran, 2008. USU e-Repository © 2008
DAFTAR PUSTAKA
Aust, R. J. A Dynamic Programming Branch and Bound Algorithm for Pure In-teger Programming. Comp. and Operations Research 5: 27-38, 1976.
Balas, E. and Mazzola, J. B. Nonlinear 0-1 Programming : Linearization Tech-niques, and II Dominance Relations and Algorithm, Math.Progr. 30:1-21,1984a.
Balas, E. and Mazzola, J. B. Nonlinear 0-1 Programming : Linearization Tech-niques, and II Dominance Relations and Algorithm, Math.Progr. 30:22-45,1984b.
Bazaraa, M. S. and Sherali, H. D. Benders’ Partitioning Scheme Applied to a NewFormulation of the Quadratic Assignment Problem. Nav. Res. Log. Quart.27:29-41, 1980.
Bellman, R. Dynamic Programming, Princeton University Press, New Jersey, 1957.
Benichou, M., Gauthier, J. M., Girodet, P., Hentges, G., Ribiere, G. and Vin-cent, O. Experiments in Mixed-Integer Linear Programming. MathematicalProgramming. 1:76-94, 1971.
Berrada, M. and Stecke, K. E. A Branch and Bound Approach for Machine LoadBalancing in Flexible Manufacturing Systems. Management Sci. 32: 1316-1335, 1986.
Bonami, P. et all. An Algorithmic Framework for Convex Mixed Iinteger NonlinearPrograms. Journal of Optimization Theory and Applications, 2005.
Borchers, B. and Mitchel, J. E. An Improved Branch and Bound Algorithm forMixed Integer Nonlinear Programming.Computer and Operations Research,21(4):359-367, 1994.
Bussieck, M. R. and Pruessner, A. Mixed Integer Nonlinear Programming. 2003.
Cooper, L. and Cooper, M. W. Nonlinear Integer Programming. Comp. and Math.with Appls.. 1:215-222, 1975.
Cooper, L. and Cooper, M. W. Introduction to Dynamic Programming. PergamosPress, Oxford, 1981.
Cooper, M. W. A Survey of Methods for Pure Nonlinear Integer Programming .Management Science, 27:353, 1981.
Cooper, M. W. The Use of Dynamic Programming Methodology for the Solutionof a Class of Nonlinear Programming Problems. Naval. Res. Log. Quart. 27:89-95, 1980.
Cooper, M. W. Post Optimality Analysis in Nonlinear Integer Programming forVarious Forms of Constraints. Naval. Res. Log. Quart. 29: 585-592, 1982.
74
Juandi Sidabutar: Pengembangan Algoritma Pencarian Untuk Menyelesaikan Problema Program Taklinier Integer Campuran, 2008. USU e-Repository © 2008
75
Dakin, R. J. A Tree Search Algorithm for Mixed Integer Programming. ComputerJournal 8: 250-255, 1965.
Denardo, E. V. and Fox, B. L. Shorthest Route Methods:2. Group KnapsacksExpanded Networks and Branch and Bound. Operations Research 27: 548-566, 1979.
Duran, M. and Grossmann, I. E. An Outer-Approximation Algorithm for A Classof Mixed Integer Nonlinear Programs. Math. Prog., 36:307339, 1986.
Duran, M. A and Grossmann, I. E. A Mixed-Integer Nonlinier Programming Al-gorithm for Process Systems Synthesis. American Institute of Chemical En-gineers Journal, 32:592-606, 1986.
Exler, O. and Schittkowski. A Trust Region SQP Algorithm for Mixed IntegerNonlinear programming. 2006.
Fox, D. B. and Liebman, J. S. A Discrete Nonlinear Simplex Method for OptimizedEngineering Design. Engineering Optimization 5: 129-149, 1981.
Garfinkel, R. S and Nemhauser, G. L. Integer Programming. John Wiley & Sons,New York, 1972.
Geoffrion, A. M. Generalized Benders Decomposition. Journal of OptimizationTheory and Applications 10: 237-260, 1972.
Gisvold, K. M. and Moe, J. A Method for Nonlinear Mixed-Integer Programmingand Its Application to Design Problems. Journal Engineering for Industry94: 353-364, 1972.
Glover, F. Improved Linear Integer Programming Formulations of Nonlinear Inte-ger Problems. Management Sci. 22: 455-460, 1975.
Glover, F. and Woolsey, E. Further Reduction of Zero-One Polynomial Program-ming Problems to A Zero-One Linear Programming Problems. operationsReseacrh 21: 156-160, 1973.
Glover, F. and Woolsey, E. Converting the 0-1 Polynomial Programming Problemto a 0-1 Linear Programming. management Sci. 22: 180-182, 1974.
Granot, D. and Granot, F. Generalized Covering Relaxation for 0-1 Programs.Operations research 28: 1442-1449, 1980.
Granot, F. and Hammer, P. L. On the Use of Boolean Functions in 0-1 Program-ming. Methods for Operations Research 12: 154-184, 1971.
Grossmann, I. E. Mixed-Integer Programming Approach for The Synthesis of Inte-grated Process Flow-Sheets. Computer and Chemical Engineering 9:463-482,1985.
Gupta, O.K. and Ravindran, A. Branch and Bound Experiments in Convex Nonlin-ear Integer Linear Programming. Management Science, 31:1533-1546, 1985.
Juandi Sidabutar: Pengembangan Algoritma Pencarian Untuk Menyelesaikan Problema Program Taklinier Integer Campuran, 2008. USU e-Repository © 2008
76
Hammer, P. L. A Branch and Bound Method for Linear and Nonlinear Biva-lent Programming. Development in Operations Research, Gordon and Breach,New York, 45-82, 1971.
Hammer, P. L. and Peled, U. On the Maximization of a Pseudo Boolean Function.JACM 19: 265-282, 1972.
Hansen, P. Quadratic Zero-One Programming by Implicit Enumeration. Numeri-cal Methods for Nonlinear Optimization, Academic Press, London, 265-278,1972.
Hansen, P. Methods of Nonlinear 0-1 programming. Ann. Discreate Math, 5:53- ,1979.
Hoang Hai Hoc. Topological Optimization of Networks: A Nonlinear Mixed IntegerModel Employing Generalized Benders Decomposition. IEEE Transactionson Automatic Control AC27: 164-169, 1982.
Jeroslow, R. G. Cross-Branching in Bivalent Programming. Paper Presented atthe 8th International Symposium on Mathematical Programming, Stanford,1973.
Kocis, G. R. and Grossmann, I. E. Relaxation Strategy for the Structural Opti-mization of Process Synthesis. Paper Presented at the Annual ALCHE Meet-ing, Miami, November 1986.
Korner, F. An efficient Branch and Bound Algorithm to Solve Quadratic IntegerProgramming Problem. Computing 30: 253-260, 1983.
Land, A. H. and Doig, A. G. An Automated Method for Solving Discrete Pro-gramming Problems. Econometrics 28: 497-520, 1960.
Lazimy, R. Mixed-Integer Quadratic Programming. Mathematical Programming22: 332-349, 1982.
Lazimy, R. Improved Algorithm for Mixed-Integer Quadratic Programs and a Com-putational Study. Mathematical Programming 24: 100-113, 1984.
Laughhunn, D. J. Quadratic Binary Programming with Application to Capital-Budgeting Problems. Operations Research 18: 454-461, 1970.
Lawler, E. L. and Bell, M. D. A Method for Solving Discrete Optimization Prob-lems. Operations Research 14: 1098-1112, 1966.
Mao, J. C. T. and Wallingford, B. A. An Extension of Lawler and Bell’s Method ofDiscrete Optimization with Examples from Capital Budgeting. ManagementSci. 15: B51-B60, 1969.
Mawengkang, H. An Improved Algorithm for Solving Nonlinear Integer Program-ming Problems,INFORM Meeting, Atlanta, 1996.
Mawengkang, H. Solving Nonlinear Integer Programs with Large-Scale Optimiza-tion Software, Annals of Operation Research, Vol. 5. pp. 425-437, 1985.
Juandi Sidabutar: Pengembangan Algoritma Pencarian Untuk Menyelesaikan Problema Program Taklinier Integer Campuran, 2008. USU e-Repository © 2008
77
Mayne, D. Q, Polak, E and Trahan, R. An Outer-Approximations Algorithm forComputer Aided Design Problemas. Journal of Optimization Theory and Ap-plications, 28:331-352, 1979.
Mcbride, R. D. and Yormark, J. S. An Implicit Algorithm for Quadratic IntegerProgramming. Management Sci. 26: 282-296, 1980a.
Mcbride, R. D. and Yormark, J. S. An Implicit Algorithm for Quadratic IntegerProgramming. Management Sci. 26: 784-795, 1980b.
Mitten, L. G. Composition Principles for Synthesis of Optimal Multi-Stage Pro-cesses. Operations Research 12: 610-619.
Morin, T. L. Computational Advances in Dynamic Programming. Dynamic Pro-gramming and Its Applications Academic Press, New York, 1978.
Morin, T. L. and Marsten, R. E. Branch and Bound Strategies for Dynamic Pro-gramming. Operations Research 24: 611-627, 1976.
Murtagh, B. A. and Saunders, M. A. MINOS / AUGMENTED Users Manual,Report SOL 80-14, System Optimization Laboratory, Stanford University,1980.
Noonan, F. and Giglio, R. J. Planning Electrical Power Generation : A NonlinearMixed Integer Model Employing Benders Decomposition. Management Sci.23: 946-956, 1977.
Pedroso, J., P. Hybrid Enumeration Strategies for Mixed Integer Programming.Journal of Optimization Theory and Applications, 2004.
Rouhani, R., Lasdon, L., Lebow, W. and Waren, A. D. A Generalized BendersDecomposition Approach to Reactive Source Planning in Power Systems.Mathematical Programming Study 25: 62-75, 1985.
Salkin, H. M. Integer Programming, Addison Wesley, Pub. Co. Inc. Philipines,1975.
Sexton, T. R. and Bodin, L. D. Single Vechicle Many-to-Many Operations withDesired Delivery Times : I. Scheduling, ang II. Routing. Transportation Sci.19: 378-435, 1985.
Shmelev, V. V. Penalty Functions in Linear Integer Programming. Automationand Remote Control (USSR), 36: 1566-1570, 1975.
Sinclair, M. An Exact Penalty Function Approach for Nonlinear Integer Program-ming Problems. EJOR 27: 50-56, 1986.
Stubbs, R. A. and Mehrotra, S. A. A Branch and Cut Method for 0-1 MixedConvex Programming. Math progr. 86:515-532, 1999.
Taha, H. A. Integer Programming: Theory, Applications and Computations, Aca-demic Press, New York, 1975.
Juandi Sidabutar: Pengembangan Algoritma Pencarian Untuk Menyelesaikan Problema Program Taklinier Integer Campuran, 2008. USU e-Repository © 2008
78
Turgeon, A. Optimal Scheduling of Thermal Generating Units. IEEE Trans. onAutomatic Control AC23: 1000-1005.
Weinstein, I. J. and Yu, S. O. Comment on an Integer Maximization Problem.Operations Research 21: 648-650, 1973.
Juandi Sidabutar: Pengembangan Algoritma Pencarian Untuk Menyelesaikan Problema Program Taklinier Integer Campuran, 2008. USU e-Repository © 2008