Penyelesaian LP Lanjutan

Terlepas dari kematangan teknologi LP, beberapa kasus penggunaan memerlukan teknik yang lebih canggih. Misalnya, tersedia berbagai implementasi dan algoritma LP, yang masing-masing memiliki kelebihan dan kekurangan. Selain itu, ketidakstabilan numerik dapat menyebabkan pemecah perlambat atau gagal memecahkan model tertentu.

Panduan ini memperkenalkan konsep dan memberikan contoh untuk membantu Anda mendapatkan performa dan keandalan terbaik dari pemecah masalah LP.

Konsep

Bagian ini menyajikan konsep utama untuk penggunaan lanjutan pemecah LP. Kami berasumsi bahwa pembaca sudah memahami konsep dualitas di LP.

Keluarga algoritma LP

Kelas algoritma untuk LP berikut dapat diakses melalui OR-Tools.

  1. Algoritma Simplex adalah algoritma LP praktis pertama dan tetap yang paling populer. Algoritma berjalan di sepanjang verteks (titik sudut) dari wilayah yang layak, secara berulang meningkatkan nilai fungsi objektif hingga mencapai solusi yang optimal. Ada dua jenis algoritma {i>simpleks<i}:

    1. simpleks primal mengambil langkah-langkah di sepanjang verteks dari wilayah primal yang valid. Varian ini sangat efektif dalam memecahkan urutan masalah LP dengan berbagai fungsi objektif, yaitu, di mana wilayah dasar yang layak diperbaiki.
    2. simpleks ganda mengambil langkah-langkah di sepanjang verteks dari region yang layak untuk dual. Varian ini sangat efektif dalam memecahkan urutan masalah LP dengan region ganda yang memungkinkannya diperbaiki, misalnya, saat hanya batas pada variabel yang berubah. Karena alasan ini, simplex ganda digunakan secara luas dalam pemecah masalah MIP.

  2. Metode Barrier atau interior-point adalah kelompok algoritma praktis kedua untuk LP. Metode penghalang memasangkan jaminan teoritis konvergensi efisien (waktu polinomial) dengan performa yang andal dalam praktiknya. Metode ini melengkapi algoritma simpleks yang performanya buruk; misalnya, beberapa pemecah pemecahan menawarkan untuk menjalankan simplex dan penghalang secara paralel, yang mengembalikan solusi dari algoritme yang selesai terlebih dahulu.

  3. Metode urutan pertama adalah kelompok algoritma yang menggunakan informasi gradien secara eksklusif (yaitu, turunan urutan pertama) untuk memandu iterasi. Penurunan gradien adalah contoh yang terkenal. Metode ini populer dalam pengoptimalan nonlinear dan machine learning. Untuk LP, metode urutan pertama dapat menskalakan masalah yang lebih besar daripada simplex dan batasan, dan mungkin juga memiliki persyaratan memori yang jauh lebih kecil. Di sisi lain, mereka lebih sensitif terhadap masalah numerik dan mungkin berjuang untuk mendapatkan solusi yang sangat akurat.

Tabel di bawah mencantumkan pemecah LP yang tersedia di OR-Tools dan menunjukkan mana dari tiga kelompok algoritma yang diimplementasikan di setiap pemecah.

Pemecah soal Simpleks Barrier Urutan pertama
KLP X X
CPLEXK X X
GlopG X
GLPK X X
GurobiS X X
PDLPG X
XpressL X X

G menunjukkan pemecah masalah dikembangkan oleh Google. L menunjukkan bahwa pemecah masalah memerlukan lisensi yang dikeluarkan oleh developer pihak ketiga masing-masing.

Lihat Rekomendasi untuk mendapatkan saran pemecah masalah dan algoritma yang akan digunakan.

Apa arti pemecahan masalah?

Untuk mendapatkan hasil maksimal dari pemecah LP, penting untuk memahami apa yang tersirat ketika pemecah masalah mengklaim telah menemukan solusi untuk masalah LP. Bagian ini membahas dasar-dasar yang diperlukan untuk menjawab pertanyaan ini, khususnya mengingat ketidaktepatan numerik dan ketidakunikan solusi.

Toleransi

