Skip to content
Kembali ke hasil pencarian

Pemrograman Integer Deterministik — Optimasi Tepat dengan Variabel Keputusan Integer

Diperkenalkan oleh
Ralph E. Gomory
Tahun
1958
Jenis
Exact combinatorial optimization
Keluarga
Simulation / optimization

Teks ini adalah terjemahan mesin dan belum ditinjau. Baca versi asli dalam bahasa Inggris

Ukuran huruf

Apa fungsinya?

Pemrograman Integer Deterministik (DIP) adalah pendekatan optimasi matematis yang menemukan solusi terbaik untuk masalah di mana beberapa atau semua variabel keputusan harus mengambil nilai integer, dengan data tujuan dan kendala yang sepenuhnya diketahui (deterministik).

Ini adalah bentuk klasik, non-stokastik dari pemrograman integer, yang menjadi dasar riset operasi dan optimasi kombinatorial sejak akhir 1950-an.

Intuisi di balik metode

Banyak keputusan dunia nyata bersifat diskrit: Anda membuka fasilitas atau tidak; Anda menugaskan pekerja ke suatu giliran atau tidak. Metode optimasi kontinu tidak dapat memberlakukan persyaratan bilangan bulat ini. Pemrograman Integer Deterministik menangani hal ini dengan membatasi variabel menjadi integer sementara semua parameter masalah — biaya, kapasitas, permintaan — diketahui dengan pasti. Hasilnya adalah solusi yang tepat, terbukti optimal di bawah asumsi kepastian tersebut, menjadikannya formulasi referensi terhadap varian stokastik dan robust yang dibandingkan.

Sejarah

Pemrograman integer muncul dari pemrograman linear pada akhir 1950-an. Algoritma bidang potong Ralph Gomory tahun 1958 adalah metode tepat sistematis pertama. Bersamaan dengan branch-and-bound (Land dan Doig, 1960), pendekatan ini mendefinisikan bidang tersebut. Kata sifat 'deterministik' membedakan formulasi klasik dari pemrograman integer stokastik (Birge dan Louveaux, 1997) dan menjadi terminologi standar seiring proliferasi varian yang sadar ketidakpastian.

Kapan digunakan

Gunakan Pemrograman Integer Deterministik ketika: (1) variabel keputusan secara inheren diskrit (penugasan, penjadwalan, lokasi fasilitas, pengemasan bin, desain jaringan); (2) semua parameter masalah diketahui dengan pasti atau dapat diperkirakan secara andal sebagai nilai titik; (3) solusi optimal yang tepat diperlukan daripada perkiraan heuristik. JANGAN gunakan ketika: parameter tidak pasti atau bergantung pada skenario (gunakan pemrograman integer stokastik atau robust sebagai gantinya); skala masalah sangat besar sehingga branch-and-bound secara komputasi tidak dapat dipecahkan dan heuristik dapat diterima; variabel benar-benar kontinu (gunakan LP); atau beberapa tujuan yang saling bertentangan harus diseimbangkan secara bersamaan (gunakan pemrograman integer multi-tujuan).

Batasan dan pertimbangan

  • Mengasumsikan semua parameter masalah diketahui secara tepat — ketidakpastian dunia nyata diabaikan berdasarkan desain.
  • NP-hard secara umum; waktu penyelesaian kasus terburuk tumbuh secara eksponensial dengan ukuran masalah.
  • Masalah kombinatorial besar mungkin memerlukan waktu berjam-jam atau berhari-hari untuk komputasi bahkan dengan solver modern.
  • Kualitas formulasi model (kekencangan kendala, pemecahan simetri) sangat memengaruhi waktu penyelesaian.

Syarat dari sumber tidak menggantikan tinjauan ilmiah independen atau validasi oleh mesin analisis.

