Pemrograman Bilangan Bulat

Pemrograman bilangan bulat (PBB; Ingg. integer programming, IP) — adalah cabang optimasi matematika yang mengkaji masalah-masalah di mana sebagian atau seluruh variabel harus mengambil nilai bilangan bulat saja.

Kasus khusus yang paling banyak dipelajari adalah pemrograman linear bilangan bulat (PLBB; Ingg. integer linear programming, ILP), di mana fungsi tujuan dan kendalanya bersifat linear. Berbeda dengan pemrograman linear, di mana variabel dapat mengambil nilai riil sembarang, persyaratan bilangan bulat membuat masalah PBB jauh lebih sulit untuk diselesaikan.

Pemrograman bilangan bulat banyak diterapkan dalam ekonomi, logistik, perencanaan produksi, dan bidang-bidang lain di mana variabel secara alami bersifat diskret (misalnya, jumlah unit produk yang dihasilkan atau jumlah tenaga kerja).

Definisi dan Terminologi

Masalah umum pemrograman linear bilangan bulat dapat dituliskan sebagai berikut:

Cari vektor $x$ yang:

memaksimalkan (atau meminimalkan) $c^{T}x$

dengan kendala:

$Ax\le b$

$x\ge 0$

$x\in {\mathbb{Z}}^n$ (semua komponen vektor $x$ adalah bilangan bulat)

di mana $x$ — vektor variabel, $c$ dan $b$ — vektor, serta $A$ — matriks koefisien.

Berdasarkan persyaratan terhadap variabel, dibedakan jenis-jenis masalah berikut:

• Pemrograman bilangan bulat penuh: semua variabel harus berupa bilangan bulat.
• Pemrograman bilangan bulat campuran (Ingg. mixed-integer programming, MIP): hanya sebagian variabel yang harus berupa bilangan bulat.
• Pemrograman Boolean (0-1): variabel hanya mengambil nilai 0 atau 1, yang memungkinkan pemodelan keputusan logis bertipe "ya/tidak".

Sifat-Sifat Utama dan Kompleksitas

Kompleksitas Komputasi

Masalah pemrograman linear bilangan bulat dalam kasus umum bersifat NP-sulit. Ini berarti tidak ada algoritma yang diketahui mampu menemukan solusi optimal yang tepat untuk sembarang masalah PBB dalam waktu polinomial. Kompleksitas ini disebabkan oleh sifat kombinatorial dari masalah tersebut, karena jumlah solusi bilangan bulat yang mungkin dapat tumbuh secara eksponensial seiring bertambahnya jumlah variabel.

Hubungan dengan Pemrograman Linear (Relaksasi LP)

Untuk setiap masalah PBB, dapat dirumuskan relaksasi linearnya — masalah pemrograman linear (LP) di mana persyaratan bilangan bulat diabaikan. Solusi relaksasi LP memiliki dua sifat penting:

1. Solusi tersebut dapat ditemukan jauh lebih cepat (dalam waktu polinomial).
2. Nilai optimal fungsi tujuan dari relaksasi LP memberikan estimasi (batas atas untuk masalah maksimasi dan batas bawah untuk minimasi) bagi nilai optimal masalah bilangan bulat asal.

Namun, pembulatan sederhana solusi fraksional dari relaksasi LP ke bilangan bulat terdekat, pada umumnya, tidak menghasilkan solusi optimal atau bahkan solusi yang layak bagi masalah bilangan bulat.

Sifat Unimodularitas Total

Terdapat kelas penting dari masalah PLBB yang dapat diselesaikan semudah relaksasi LP-nya. Ini adalah masalah-masalah di mana matriks kendala $A$ bersifat unimodular total (yaitu determinan dari setiap submatriks persegi adalah 0, +1, atau −1). Jika matriks $A$ unimodular total dan vektor $b$ berupa bilangan bulat, maka semua titik sudut dari polihedron solusi layak relaksasi LP secara otomatis akan berupa bilangan bulat. Oleh karena itu, solusi yang ditemukan dengan metode simpleks akan berupa bilangan bulat. Contoh masalah semacam itu adalah masalah transportasi dan masalah penugasan.

Metode Penyelesaian

Untuk menyelesaikan masalah PBB umum yang tidak memiliki sifat unimodularitas total, telah dikembangkan metode-metode eksak yang didasarkan pada gagasan pencacahan implisit.

• Metode cabang dan batas (Ingg. Branch and Bound) — metode eksak utama yang didasarkan pada pemecahan sistematis himpunan solusi layak menjadi himpunan-himpunan bagian (pencabangan) dan pemangkasan himpunan bagian yang jelas tidak memuat solusi optimal. Relaksasi LP digunakan untuk menilai prospek himpunan bagian tersebut.

• Metode bidang potong (metode Gomory; Ingg. Cutting Plane Method) — pendekatan iteratif yang secara berurutan menambahkan kendala linear baru ("potongan") ke dalam masalah. Potongan-potongan ini "memotong" solusi fraksional dari relaksasi LP tanpa menghilangkan satu pun solusi bilangan bulat yang layak, sehingga secara bertahap mendekatkan himpunan solusi layak dari relaksasi LP ke selubung cembung dari solusi-solusi bilangan bulat.

Solvers modern pada umumnya menggunakan algoritma hibrida, seperti metode cabang dan potong (Ingg. Branch and Cut), yang menggabungkan keunggulan kedua pendekatan tersebut.

Contoh dan Bidang Penerapan

Pemrograman bilangan bulat memungkinkan pemodelan berbagai masalah klasik dalam optimasi kombinatorial.

• Masalah ransel (knapsack problem): masalah klasik pemrograman 0-1, di mana harus dipilih sekumpulan barang dengan nilai total maksimum tanpa melebihi batas berat keseluruhan.
• Masalah penjual keliling (travelling salesman problem): masalah pencarian rute terpendek yang melewati sekumpulan kota tertentu. Dapat dirumuskan sebagai masalah pemrograman bilangan bulat, di mana variabel menentukan apakah suatu sisi graf dimasukkan ke dalam rute akhir.

Berkat fleksibilitasnya, PBB merupakan salah satu alat yang paling banyak digunakan dalam riset operasi dan diterapkan di bidang-bidang seperti:

• Logistik dan manajemen rantai pasok: optimasi rute transportasi, penempatan gudang, manajemen persediaan.
• Perencanaan produksi: penyusunan jadwal produksi, alokasi sumber daya, pemanfaatan peralatan.
• Keuangan dan ekonomi: pembentukan portofolio investasi, penganggaran modal.
• Telekomunikasi dan energi: perancangan jaringan komunikasi, perencanaan operasi unit pembangkit listrik.

Lihat Pula

• Pemrograman linear
• Metode cabang dan batas

Catatan

</references>