Pemecah soal LP hampir selalu menggunakan aritmetika floating point, sehingga solusinya bergantung pada ketidaktepatan numerik. Untuk memperhitungkan hal ini, dan untuk meningkatkan performa dengan menghindari upaya pada solusi yang sudah cukup baik, pemecah masalah akan menerima solusi—dan mengklaim telah memecahkan masalah—saat solusi tersebut memenuhi kondisi hingga toleransi tertentu.

Pertimbangkan soal pemrograman linear

$$ \begin{align*} \min\quad & -2x_1 - x_2 \\ \text{s.t.}\quad& x_1 + x_2 \le 1\\ & x_1, x_2 \ge 0 \end{align*} $$

dan masalah ganda yang terkait

$$ \begin{align*} \max\quad& y \\ \text{s.t.}\quad& -2 - y \ge 0\\ &-1 - y \ge 0 \\ &y \le 0 \end{align*} $$

Pasangan soal ini memiliki solusi primal optimal yang unik, yaitu $ x_1 = 1, x_2 = 0 $, dan solusi ganda $ y = -2 $. Solusi mana yang dapat diterima sebagai solusi optimal? Untuk menjawabnya, kami menentukan jumlahnya sebagai berikut:

  • Kesenjangan dualitas adalah selisih antara nilai tujuan utama dan nilai tujuan ganda, dalam hal ini, $ |(-2x_1 - x_2) - y| $.
  • Infeasibilitas primal adalah pelanggaran batasan dasar, dalam hal ini, $ (\max\{ (x_1+x_2) - 1, 0 \}, \max\{-x_1, 0\}, \max\{-x_2, 0\}) $.
  • Infeasiitas ganda adalah pelanggaran batasan ganda, dalam hal ini, $ (\max\{ 2 + y, 0 \}, \max\{ 1 + y, 0 \}, \max\{ y, 0 \}) $.

Pemecah masalah menyatakan solusi sebagai optimal jika kesenjangan dualitas, ketidaksesuaian primal, dan infeasiitas ganda lebih kecil dari toleransi tertentu.1

Secara khusus, penerapan toleransi bervariasi untuk alasan alami dan idiosinkratik di seluruh pemecah dan algoritme. Misalnya, kesenjangan dualitas dalam algoritme simpleks hanya didorong oleh ketidaktepatan numerik, sedangkan infeasiitas primal dan ganda ada bahkan dalam aritmetika yang tepat. Beberapa metode secara langsung menerapkan batasan terikat $ x_1 \ge 0, x_2 \ge 0, $ dan $ y \le 0 $, sedangkan metode yang lain memperlakukan pelanggaran batasan terikat dengan cara yang berbeda dengan pelanggaran batasan linear seperti $x_1 + x_2 \le 1$. Untuk beberapa pemecah masalah, adalah toleransi ganda, jika dipandang memiliki nilai '

Untuk contoh efek toleransi, pertimbangkan toleransi absolut $ \epsilon = \frac{1}{2} $ yang diterapkan pada pasangan primal-dual di atas. Penyelesaian $ x_1 = 1,5, x_2 = 0, y = -3 $ memiliki kesenjangan dualitas nol dan infeasiitas semuanya kurang dari atau sama dengan $ \epsilon $, sehingga pemecah masalah mungkin mendeklarasikan solusi ini "optimal". Namun, nilai objektif (-3) berbeda 1 dari nilai objektif optimal sebenarnya, yaitu -2. Nilai default umum $ \epsilon $ adalah antara $10^{-6}$ dan $10^{-8}$, yang membuat contoh ekstrem seperti ini jarang terjadi, tetapi mustahil.

Jenis solusi

Masalah LP dapat memiliki lebih dari satu solusi optimal, bahkan lebih ketika memperhitungkan toleransi. Kami secara singkat membahas sifat-sifat solusi yang dihasilkan oleh tiga keluarga berbeda dari algoritma LP yang disajikan di atas.

Algoritma {i>simplex<i} selalu menampilkan verteks atau titik sudut dari wilayah yang layak. Solusi ini lebih disukai dalam beberapa situasi karena cenderung lebih jarang.

Metode penghalang dan urutan pertama umumnya tidak mengembalikan verteks. (Teori memberikan karakter tambahan yang berada di luar cakupan panduan ini.)

Karena alasan historis dan karena solusi vertex memiliki properti yang menarik, pemecah masalah sering kali secara default menerapkan prosedur crossover untuk beralih ke vertex optimal dari solusi yang ditemukan oleh algoritme penghalang. Crossover saat ini tidak ditawarkan untuk solusi yang ditemukan oleh metode urutan pertama.

