Skip to content
Kembali ke hasil pencarian

Pemrograman Campuran-Bilangan Bulat Multi-Objektif

Diperkenalkan oleh
Ehrgott, M.; Mavrotas, G. and others in multi-criteria optimization
Tahun
1980s–2000s
Jenis
Mathematical optimization
Keluarga
Simulation / optimization

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

Ukuran huruf

Apa fungsinya?

Pemrograman Campuran-Bilangan Bulat Multi-Objektif (MO-MIP) adalah kerangka kerja optimasi yang secara simultan mengoptimalkan dua atau lebih fungsi tujuan yang saling bertentangan tunduk pada kendala linear atau non-linear, di mana beberapa variabel keputusan dibatasi pada nilai bilangan bulat dan yang lainnya kontinu.

Kerangka ini banyak diterapkan dalam desain teknik, perencanaan rantai pasok, alokasi sumber daya, dan masalah penjadwalan yang memerlukan pilihan diskrit bersama dengan kuantitas kontinu.

Intuisi di balik metode

Banyak keputusan dunia nyata melibatkan pilihan diskrit (berapa banyak fasilitas yang akan dibuka, proyek mana yang akan didanai, apakah akan membeli mesin) dan keputusan kontinu (berapa banyak yang akan diproduksi, bagaimana mengalokasikan anggaran). Ketika pilihan-pilihan ini memengaruhi banyak tujuan yang saling bertentangan secara bersamaan — misalnya, meminimalkan biaya sambil memaksimalkan tingkat layanan — tidak ada satu solusi optimal tunggal. Sebaliknya, MO-MIP mengeksplorasi batas pertukaran (front Pareto) dari semua solusi yang tidak didominasi, memberikan peta terstruktur dari kompromi yang layak kepada pengambil keputusan daripada satu jawaban yang dipaksakan.

Sejarah

Pemrograman campuran-bilangan bulat diformalkan pada tahun 1950-an–1960-an melalui karya Gomory dan Land serta Doig. Perluasan multi-objektif muncul melalui tahun 1970-an–1980-an ketika para peneliti menyadari bahwa banyak masalah riset operasi dan teknik melibatkan tujuan yang bersaing. Perlakuan sistematis dikonsolidasikan oleh Ehrgott (2005) dan Mavrotas (2009), yang implementasi epsilon-kendala mereka tetap menjadi referensi yang banyak dikutip untuk MO-MIP praktis.

Kapan digunakan

Gunakan MO-MIP ketika masalah keputusan secara alami melibatkan variabel bilangan bulat atau biner (lokasi fasilitas, pemilihan proyek, penjadwalan) bersama dengan kuantitas kontinu, dan ketika dua atau lebih tujuan yang saling bertentangan harus dipertukarkan secara eksplisit. Ini sesuai ketika solusi Pareto yang tepat atau mendekati tepat diperlukan dan sumber daya komputasi memungkinkan pencarian branch-and-bound. JANGAN gunakan ketika semua variabel kontinu (gunakan pemrograman linear atau non-linear multi-objektif sebagai gantinya), ketika skala masalah membuat penyelesaian MIP eksak tidak dapat diatasi dan metaheuristik lebih praktis, atau ketika satu tujuan agregat sudah cukup dan analisis multi-objektif tidak menambah nilai keputusan.

Batasan dan pertimbangan

  • Biaya komputasi tumbuh secara eksponensial dengan jumlah variabel bilangan bulat dan ukuran masalah; instansi besar mungkin tidak dapat diatasi untuk metode eksak.
  • Memerlukan formulasi yang tepat dari semua tujuan dan kendala dalam bentuk matematis, yang mungkin sulit untuk tujuan dunia nyata yang kualitatif atau ambigu.
  • Metode skalarisasi seperti jumlah tertimbang tidak dapat menemukan solusi di wilayah front Pareto yang tidak cembung, berpotensi melewatkan pertukaran penting.
  • Menghasilkan front Pareto yang padat memerlukan penyelesaian banyak submasalah MIP, melipatgandakan total waktu komputasi.
  • Hasil sensitif terhadap formulasi kendala dan akurasi data masalah; model yang tidak layak atau dibatasi dengan buruk tidak menghasilkan keluaran yang berguna.

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

