pengembangan algoritma pencarian untuk menyelesaikan

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


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


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


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


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


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


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


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


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


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


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


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


DAFTAR TABEL

Nomor Judul Halaman

4.1 Hasil Contoh 1 . . . . . . . . . . . . . . . . . . . . . . . . 66

4.2 Hasil Contoh 2 . . . . . . . . . . . . . . . . . . . . . . . . 70

4.3 Hasil Contoh 3 . . . . . . . . . . . . . . . . . . . . . . . . 71

x


DAFTAR GAMBAR

Nomor Judul Halaman

4.1 Struktur Super pada Contoh 1 . . . . . . . . . . . . . . . . 65



xi


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


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


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


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.


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.


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


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.


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


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


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.


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


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


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


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


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


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,


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


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.


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-


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.


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


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.


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


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)


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.


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)


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


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


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)


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.


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.


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


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.


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)


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


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.


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


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.


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-


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)).


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).


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


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


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)


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.


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.


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


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)


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


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.


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)


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.


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


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


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 .


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


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


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.


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.


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∗


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


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)


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.


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.


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


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


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)



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


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-


70

saikan masalah.


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


71

dapat dijelaskan secara eksplisit pd bagian ini. Subroutines CALCFG dan

CALCON dari paket MINOS digunakan untuk menyelesaikan problema.


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).


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


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


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.


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


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.


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.


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.


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.


pengembangan algoritma pencarian untuk menyelesaikan

Documents