Rekomendasi

Kami membuat rekomendasi berikut untuk penggunaan lanjutan pemecah masalah LP.

Penskalaan data masalah

Pemecah masalah dapat mengalami konvergensi atau kegagalan yang lambat pada model karena masalah numerik. Masalah semacam ini dapat muncul karena berbagai alasan. Di sini kami akan memberikan satu contoh.

Konstanta numerik yang sangat kecil atau besar biasanya muncul dalam model LP. Dengan memperluas contoh di atas, jika \(x_1\) dan \(x_2\) mewakili fraksi pelanggan yang ditetapkan ke "penyedia 1" atau "penyedia 2", dan jika ingin memaksimalkan manfaat dari penayangan pelanggan ini, kita dapat menulis fungsi objektif berikut,

$$ \min -c_1x_1 - c_2x_2 $$

dalam hal ini:

  • $ c_1 $ adalah manfaat dari menetapkan pelanggan ke penyedia 1
  • $ c_2 $ adalah manfaat dari menetapkan pelanggan ke penyedia 2

Duals yang memenuhi batasan berikut akan dianggap layak dengan toleransi absolut $ \epsilon $:

  • $ y \le -c_1 + \epsilon $,
  • $ y \le -c_2 + \epsilon $.

Jika unit manfaat $ c_1 $ dan $ c_2 $ adalah nilai pecahan kecil yang kebetulan berada pada skala yang sama dengan $ \epsilon $, maka kondisi kelayakan ganda menjadi agak lemah, sehingga primal yang sangat kurang optimal dapat dideklarasikan optimal.

Di sisi lain, jika unit manfaat adalah "dolar mikro" (1.000.000 dolar mikro = 1 dolar), nilai absolut yang sangat besar yang dihasilkan meminta presisi yang sangat tinggi dalam solusi, mungkin sangat tinggi mengingat batas bilangan floating point. Pemecah masalah mungkin gagal untuk bertemu jika masalah dirumuskan dengan cara ini. Sebagai bagian dari perumusan masalah yang baik, pemodel tingkat lanjut harus mempertimbangkan apakah data masalah diskalakan dengan cara yang konsisten dengan toleransi pemecahnya.

Selain menghindari kegagalan numerik, toleransi juga dapat disesuaikan untuk performa yang lebih baik. Metode simpleks dan penghalang tidak terlalu sensitif terhadap toleransi, tetapi terkadang mungkin diuntungkan oleh toleransi yang lebih besar jika progres terlihat terhenti di akhir penyelesaian. Di sisi lain, metode urutan pertama biasanya jauh lebih sensitif. Pengguna metode urutan pertama dapat memperoleh manfaat dari solusi yang lebih cepat dengan melonggarkan toleransi, sesuai dengan konteks.

Untuk toleransi Glop, lihat primal_feasibility_tolerance, dual_feasibility_tolerance, dan solution_feasibility_tolerance dalam GlopParameters. Perhatikan bahwa primal_feasibility_tolerance dan dual_feasibility_tolerance digunakan dalam algoritme, sedangkan solution_feasibility_tolerance diperiksa setelah penyelesaian untuk menandai masalah numerik. Untuk PDLP, lihat eps_optimal_absolute dan eps_optimal_relative.

Untuk mengetahui informasi lebih lanjut tentang jenis masalah ini, lihat Pedoman untuk Masalah Numerik Gurobi. Meskipun panduan ini ditulis untuk pengguna Gurobi, banyak prinsip yang berlaku secara umum.

Pilihan pemecah masalah dan algoritma

Kita mulai dengan contoh seberapa besar dampak dari pilihan pemecah masalah dan algoritma, lalu menyajikan panduan untuk memilih pemecah Lp.

Variabilitas dalam praktik

Kami menggambarkan variabilitas dalam performa di seluruh algoritma dan pemecah masalah LP dengan membandingkan waktu penyelesaian pada pilihan instance yang telah digunakan oleh Hans Mittelmann untuk melakukan benchmark pemecah masalah LP. Instance secara eksplisit dipilih untuk menunjukkan performa relatif yang ekstrem dan tidak selalu mewakili perilaku umum.

