Pemrograman Integer — IP dan Pemrograman Integer Campuran (MIP)
- Diperkenalkan oleh
- Ralph Gomory (cutting planes, 1958); land-and-doig branch-and-bound (1960)
- Tahun
- 1958
- Jenis
- Mathematical optimisation — exact combinatorial method
Teks ini adalah terjemahan mesin dan belum ditinjau. Baca versi asli dalam bahasa Inggris
Apa fungsinya?
Pemrograman integer (IP), juga disebut pemrograman integer campuran (MIP) ketika hanya beberapa variabel yang dibatasi pada bilangan bulat, adalah cabang optimasi matematis di mana beberapa atau semua variabel keputusan harus mengambil nilai integer atau biner.
Dibangun di atas pemrograman linear, ini diformalkan melalui metode cutting-plane Ralph Gomory (1958) dan algoritma branch-and-bound Land-dan-Doig (1960), dan sejak itu menjadi kerangka kerja eksak standar untuk masalah penjadwalan, penugasan, perutean, dan alokasi sumber daya.
Intuisi di balik metode
Pemrograman linear biasa menemukan titik terbaik dalam wilayah layak yang kontinu. Namun, banyak keputusan nyata bersifat diskrit — Anda tidak dapat mempekerjakan 2,7 perawat atau membuka setengah gudang. Pemrograman integer menambahkan kendala bahwa beberapa atau semua variabel harus berupa bilangan bulat (atau pilihan biner 0/1). Harga dari kendala tersebut adalah komputasi: himpunan layak tidak lagi merupakan permukaan yang mulus tetapi himpunan titik yang tersebar, dan menemukan yang terbaik dapat memerlukan pemeriksaan sejumlah besar solusi kandidat. Solver mengelola ini dengan secara cerdas membagi masalah menjadi sub-masalah yang lebih kecil (branching) dan memangkas cabang yang tidak dapat mengalahkan solusi terbaik yang ditemukan sejauh ini (bounding), sambil juga memperketat aproksimasi kontinu melalui ketidaksetaraan tambahan (cutting planes).
Sejarah
Pemrograman integer muncul pada akhir 1950-an ketika para peneliti berusaha memperluas pemrograman linear ke keputusan diskrit. Ralph Gomory memperkenalkan metode cutting-plane sistematis pada tahun 1958, membuktikan bahwa setiap program integer secara prinsip dapat diselesaikan dengan menambahkan sejumlah potongan yang terbatas. Land dan Doig (1960) memformalkan branch-and-bound, yang menjadi algoritma eksak dominan. Wolsey (1998) dan Nemhauser dan Wolsey (1988) memberikan perlakuan buku teks kanonik yang masih diandalkan oleh bidang ini. Revolusi praktis datang dengan pengembangan solver branch-and-cut pada tahun 1990-an, menggabungkan kedua teknik dengan heuristik canggih, dan kemudian dengan ledakan kinerja solver komersial dan open-source yang memungkinkan aplikasi dunia nyata skala besar saat ini.
Kapan digunakan
Gunakan pemrograman integer ketika keputusan secara inheren diskrit — pilihan ya/tidak biner, kuantitas integer, atau kendala logika aktif/nonaktif — dan ketika Anda memerlukan solusi optimal yang tepat atau mendekati tepat dengan batas kualitas yang dapat dibuktikan. Ini cocok untuk penjadwalan, penugasan kru dan sumber daya, perutean kendaraan, lokasi fasilitas, penganggaran modal, dan pemilihan portofolio. Tidak ada persyaratan ukuran sampel minimum karena IP adalah kerangka kerja optimasi deterministik daripada prosedur inferensi statistik. Tipe variabel dapat berupa biner, kategorikal (dikodekan sebagai biner), atau kontinu (dalam kasus integer campuran). Persyaratan praktis utama adalah bahwa masalah dapat dimodelkan dengan tujuan linear dan kendala linear; jika tujuan atau kendala non-linear, ekstensi pemrograman non-linear integer campuran (MINLP) diperlukan.
Batasan dan pertimbangan
- Pemrograman integer bersifat NP-hard secara umum; waktu penyelesaian dapat tumbuh secara eksponensial dengan ukuran masalah dan formulasi yang buruk.
- Relaksasi LP yang lemah (kesenjangan integritas besar) mengarah pada pohon pencarian yang dalam dan mahal serta waktu berjalan yang lama.
- Ekspansi biner dari variabel kategorikal dengan kardinalitas besar dapat meledakkan ukuran model.
- Untuk instans yang sangat besar, solver mungkin perlu dihentikan lebih awal dengan toleransi kesenjangan daripada mencapai kesenjangan nol.
Syarat dari sumber tidak menggantikan tinjauan ilmiah independen atau validasi oleh mesin analisis.
Kelebihan
- Menghasilkan solusi optimal yang tepat dengan kesenjangan optimalitas yang tersertifikasi, tidak seperti heuristik yang tidak menawarkan jaminan kualitas.
- Menangani variabel biner dan integer umum secara native, menjadikannya kerangka kerja alami untuk keputusan kombinatorial.
- Berlaku di berbagai masalah domain — penjadwalan, perutean, penugasan, tas punggung — dengan mesin matematis yang sama.
- Solver branch-and-cut modern dapat menyelesaikan masalah dengan jutaan variabel dan kendala yang puluhan tahun lalu tidak dapat dipecahkan.
Penerapan
- Penjadwalan staf dan perawat — menugaskan shift untuk memenuhi persyaratan cakupan sambil menghormati peraturan jam kerja.
- Perutean dan logistik kendaraan — menemukan rute pengiriman dengan biaya minimum di bawah kendala kapasitas dan jendela waktu.
- Lokasi fasilitas — memutuskan gudang atau pabrik mana yang akan dibuka untuk meminimalkan total biaya distribusi.
- Penganggaran modal — memilih portofolio proyek investasi dalam anggaran untuk memaksimalkan total pengembalian.
- Perencanaan produksi — menentukan ukuran lot integer di berbagai periode waktu untuk menyeimbangkan biaya penyiapan dan biaya penyimpanan.
- Desain jaringan — memilih tautan mana yang akan dipasang dalam jaringan komunikasi atau transportasi.
Cara kerjanya
Cara kerjanya
Masalah ini disajikan sebagai program matematis: definisikan variabel keputusan (yang harus dinyatakan sebagai integer atau biner jika masalah memerlukannya), tulis fungsi objektif linear untuk diminimalkan atau dimaksimalkan, dan daftarkan semua kendala linear. Formulasi yang ketat — yang relaksasi kontinu (LP) nya sedekat mungkin dengan optimum integer yang sebenarnya — secara dramatis mengurangi waktu penyelesaian.
Pembatasan integritas sementara dihilangkan untuk mendapatkan relaksasi LP. Menyelesaikan relaksasi ini cepat dan menghasilkan batas: nilai optimalnya selalu setidaknya sebaik optimum integer yang sebenarnya (batas bawah untuk minimisasi). Jika solusi relaksasi kebetulan semuanya integer, masalahnya terpecahkan. Jika tidak, kesenjangan antara relaksasi dan integritas memandu pencarian.
Variabel pecahan dalam solusi relaksasi dipilih dan masalah dibagi menjadi dua sub-masalah — satu mengharuskan variabel tersebut dibulatkan ke bawah, satu dibulatkan ke atas. Setiap sub-masalah direlaksasi dan diselesaikan, menciptakan pohon pencarian. Cabang yang batas relaksasinya lebih buruk daripada solusi integer terbaik yang ditemukan sejauh ini dipangkas tanpa eksplorasi lebih lanjut.
Cutting planes adalah ketidaksetaraan linear yang valid yang memotong sebagian dari wilayah layak relaksasi LP tanpa menghilangkan titik layak integer. Menambahkan potongan kuat (potongan Gomory, ketidaksetaraan penutup, potongan klik) memperketat batas LP dan mengurangi jumlah node yang harus dieksplorasi oleh solver.
Solusi layak integer terbaik yang ditemukan di semua node yang dieksplorasi dikembalikan sebagai optimum. Kesenjangan optimalitas — perbedaan persentase antara solusi integer terbaik dan batas tersisa terbaik — dilaporkan; kesenjangan nol mensertifikasi optimalitas global. Untuk instans NP-hard yang besar, solver dapat berhenti lebih awal dengan toleransi kesenjangan yang ditentukan pengguna, mengembalikan solusi yang mendekati optimal dengan batas yang dapat dibuktikan.
Kesalahan umum
- Menyatakan variabel sebagai kontinu padahal seharusnya integer — atau sebaliknya — secara diam-diam menghasilkan solusi yang salah; selalu verifikasi tipe variabel sesuai dengan realitas fisik masalah.
- Formulasi yang longgar dengan kesenjangan relaksasi LP yang besar menyebabkan percabangan yang berlebihan; investasikan waktu dalam pengetatan formulasi (ketidaksetaraan kuat, pemecahan simetri) sebelum menyelesaikan.
- Mengabaikan kesenjangan integritas dalam keluaran solver: nilai objektif yang dilaporkan hanyalah solusi integer terbaik yang ditemukan, belum tentu optimum global kecuali kesenjangannya nol.
- Menerapkan IP pada masalah yang tujuan atau kendalanya non-linear tanpa perlakuan MINLP yang sesuai akan menghasilkan model yang salah.
- Untuk masalah penjadwalan atau perutean, gagal menambahkan ketidaksetaraan yang valid (seperti potongan klik atau penutup) akan meninggalkan keuntungan kinerja yang substansial.
Pertanyaan yang sering diajukan
Apa perbedaan antara IP dan MIP?
Dalam pemrograman integer murni (IP) setiap variabel keputusan harus berupa integer. Dalam pemrograman integer campuran (MIP), beberapa variabel adalah integer atau biner sementara yang lain diizinkan kontinu. MIP adalah kerangka kerja yang lebih umum dan lebih sering digunakan dalam praktik, karena sebagian besar masalah nyata mencampur pilihan diskrit dengan kuantitas kontinu.
Mengapa pemrograman integer NP-hard jika pemrograman linear polinomial?
Pemrograman linear mengoptimalkan atas politop cembung dan dapat diselesaikan dalam waktu polinomial oleh metode simpleks atau titik interior. Menambahkan kendala integritas menghancurkan konveksitas ini: himpunan layak menjadi himpunan titik integer yang terbatas tetapi berpotensi sangat besar, dan tidak ada algoritma waktu polinomial yang diketahui untuk menemukan yang terbaik secara umum. Relaksasi LP memberikan batas tetapi bukan solusi langsung.
Bagaimana saya tahu apakah solusi saya optimal?
Solver melaporkan kesenjangan optimalitas — perbedaan persentase antara solusi integer terbaik yang ditemukan dan batas bawah tersisa terbaik. Kesenjangan 0% mensertifikasi optimalitas global. Untuk masalah besar Anda dapat mengatur toleransi kesenjangan (misalnya, 1%) dan menerima solusi yang mendekati optimal; batasnya masih menjamin bahwa optimum yang sebenarnya tidak bisa lebih baik dari persentase tersebut.
Apa yang membuat formulasi 'ketat' dan mengapa itu penting?
Formulasi yang ketat adalah yang relaksasi LP-nya memberikan batas yang dekat dengan optimum integer, menyisakan kesenjangan integritas yang kecil. Ketika kesenjangan kecil, branch-and-bound perlu mengeksplorasi lebih sedikit node dan selesai lebih cepat. Menambahkan ketidaksetaraan yang valid seperti potongan Gomory, ketidaksetaraan penutup, atau potongan klik memperketat formulasi dan seringkali merupakan cara paling berdampak untuk mempercepat solver.
Metode terkait
Sumber
Wolsey, L.A. (1998). Integer Programming. Wiley.
ISBN: 9780471283669Disalin.Nemhauser, G.L. & Wolsey, L.A. (1988). Integer and Combinatorial Optimization. Wiley.
ISBN: 9780471359432Disalin.