Algoritma untuk masalah penugasan umum banyak ke banyak

20

Saya sepertinya tidak dapat menemukan literatur tentang algoritma yang dapat digunakan untuk memecahkan masalah penugasan umum (GAP) banyak-ke-banyak, yaitu model di mana tidak hanya dapat lebih banyak tugas yang ditugaskan ke satu agen, tetapi beberapa agen juga dapat ditugaskan untuk satu tugas (AP satu-ke-satu dan satu-ke-banyak dibahas dalam makalah oleh Pentico). Saya tahu hampir tidak ada masalah penugasan, tetapi saya menemukan masalah seperti ini selama penelitian saya dan ingin tahu lebih banyak tentang bagaimana menyelesaikannya. Mungkinkah GAP banyak-ke-banyak dikenal dengan nama lain, atau adakah alasan berbeda mengapa begitu sedikit literatur tentang itu dapat ditemukan?

Pentico, D. Masalah Penugasan: Survei Ulang Tahun Emas . European Journal Of Operational Research (2007); 176 (2): 774-793.

algorithms data-analysis Gerrit Jan
sumber
1
Hai GerritJan. Selamat datang di Scicomp! :) Apakah Anda terbiasa dengan heuristik lagrangian ini untuk masalah penugasan umum? sciencedirect.com/science/article/pii/S0898122110002609 atau irma-international.org/viewtitle/58969 atau crcnetbase.com/doi/abs/10.1201/9781420010749.ch48 ?
Paul
1
Tampak bagi saya bahwa kasus penugasan porsi tugas ke banyak agen dapat dimodelkan, setidaknya dalam kasus di mana biaya secara linear dibagi, dengan memperlakukan satu tugas seolah-olah itu bukan beberapa subtugas. Tanpa rincian lebih lanjut, sulit untuk mengetahui bagaimana masalah Anda mungkin lebih "umum" daripada masalah penugasan umum. The Artikel Wikipeida memiliki beberapa baik eksposisi dan link ke beberapa referensi pada topik.
hardmath
Terima kasih, @Paul. Saya akan melihat ke kertas, meskipun tampaknya agak rumit bagi mata saya yang tidak terlatih. Kemudian lagi, saya menduga masalahnya rumit, dan saya mungkin harus melakukan penyederhanaan. hardmath, masalah saya pada dasarnya adalah tentang distribusi energi dalam jaringan: supply- dan demandnode perlu dicocokkan menggunakan koneksi (tertimbang) di antara mereka, dengan cara yang paling optimal, dengan penggunaan minimum pasokan untuk memenuhi semua permintaan. Tentu saja, kendala tambahan dapat digunakan, seperti kapasitas maksimal pada koneksi, dll.
Gerrit
1
@GerritJan: Ini masalah np-hard, sehingga akan membutuhkan skema perkiraan. Jika Anda membutuhkan perkiraan yang baik, algoritme Anda mungkin harus sedikit rumit.
Paul
2
@GerritJan: Ini berarti bahwa solusi 'optimal' yang tepat hanya dapat dijamin dengan memeriksa semua kemungkinan konfigurasi. Solusi yang mungkin ini tumbuh (setidaknya) secara eksponensial dari waktu ke waktu, membuat masalah ukuran yang relatif sederhana hampir tidak mungkin untuk diselesaikan dengan tepat dalam jumlah waktu yang wajar.
Paul

Jawaban:

1

Masalah Anda tampaknya bukan, "bahwa jumlah" agen "harus menyediakan persis energi terpisah atau tidak sama sekali untuk setiap permintaan tunggal ...", kan? Atau Anda tidak mengerti saya. Jadi saya akan mencoba menggambarkan masalah saya dengan lebih baik, juga karena saya menemukan solusi.

Dalam masalah saya, saya memiliki satu set agen di mana masing-masing memiliki anggaran sumber daya tertentu, yang dapat berbagi biaya tugas, yang harus "dieksekusi" 1 kali atau tidak (banyak-ke-banyak-penugasan tanpa perlu "jalankan" setiap tugas). Ini berarti: jumlah solusi parsial agen untuk tugas x harus kurang atau sama dengan biaya tugas x. Tujuannya adalah untuk menemukan serangkaian tugas dengan nilai paling tinggi yang dapat dibayar agen.

Saya bekerja dengan perangkat lunak gams jadi saya jelaskan dengan gaya gams: atur agen, t tugas parameter biaya (t), nilai (t) sumber daya parameter (a)

variabel positif y (a, t) (non-int), bagian dari agen a untuk biaya tugas t tujuan: 

maxvalue =e= sum((a,t), value(t) * y(a,t) / cost(t) );
agentresource_max_constraint(a).. sum(t, y(a,t)) =l= resources(a);
taskcost_max_constraint.. sum(a, y(a,t)) =l= cost(t);

Ketika saya menulis, saya punya solusi tetapi tidak tahu bagaimana memisahkan solusi tugas parsial. Tetapi sekarang saya mengetahui bahwa saya dapat membangun batasan dengan a

variabel biner z(t)

taskcost_bin_constraint z(t) =e= sum(a, y(a,t)) / cost(t);

sum(a, y(a,t)) / cost(t)dalam rumusan persamaan adalah sesuatu antara 0 dan 1 dan dengan batasan ini, zadalah 0 untuk semua kurang dari 1 dan 1 untuk 1. dengan taskcost_bin_constrainttujuan ini adalah:

maxvalue =e= sum(t, value(t) * z(t));

Saya bertanya-tanya tetapi ini berhasil dan memberi saya solusi yang lebih baik di bawah kendala, untuk membangun tugas penuh atau tidak.

Mungkin Anda juga bisa menambahkan batasan seperti itu? Kendala untuk memenuhi permintaan dengan tepat, dinyatakan dalam ekspresi dengan nilai antara 0 dan 1.

Maik
sumber
1

Ada algoritma annealing deterministik yang memecahkan masalah penugasan satu-ke-satu atau setara dengan masalah partisi matriks diad.

Namun alih-alih menggunakan nilai integer [0, 1] seseorang dapat menggunakan nilai fraksional (sehingga algoritme tetap sama) atau bahkan memperluasnya untuk menangani lebih dari satu penugasan (dengan menambahkan loop dalam dan pada dasarnya matriks menjadi array hiper-dimensional. atau tensor)

Makalahnya ada di sini: http://www.researchgate.net/publication/2382666_Pairwise_Data_Clustering_by_Deterministic_Annealing/file/d912f50c75945d835b.pdf

Nikos M.
sumber