Pengoptimalan batasan, atau pemrograman batasan (CP), adalah nama yang diberikan untuk mengidentifikasi solusi yang layak dari sekumpulan kandidat yang sangat besar, yang mana masalah tersebut dapat dimodelkan dari segi batasan arbitrer. Masalah CP muncul di banyak disiplin ilmu dan teknik. (Kata "pemrograman" adalah istilah yang sedikit keliru, mirip dengan istilah "komputer" yang dulunya berarti "orang yang menghitung". Di sini, "pemrograman" mengacu pada pengaturan rencana, bukan pemrograman dalam bahasa komputer.)
CP didasarkan pada kelayakan (menemukan solusi yang layak), bukan pengoptimalan (menemukan solusi yang optimal) dan berfokus pada batasan dan variabel, bukan fungsi objektif. Bahkan, masalah CP bahkan mungkin tidak memiliki fungsi objektif — tujuannya mungkin untuk mempersempit kumpulan kemungkinan solusi yang sangat besar ke subkumpulan yang lebih mudah dikelola dengan menambahkan batasan pada masalah.
Contoh masalah yang sangat sesuai untuk CP adalah penjadwalan karyawan.
Masalah muncul ketika perusahaan yang beroperasi secara terus-menerus — seperti pabrik — perlu membuat jadwal mingguan untuk karyawannya. Berikut ini
contoh yang sangat sederhana: perusahaan menjalankan tiga shift 8 jam per hari dan menugaskan
tiga dari empat karyawannya untuk shift yang berbeda setiap hari, sekaligus memberikan
hari libur keempat. Bahkan dalam kasus sekecil itu, jumlah kemungkinan jadwal
sangat banyak: setiap hari, ada 4! = 4 * 3 * 2 * 1 = 24 kemungkinan penetapan
karyawan, sehingga jumlah kemungkinan jadwal mingguan adalah 247, atau
lebih dari 4,5 miliar.
Biasanya akan ada batasan lain yang mengurangi jumlah solusi
yang layak — misalnya, setiap karyawan bekerja setidaknya
jumlah hari minimum per minggu. Metode CP melacak solusi mana yang tetap
layak saat Anda menambahkan batasan baru, sehingga menjadikannya alat yang efektif untuk
memecahkan masalah penjadwalan yang besar dan di dunia nyata.
CP memiliki komunitas yang luas dan sangat aktif di seluruh dunia dengan jurnal ilmiah khusus, konferensi, dan berbagai teknik pemecahan masalah. CP telah berhasil diterapkan dalam perencanaan, penjadwalan, dan banyak domain lainnya dengan batasan heterogen.
Alat
Google menyediakan beberapa cara untuk menyelesaikan masalah CP:
- Pemecah CP-SAT: Pemecah pemrograman batasan yang menggunakan metode SAT (kepuasan).
- Pemecah CP asli: Pemecah pemrograman batasan yang digunakan di library perutean.
Jika masalah Anda dapat dimodelkan dengan tujuan linear dan batasan linear, Anda memiliki masalah pemrograman linear dan harus mempertimbangkan MPSolver. (Namun, masalah pemilihan rute biasanya paling tepat diselesaikan dengan library pemilihan rute kendaraan meskipun dapat direpresentasikan dengan model linear.)
Contoh
Bagian berikutnya menjelaskan pemecah CP-SAT, pemecah masalah OR-Tools utama untuk pemrograman batasan. (SAT adalah singkatan dari satisfiability: pemecah masalah menggunakan teknik untuk memecahkan masalah SAT bersama dengan metode CP.)
Berikut adalah beberapa contoh masalah penjadwalan yang sangat cocok untuk pemecah masalah CP-SAT:
Dua masalah CP klasik adalah masalah N-queens dan puzzle kriptoaritmatika.