Pemrograman Integer Campuran — Optimasi Tepat atas Keputusan Kontinu dan Integer
- Diperkenalkan oleh
- Ralph Gomory (branch-and-bound cuts, 1958); Land & Doig (branch-and-bound, 1960)
- Tahun
- 1958–1960
- Jenis
- Mathematical optimization
- Keluarga
- Simulation / optimization
Teks ini adalah terjemahan mesin dan belum ditinjau. Baca versi asli dalam bahasa Inggris
Apa fungsinya?
Pemrograman Integer Campuran (MIP) adalah kerangka kerja optimasi matematis di mana beberapa variabel keputusan harus mengambil nilai integer sementara yang lain dapat berupa kontinu.
Ini menggeneralisasi pemrograman linear dan banyak digunakan dalam riset operasi, logistik, penjadwalan, alokasi sumber daya, dan desain teknik, di mana kendala ketidakdapatdibagi — seperti keputusan ya/tidak atau kuantitas unit utuh — muncul secara alami.
Intuisi di balik metode
Banyak masalah optimasi nyata melibatkan keputusan yang tidak dapat dibagi — Anda membuka fasilitas atau tidak, Anda menugaskan tepat satu pekerja ke suatu shift, Anda memesan unit utuh. Pemrograman linear kontinu mengabaikan realitas ini dan dapat menghasilkan jawaban pecahan yang tidak dapat diimplementasikan. MIP memberlakukan integrality secara langsung dalam model. Pemecah menjelajahi ruang solusi integer layak secara sistematis melalui branch-and-bound: ia memecahkan submasalah kontinu yang direlaksasi untuk membatasi solusi terbaik yang mungkin di setiap wilayah, membuang wilayah yang tidak dapat meningkatkan solusi integer terbaik yang ditemukan sejauh ini, dan menambahkan bidang potong untuk memperketat pencarian. Hasilnya adalah rencana yang terbukti optimal atau mendekati optimal.
Sejarah
Dasar-dasar pemrograman integer diletakkan oleh Ralph Gomory, yang memperkenalkan metode cutting-plane pada tahun 1958, dan oleh Land dan Doig, yang memformalkan branch-and-bound pada tahun 1960. Dekade berikutnya menyaksikan pengembangan teori relaksasi LP, kombinatorik polihedral (Edmonds, Padberg, Grötschel), dan pada tahun 1990-an pemecah komersial membuat MIP skala besar menjadi praktis. Bidang ini dibahas secara komprehensif dalam Nemhauser dan Wolsey (1988) dan Wolsey (1998).
Kapan digunakan
Gunakan MIP ketika masalah Anda memiliki tujuan dan kendala linear atau dapat dilinearisasi dan mencakup keputusan yang harus bernilai integer (lokasi fasilitas, penjadwalan kru, penganggaran modal, desain jaringan, masalah pemotongan stok). Ini adalah metode pilihan ketika Anda memerlukan solusi yang terbukti optimal atau dengan celah terbatas dan ukuran masalah dapat dikelola (ribuan variabel dengan pemecah modern). JANGAN gunakan MIP ketika tujuan atau kendala sangat non-linear (gunakan pemrograman non-linear atau non-linear integer campuran sebagai gantinya), ketika masalahnya sangat besar sehingga metode eksak tidak mungkin dilakukan (pertimbangkan heuristik atau metaheuristik), atau ketika aproksimasi kontinu sudah cukup akurat (gunakan LP untuk kecepatan).
Batasan dan pertimbangan
- Kompleksitas kasus terburuk adalah NP-hard; waktu penyelesaian dapat tumbuh secara eksponensial dengan jumlah variabel integer.
- Memerlukan formulasi matematis yang tepat; model yang diformulasikan dengan buruk dapat menjadi sulit dipecahkan bahkan ketika masalah yang mendasarinya dapat dikelola.
- Elemen non-konveks atau non-linear memerlukan linearisasi tambahan atau pemecah khusus, meningkatkan kompleksitas model.
- Biaya lisensi pemecah bisa signifikan untuk alat komersial, meskipun ada alternatif sumber terbuka berkualitas tinggi.
- Hasil hanya sebaik model: spesifikasi kendala yang salah mengarah pada optimum yang tidak berarti.
Syarat dari sumber tidak menggantikan tinjauan ilmiah independen atau validasi oleh mesin analisis.
Kelebihan
- Menghasilkan solusi yang terbukti optimal dengan celah optimalitas yang dapat dikuantifikasi, memungkinkan justifikasi keputusan yang ketat.
- Menangani variabel biner dan integer umum secara native, menangkap ketidakdapatdibagi dan kendala logis dunia nyata.
- Pemecah modern (Gurobi, CPLEX, SCIP) memanfaatkan branch-and-bound canggih, bidang potong, dan presolve untuk menangani instansi besar secara efisien.
- Formulasi model yang transparan membuat asumsi eksplisit dan dapat diaudit oleh pakar domain.
- Mendukung analisis sensitivitas dan studi parametrik untuk memahami bagaimana solusi berubah dengan data input.
- Didukung secara luas oleh bahasa pemodelan (AMPL, GAMS, Pyomo, JuMP) yang memungkinkan prototipe cepat.
Penerapan
- Rantai pasokan dan logistik: rute kendaraan, lokasi fasilitas, dan optimasi inventaris dengan kuantitas pengiriman integer.
- Penjadwalan tenaga kerja: rostering perawat, penugasan kru, dan perencanaan shift dengan variabel penugasan biner.
- Penganggaran modal: memilih portofolio proyek investasi yang tidak dapat dibagi tunduk pada kendala anggaran.
- Desain telekomunikasi dan jaringan: ekspansi kapasitas dan perutean dengan keputusan aktivasi tautan biner.
- Sistem energi: komitmen unit dalam jaringan listrik yang memutuskan generator mana yang akan dinyalakan atau dimatikan setiap jam.
- Manufaktur: lot-sizing produksi, penjadwalan mesin, dan masalah pemotongan stok dengan ukuran batch integer.
Cara kerjanya
Cara kerjanya
Definisikan model optimasi: fungsi tujuan (kombinasi linear dari variabel keputusan untuk diminimalkan atau dimaksimalkan), kendala ketidaksetaraan dan kesetaraan linear, dan persyaratan integrality. Variabel kontinu menangani kuantitas yang dapat berupa pecahan; variabel biner (0/1) atau integer umum menangani keputusan diskrit.
Rumus
\min_{x,y}\; c^\top x + d^\top y \quad \text{s.t.}\; Ax + By \leq b,\; x \geq 0,\; y \in \mathbb{Z}^pSelesaikan relaksasi LP dengan sementara menjatuhkan kendala integrality. Ini memberikan batas bawah (untuk minimisasi) pada tujuan MIP optimal dan solusi kandidat yang mungkin berupa pecahan.
Rumus
\text{LP relaxation: replace } y \in \mathbb{Z}^p \text{ with } y \geq 0Pilih variabel integer pecahan dari solusi relaksasi LP. Buat dua submasalah anak dengan menambahkan kendala lantai di satu dan kendala langit-langit di yang lain, mempartisi ruang layak tanpa kehilangan titik layak integer apa pun.
Rumus
\text{Select fractional } y_j^*; \text{ create subproblems: } y_j \leq \lfloor y_j^* \rfloor \text{ and } y_j \geq \lceil y_j^* \rceilSelesaikan relaksasi LP dari setiap submasalah. Jika batas lebih buruk daripada solusi integer terbaik yang ditemukan sejauh ini (incumbent), pangkas cabang tersebut. Jika solusi LP kebetulan layak integer, perbarui incumbent jika meningkatkan tujuan.
Rumus
\text{Prune node if LP bound} \geq \text{incumbent; update incumbent when integer-feasible solution found}Secara opsional tambahkan bidang potong — ketidaksetaraan yang valid yang memotong solusi LP pecahan tanpa menghilangkan titik layak integer apa pun. Potongan Gomory adalah pendekatan klasik; potongan spesifik masalah (misalnya, potongan clique, potongan aliran) dapat secara dramatis mengurangi ukuran pohon.
Rumus
\text{Add Gomory or problem-specific cutting planes to tighten LP relaxation before branching}Berhenti ketika pohon branch-and-bound sepenuhnya dieksplorasi atau ketika celah antara solusi integer terbaik dan batas bawah global jatuh dalam toleransi yang ditentukan pengguna (misalnya, 0,01%). Kembalikan solusi incumbent dengan sertifikat optimalitasnya.
Rumus
\text{Stop when all nodes pruned; return incumbent } x^*, y^* \text{ with optimality gap} \leq \epsilonKesalahan umum
- Memilih toleransi celah optimalitas yang terlalu ketat dapat membuat pemecah berjalan tanpa batas; selalu tetapkan celah praktis (misalnya, 1%) untuk instansi besar.
- Simetri dalam model (misalnya, fasilitas yang dapat dipertukarkan) menciptakan cabang yang berlebihan dan memperbesar pohon pencarian — gunakan kendala pemecah simetri.
- Relaksasi LP yang lemah (celah integrality besar) mengarah pada pohon branch-and-bound yang sangat besar; investasikan waktu dalam menambahkan ketidaksetaraan yang valid atau memperketat formulasi.
- Memperlakukan semua variabel sebagai integer ketika hanya beberapa yang perlu adalah biaya yang tidak perlu; gunakan variabel biner hanya di mana kendala logis menuntutnya.
- Mengabaikan warm-starting dengan solusi layak awal yang baik membuang waktu pemecah untuk menemukan incumbent pertama.
Pertanyaan yang sering diajukan
Bagaimana MIP berbeda dari pemrograman linear (LP)?
LP mensyaratkan semua variabel keputusan bersifat kontinu (bernilai riil), yang dapat menghasilkan solusi pecahan yang secara fisik tidak layak (misalnya, 2,7 truk). MIP menambahkan kendala integrality pada beberapa atau semua variabel, memberlakukan solusi bilangan bulat atau biner dengan biaya kompleksitas komputasi yang lebih besar.
Kapan saya harus menggunakan heuristik alih-alih MIP?
Ketika masalah memiliki jutaan variabel, struktur yang sangat non-linear, atau memerlukan solusi mendekati waktu nyata, MIP eksak mungkin terlalu lambat. Metaheuristik (algoritma genetik, simulated annealing) dapat menghasilkan solusi yang baik dengan cepat, tetapi tanpa jaminan optimalitas. MIP lebih disukai ketika sertifikasi kualitas solusi penting.
Apa itu celah optimalitas dan seberapa kecil seharusnya?
Celah adalah (objektif incumbent - batas LP) / batas LP, dinyatakan sebagai persentase. Ini menyatakan seberapa jauh solusi integer terbaik yang diketahui dari optimum sebenarnya. Untuk sebagian besar aplikasi praktis, celah 0,1–1% sudah cukup; celah yang lebih ketat membutuhkan waktu pemecah secara eksponensial lebih banyak.
Bisakah MIP menangani tujuan atau kendala non-linear?
MIP standar mengasumsikan linearitas. Hubungan non-linear harus dilinearisasi (misalnya, aproksimasi linear-potongan, ekspansi biner dari produk) atau ditangani oleh pemecah pemrograman non-linear integer campuran (MINLP), yang secara signifikan lebih sulit dipecahkan.
Pemecah mana yang direkomendasikan untuk MIP?
Komersial: Gurobi dan CPLEX adalah tolok ukur industri. Sumber terbuka: SCIP, CBC (melalui COIN-OR), dan HiGHS kompetitif untuk masalah berukuran sedang. Semua mendukung antarmuka pemodelan standar seperti AMPL, Pyomo, dan JuMP.
Metode terkait
Sumber
Nemhauser, G. L., Wolsey, L. A. (1988). Integer and Combinatorial Optimization. Wiley-Interscience, New York.
ISBN: 9780471359432Disalin.Wolsey, L. A. (1998). Integer Programming. Wiley-Interscience, New York.
ISBN: 9780471283669Disalin.