Saya memiliki satu set agen dan satu set n tugas, dan saya perlu menetapkan masing-masing agen dengan tepat satu tugas sehingga biaya diminimalkan. Beberapa agen tidak kompatibel dengan beberapa tugas.
Saya memiliki implementasi Algoritma Hongaria yang membutuhkan waktu sekitar satu menit untuk menyelesaikan untuk matriks 640 × saya . Untuk tugas terlarang, saya menetapkan biaya ke ∞ . ( Selalu ada solusi yang layak dalam masalah saya).
Saya juga mengaturnya sebagai program biner di CPLEX, yang membutuhkan waktu sekitar 9 detik untuk menyelesaikan masalah yang sama. Model BIP mengecualikan tugas terlarang secara langsung dengan menghilangkan variabel-variabel tersebut.
Saya belum menyelidiki pengaturannya sebagai model jaringan di CPLEX, tetapi itu mungkin akan menjadi langkah saya berikutnya. Namun, ada biaya kinerja dengan berkomunikasi dengan CPLEX, jadi saya yakin algoritma khusus harus mendapatkan kinerja yang lebih baik.
Masalah pencocokan bipartit ini adalah kernel di dalam algoritma pencarian berulang lainnya, sehingga harus berjalan secepat mungkin .
Apakah ada algoritma yang dapat saya terapkan yang akan mengungguli Algoritma Hongaria dalam kasus ini? Atau apakah Anda punya saran lain tentang bagaimana saya dapat meningkatkan kinerja kernel ini?
Jawaban:
Anda dapat mencoba salah satu algoritma berbasis lelang untuk pencocokan bipartit. (Lihat misalnya catatan kuliah yang menjelaskan varian sederhana di sini: https://staff.fnwi.uva.nl/nswalton/Notes/Bertsekas_Auction.pdf tetapi lebih banyak optimisasi dimungkinkan).
Algoritme ini tidak selalu memiliki waktu terbaik untuk menjalankan kasus terburuk, tetapi hanya memerlukan operasi yang sangat sederhana, sehingga seringkali efisien dalam praktiknya, dan dapat menerima paralelisasi. (Dan mereka dapat digunakan sebagai dasar untuk memulihkan waktu berjalan kasus terburuk yang diketahui, lihat: http://agtb.wordpress.com/2009/07/13/auction-algorithm-for-bipartite-matching/
sumber