Metode simplex ganda dan primal Glop dibandingkan dengan metode batasan Gurobi (dengan dan tanpa crossover, yang menemukan solusi vertex) dan PDLP, metode urutan pertama, dalam presisi tinggi dan rendah. Tabel di bawah laporan menyelesaikan waktu dalam detik, dengan batas 20 menit (1.200 detik).

Instance Glop
Primal Simplex		 Glop
Dual Simpleks		 Penghalang Gurobi
dengan Crossover		 Gurobi Barrier
tanpa Crossover		 PDLP
Presisi Tinggi		 PDLP
Presisi Rendah
ex10 >1200 >1200 79.7 63.5 8.2 2.7
nug08-3 >1200 252.8 144,6 3.2 1.1 0,9
savsched1 >1200 >1200 156.0 22,6 46.4 32.4
wide15 >1200 20,8 >1200 >1200 916,4 56.3
energi bangunan 178.4 267.5 12,8 12.3 >1200 157.2
S250R10 12.1 520.6 15.2 16.4 >1200 >1200
Versi Pemecah Soal Alat OR 9.3 Alat OR 9.3 Gurobi 9.0 Gurobi 9.0 Alat OR 9.3 Alat OR 9.3
solver_specific_parameters (default) use_dual_simplex: true Method 2, Threads 1 Method 2, Crossover 0, Threads 1 termination_criteria { eps_optimal_absolute: 1e-8 eps_optimal_relative: 1e-8 } termination_criteria { eps_optimal_absolute: 1e-4 eps_optimal_relative: 1e-4 }

Dari hasil tersebut, kita menyimpulkan hal berikut.

  • Performa relatif algoritma dan pemecah masalah dapat bervariasi berdasarkan urutan besaran pada satu instance.
  • Tidak ada satu algoritma dan pemecah masalah yang secara seragam lebih baik dari yang lain.
  • Crossover (diaktifkan secara default) meningkatkan waktu penyelesaian, terkadang secara substansial.
  • PDLP dapat menyelesaikan presisi rendah 10 kali lebih cepat daripada presisi tinggi.

Panduan singkat untuk memilih pemecah masalah LP

Mengingat tidak ada satu pun algoritme atau pemecah masalah yang terbaik, sebaiknya langkah-langkah berikut ini untuk menemukan solusi yang terbaik bagi kasus penggunaan Anda. Mulailah dengan langkah pertama dan lanjutkan ke langkah berikutnya jika performa tidak cukup.

  1. Coba Glop. Alasan: Glop adalah implementasi internal Google untuk metode simpleks ganda dan primal. Glop adalah open source dan tepercaya untuk beban kerja produksi Google.
    • Jika konfigurasi default (primal simplex) tidak berperforma baik, coba beralih ke simplex ganda menggunakan use_dual_simplex: true.
  2. Jika lisensi tersedia, coba pemecah masalah komersial (CPLEX, Gurobi, atau Xpress). Bereksperimen dengan metode simplex dan penghalang. Alasan: Pemecah masalah ini merupakan standar industri dan sangat dioptimalkan. Juga, metode penghalang melengkapi algoritma {i>simpleks<i} yang ditawarkan oleh Glop.
    • Jika menggunakan batasan, nonaktifkan "crossover" jika Anda tidak memerlukan solusi vertex.
  3. Coba PDLP. Sesuaikan toleransi konvergensi dengan aplikasi Anda. Alasan: PDLP dirancang untuk masalah terbesar, dengan metode simplex dan penghalang mencapai batas memori atau terlalu lambat. PDLP memiliki performa terbaik jika solusi perkiraan tetapi cepat lebih diutamakan daripada solusi yang tepat tetapi lambat.
  4. Jika Anda telah sampai sejauh ini, Anda sekarang adalah pengguna {i>LP<i} tingkat lanjut! Lihat opsi dukungan Alat ATAU untuk mendapatkan bantuan lebih lanjut.

  1. Hal ini sering kali lebih kompleks. Pemecah masalah biasanya memeriksa kondisi ini pada versi masalah yang telah diubah/disederhanakan, yang disebut masalah presolved. Pada beberapa kasus, solusi untuk masalah yang telah diselesaikan mungkin jauh dari solusi untuk masalah input. Situasi ini dapat menyebabkan status yang tidak biasa seperti OptimalInfeas CPLEX atau IMPRECISE Glop.↩