Kelebihan

  • Menyediakan solusi yang terbukti optimal atau mendekati optimal untuk setiap submasalah yang diskalarkan, menjamin kualitas front Pareto untuk ukuran masalah yang dapat diatasi.
  • Secara alami menangani pilihan diskrit dunia nyata (keputusan biner, kuantitas bilangan bulat) yang tidak dapat direpresentasikan secara akurat oleh relaksasi kontinu.
  • Menghasilkan front Pareto lengkap, memberikan informasi pertukaran yang transparan dan terstruktur kepada pengambil keputusan daripada satu kompromi yang dipaksakan.
  • Skalarisasi epsilon-kendala dan skalarisasi sistematis lainnya memungkinkan eksplorasi himpunan solusi yang tidak didominasi secara terkontrol dan padat.
  • Kompatibel dengan berbagai pencari komersial dan sumber terbuka (CPLEX, Gurobi, GLPK, CBC) yang menangani masalah MIP skala besar.

Penerapan

  • Lokasi fasilitas dan desain jaringan rantai pasok: secara simultan meminimalkan biaya dan memaksimalkan cakupan layanan pelanggan dengan variabel buka/tutup biner.
  • Penganggaran modal dan pemilihan portofolio proyek: memaksimalkan pengembalian dan meminimalkan risiko tunduk pada kendala anggaran dan sumber daya dengan variabel pemilihan proyek biner.
  • Penjadwalan produksi: meminimalkan waktu penyelesaian (makespan) dan keterlambatan secara simultan dengan ukuran lot bilangan bulat dan penugasan mesin biner.
  • Perencanaan sistem energi: mengoptimalkan biaya dan emisi CO2 untuk bauran pembangkit listrik dengan keputusan investasi diskrit dan variabel pengiriman kontinu.
  • Alokasi sumber daya layanan kesehatan: memaksimalkan cakupan pasien dan ekuitas sambil meminimalkan pengeluaran menggunakan staf bilangan bulat dan keputusan fasilitas biner.
  • Transportasi dan logistik: meminimalkan waktu tempuh dan emisi secara simultan dengan keputusan armada kendaraan dan rute bilangan bulat.

Cara kerjanya

Cara kerjanya

1

Formulasikan masalah dengan menentukan k fungsi tujuan f_1(x), ..., f_k(x) yang akan diminimalkan atau dimaksimalkan, serangkaian kendala linear atau non-linear Ax <= b, dan domain variabel di mana beberapa variabel bernilai bilangan bulat (misalnya, biner 0/1) dan yang lainnya kontinu. Definisikan batas dan data dengan jelas sebelum menyelesaikan.

2

Terapkan strategi skalarisasi atau dekomposisi untuk mengubah masalah multi-objektif menjadi urutan submasalah MIP berobjektif tunggal. Strategi umum meliputi metode jumlah tertimbang (minimalkan jumlah w_i * f_i), metode epsilon-kendala (optimalkan satu tujuan sambil membatasi yang lain pada tingkat ambang batas), dan fungsi skalarisasi pencapaian.

3

Selesaikan setiap submasalah MIP yang diskalarkan menggunakan pencari eksak branch-and-bound, branch-and-cut, atau lainnya (misalnya, CPLEX, Gurobi, GLPK). Untuk setiap submasalah, pencari mengeksplorasi ruang solusi yang layak bilangan bulat, menerapkan relaksasi LP di setiap node dan memangkas cabang yang tidak layak atau didominasi.

4

Kumpulkan semua solusi yang tidak didominasi di seluruh eksekusi submasalah untuk memperkirakan atau secara tepat membangun front Pareto. Dua solusi tidak didominasi ketika tidak ada yang secara ketat lebih baik dari yang lain pada semua tujuan. Ulangi siklus skalarisasi-penyelesaian dengan parameter yang bervariasi untuk memadatkan front.

5

Sajikan front Pareto kepada pengambil keputusan dengan visualisasi pendukung (plot sebar, plot koordinat paralel). Terapkan aturan keputusan multi-kriteria, preferensi pemangku kepentingan, atau pengurutan leksikografis untuk memilih solusi yang disukai dari himpunan yang tidak didominasi untuk implementasi.