Kelebihan

  • Menjamin solusi yang terbukti optimal dalam asumsi model deterministik.
  • Secara alami menangani struktur keputusan diskrit, kombinatorial yang tidak dapat ditangani oleh metode kontinu.
  • Didukung oleh solver komersial dan sumber terbuka yang matang dan sangat efisien (CPLEX, Gurobi, SCIP).
  • Menyediakan sertifikat kesenjangan optimalitas, memungkinkan penghentian dini yang berprinsip untuk instansi besar.
  • Berfungsi sebagai formulasi tolok ukur standar emas untuk membandingkan varian heuristik dan stokastik.

Penerapan

  • Perencanaan dan penjadwalan produksi dengan sumber daya mesin atau tenaga kerja diskrit
  • Lokasi fasilitas: memutuskan gudang atau pabrik mana yang akan dibuka
  • Rute kendaraan dan penjadwalan kru dalam transportasi dan logistik
  • Penganggaran modal: memilih portofolio proyek investasi yang tidak dapat dibagi
  • Desain jaringan telekomunikasi dengan biaya penetapan tautan tetap
  • Penyusunan jadwal staf layanan kesehatan dan penjadwalan ruang operasi

Cara kerjanya

Cara kerjanya

1

Definisikan model optimasi: fungsi tujuan untuk diminimalkan (atau dimaksimalkan) sebagai kombinasi linear dari variabel keputusan integer, tunduk pada serangkaian kendala ketidaksetaraan atau kesetaraan linear. Semua koefisien (c, A, b) tetap dan diketahui — inilah yang membuat formulasi menjadi deterministik. Variabel biner (0/1) adalah kasus khusus untuk keputusan ya/tidak.

Rumus
\min \; c^\top x \quad \text{s.t.} \quad Ax \leq b,\; x \geq 0,\; x \in \mathbb{Z}^n
2

Selesaikan relaksasi LP, yang sementara mengizinkan variabel mengambil nilai kontinu. Ini memberikan batas bawah pada tujuan integer optimal. Jika solusi relaksasi LP sudah bernilai integer, itu optimal untuk IP; jika tidak, percabangan dimulai.

Rumus
\text{Solve LP relaxation: } \min \; c^\top x \quad \text{s.t.} \quad Ax \leq b,\; x \geq 0
3

Pilih variabel pecahan dari solusi relaksasi LP dan bagi daerah layak dengan menambahkan kendala lantai (x_j <= nilai bulat ke bawah) pada satu cabang dan kendala langit-langit (x_j >= nilai bulat ke atas) pada cabang lainnya, menghasilkan dua submasalah yang akan diselesaikan secara rekursif.

Rumus
\text{Select fractional variable } x_j^*. \text{ Create two subproblems: } x_j \leq \lfloor x_j^* \rfloor \text{ and } x_j \geq \lceil x_j^* \rceil
4

Selesaikan relaksasi LP setiap submasalah untuk mendapatkan batas. Jika batas suatu node lebih buruk daripada solusi integer terbaik yang diketahui (incumbent), pangkaslah. Jika submasalah menghasilkan solusi yang layak integer yang lebih baik daripada incumbent, perbarui incumbent. Proses ini membentuk pohon pencarian branch-and-bound.

Rumus
\text{Compute bounds; prune nodes where LP bound} \geq \text{incumbent. Update best integer solution.}
5

Metode bidang potong — terutama potongan Gomory — menurunkan ketidaksetaraan linear tambahan dari tabel LP yang dipenuhi oleh semua solusi integer tetapi dilanggar oleh solusi LP pecahan saat ini. Menambahkan potongan ini memperketat relaksasi LP dan mengurangi percabangan. Solvers modern menggabungkan branch-and-bound dengan potongan dalam kerangka kerja branch-and-cut.

Rumus
\text{Optionally add Gomory cuts or problem-specific valid inequalities to tighten LP relaxation.}
6

Algoritma berakhir ketika semua node terbuka dipangkas atau menghasilkan solusi integer. Incumbent pada saat terminasi adalah solusi integer yang terbukti optimal. Solvers juga melaporkan kesenjangan antara batas terbaik dan incumbent, yang dapat digunakan sebagai kriteria penghentian untuk masalah besar.

