Salah satu masalah pengoptimalan kombinatorial yang paling terkenal adalah masalah penetapan. Berikut ini contohnya: anggaplah sekelompok pekerja perlu melakukan serangkaian tugas, dan untuk setiap pekerja dan tugas, ada biaya untuk menetapkan pekerja ke tugas tersebut. Masalahnya adalah menetapkan setiap pekerja paling banyak pada satu tugas, tanpa dua pekerja yang melakukan tugas yang sama, sekaligus meminimalkan total biaya.
Anda dapat memvisualisasikan masalah ini melalui grafik di bawah ini, yang berisi empat pekerja dan empat tugas. Bagian tepi mewakili semua cara yang memungkinkan untuk menetapkan pekerja ke tugas. Label di tepian adalah biaya penugasan pekerja.
Penetapan sesuai dengan subset tepi, tempat setiap pekerja memiliki satu tepi yang mengarah ke luar, dan tidak ada dua pekerja yang memiliki tepi yang mengarah ke tugas yang sama. Satu kemungkinan tugas ditampilkan di bawah ini.
Total biaya tugas adalah 70 + 55 + 95 + 45 = 265.
Bagian berikutnya menunjukkan cara menyelesaikan masalah tugas, menggunakan pemecah MIP dan pemecah CP-SAT.
Alat lain untuk menyelesaikan soal tugas
OR-Tools juga menyediakan beberapa alat lain untuk memecahkan masalah tugas, yang dapat lebih cepat daripada pemecah MIP atau CP:
Namun, alat-alat ini hanya dapat memecahkan jenis masalah penugasan yang sederhana. Jadi, untuk pemecah masalah umum yang dapat menangani berbagai masalah (dan cukup cepat untuk sebagian besar aplikasi), kami merekomendasikan pemecah masalah MIP dan CP-SAT.