Kesalahan umum

  • Menggunakan metode jumlah tertimbang pada ruang tujuan yang tidak cembung akan melewatkan seluruh segmen front Pareto; lebih pilih fungsi skalarisasi pencapaian epsilon-kendala atau yang diperkuat dalam kasus seperti itu.
  • Memperlakukan variabel bilangan bulat sebagai kontinu dalam relaksasi dan pembulatan setelahnya tidak menjamin Pareto-optimalitas dan dapat menghasilkan solusi yang tidak layak atau didominasi.
  • Mengabaikan pemeriksaan redundansi atau keketatan kendala sebelum menyelesaikan dapat menyebabkan pencari berjalan terlalu lama atau melaporkan ketidaklayakan palsu.
  • Menyajikan semua solusi Pareto kepada pengambil keputusan tanpa penyaringan atau panduan visualisasi menyebabkan kelumpuhan keputusan; selalu sertai hasil dengan dukungan pemilihan yang terstruktur.
  • Mengasumsikan front Pareto lengkap setelah terlalu sedikit eksekusi skalarisasi dapat menyebabkan kesimpulan yang terlalu percaya diri; verifikasi cakupan dengan memeriksa non-dominasi di semua solusi yang dikumpulkan.

Pertanyaan yang sering diajukan

Bagaimana MO-MIP berbeda dari pemrograman linear multi-objektif standar?

Dalam LP multi-objektif semua variabel keputusan kontinu, sehingga solusi Pareto yang efisien dapat ditemukan di simpul-simpul politop cembung. MO-MIP memerlukan beberapa atau semua variabel bernilai bilangan bulat, membuat himpunan yang layak menjadi tidak cembung dan diskrit, yang menuntut pencarian branch-and-bound daripada metode berbasis simpleks.

Bisakah saya menggunakan metaheuristik seperti NSGA-II alih-alih pencari MIP eksak?

Ya, dan untuk masalah skala besar atau kompleks secara kombinatorial, metaheuristik sering kali lebih disukai karena skalabilitasnya lebih baik. Konsekuensinya adalah mereka memberikan front Pareto perkiraan tanpa jaminan optimalitas, sedangkan pencari MO-MIP eksak menjamin non-dominasi untuk solusi yang mereka temukan.

Apa itu metode epsilon-kendala dan mengapa direkomendasikan?

Metode epsilon-kendala mengoptimalkan satu tujuan sambil membatasi semua tujuan lain agar tidak lebih buruk dari batas yang ditentukan (epsilon). Metode ini dapat menemukan solusi di wilayah Pareto yang tidak cembung yang terlewatkan oleh metode jumlah tertimbang, menjadikannya lebih andal untuk masalah MO-MIP umum.

Berapa banyak solusi Pareto yang harus saya hasilkan?

Tergantung pada jumlah tujuan dan resolusi yang dibutuhkan untuk pengambilan keputusan. Untuk dua tujuan, 20–50 solusi yang berjarak sama biasanya cukup untuk mengkarakterisasi front. Untuk tiga tujuan atau lebih, jumlahnya tumbuh secara kombinatorial; metode interaktif atau yang dipandu preferensi direkomendasikan untuk menghindari kelebihan beban solusi.

Apakah MO-MIP cocok untuk masalah dengan ketidakpastian dalam data?

MO-MIP standar mengasumsikan data deterministik. Ketika data masukan tidak pasti, MO-MIP harus digabungkan dengan ekstensi optimasi robust atau pemrograman stokastik — misalnya, MO-MIP stokastik dua tahap atau MO-MIP robust dengan batas tujuan kasus terburuk.

Metode terkait

Sumber

  1. Ehrgott, M. (2005). Multicriteria Optimization (2nd ed.). Springer, Berlin.

    ISBN: 9783540213987
    Disalin.
  2. Mavrotas, G. (2009). Effective implementation of the epsilon-constraint method in Multi-Objective Mathematical Programming problems. Applied Mathematics and Computation, 213(2), 455-465.

    Buka referensi DOI
    Disalin.