Rumus
\text{Return optimal integer solution } x^* \text{ with objective value } z^* = c^\top x^*

Kesalahan umum

  • Memperlakukan parameter yang tidak pasti sebagai perkiraan titik deterministik dapat menghasilkan solusi yang berkinerja buruk dalam praktik — validasi asumsi ini sebelum menerapkan DIP.
  • Relaksasi LP yang lemah (kesenjangan integritas besar) menyebabkan pohon branch-and-bound yang sangat besar; investasikan pada ketidaksetaraan yang valid dan reformulasi sebelum meningkatkan skala.
  • Ledakan variabel biner dari formulasi big-M dapat menstabilkan relaksasi LP secara numerik; lebih pilih reformulasi kendala yang lebih ketat.
  • Salah mengartikan kelayakan sebagai optimalitas ketika menggunakan toleransi kesenjangan bukan nol — selalu laporkan kesenjangan bersama dengan nilai tujuan.
  • Mengabaikan simetri dalam model (misalnya, mesin atau pekerja yang identik) menyebabkan percabangan yang berlebihan; tambahkan kendala pemecahan simetri.

Pertanyaan yang sering diajukan

Apa yang membedakan pemrograman integer deterministik dari pemrograman integer stokastik?

Dalam IP deterministik, semua parameter tujuan dan kendala tetap dan diketahui. IP Stokastik secara eksplisit memodelkan parameter yang tidak pasti melalui distribusi probabilitas atau skenario, menghasilkan solusi yang kuat atau optimal dalam ekspektasi di seluruh skenario tersebut. IP Deterministik lebih sederhana dan lebih cepat diselesaikan tetapi mengabaikan ketidakpastian.

Apakah pemrograman biner merupakan kasus khusus dari pemrograman integer?

Ya. Pemrograman biner (0-1) membatasi setiap variabel keputusan ke {0, 1}. Ini adalah kasus khusus yang paling umum, digunakan untuk keputusan ya/tidak seperti apakah akan membuka fasilitas, memilih proyek, atau menugaskan pekerja. Pemrograman integer umum mengizinkan nilai integer non-negatif apa pun.

Kapan saya harus beralih dari IP deterministik ke metode heuristik?

Ketika pohon branch-and-bound terlalu besar untuk dijelajahi dalam batas waktu yang dapat diterima dan kesenjangan optimalitas dari heuristik yang baik (algoritma genetik, simulated annealing, large neighborhood search) dapat ditoleransi untuk aplikasi tersebut. Laporkan dan justifikasi kesenjangan ketika menyimpang dari optimasi tepat.

Bisakah IP deterministik menangani tujuan atau kendala non-linear?

IP deterministik klasik mengasumsikan linearitas (pemrograman linear integer). Pemrograman integer non-linear ada tetapi secara substansial lebih sulit; banyak bentuk non-linear dapat dilinearisasi melalui variabel biner tambahan dan reformulasi big-M. Pemrograman kuadratik integer (QIP) didukung oleh beberapa solver modern secara langsung.

Solver mana yang harus saya gunakan untuk IP deterministik dalam praktik?

Komersial: Gurobi atau IBM CPLEX untuk kinerja terbaik. Akademik/sumber terbuka: SCIP, CBC (melalui COIN-OR), atau HiGHS. Semuanya mengimplementasikan branch-and-cut dengan pra-pemrosesan otomatis. Untuk pengguna Python, PuLP, Pyomo, atau scipy.optimize.milp menyediakan antarmuka pemodelan yang nyaman.

Metode terkait

Sumber

  1. Gomory, R. E. (1958). Outline of an algorithm for integer solutions to linear programs. Bulletin of the American Mathematical Society, 64(5), 275-278.

    Buka referensi DOI
    Disalin.
  2. Wolsey, L. A. (1998). Integer Programming. Wiley-Interscience, New York.

    ISBN: 9780471283669
    Disalin.