Pemrograman Kendala
- Diperkenalkan oleh
- Rossi, van Beek & Walsh
- Tahun
- 2006
- Jenis
- Declarative combinatorial optimization
- Keluarga
- Mathematical programming
Teks ini adalah terjemahan mesin dan belum ditinjau. Baca versi asli dalam bahasa Inggris
Apa fungsinya?
Pemrograman Kendala (CP) adalah paradigma optimasi deklaratif di mana suatu masalah diformulasikan sebagai himpunan variabel, domain terbatas, dan kendala, dan pemecah secara sistematis mencari penugasan yang memenuhi semua kendala.
Diformalkan secara komprehensif oleh Rossi, van Beek, dan Walsh dalam Handbook of Constraint Programming tahun 2006, CP menyatukan pemangkasan berbasis propagasi dengan pencarian *backtracking* cerdas untuk mengatasi masalah kombinatorial di berbagai domain penjadwalan, perencanaan, dan konfigurasi.
Intuisi di balik metode
Anggap CP sebagai mengisi teka-teki yang rumit: setiap sel adalah variabel dengan sekumpulan nilai yang sah, dan setiap aturan teka-teki adalah kendala. Alih-alih menebak secara membabi buta, CP menggunakan aturan untuk segera menghilangkan nilai yang tidak mungkin dari sel-sel tetangga setiap kali satu sel terisi. Propagasi ini secara dramatis menyusutkan ruang pencarian, sehingga pemecah hanya menjelajahi kombinasi yang masuk akal — melakukan *backtracking* dan merevisi hanya ketika mencapai jalan buntu.
Sejarah
Pemrograman Kendala muncul dari penelitian kecerdasan buatan pada tahun 1970-an dengan karya awal tentang pemenuhan kendala oleh Montanari dan Mackworth. Bidang ini matang sepanjang tahun 1980-an dan 1990-an dengan pengembangan algoritma konsistensi busur, kendala global, dan pemecah praktis seperti CHIP dan ILOG Solver. Bidang ini dikonsolidasikan secara otoritatif oleh Rossi, van Beek, dan Walsh dalam Handbook of Constraint Programming tahun 2006, yang tetap menjadi referensi definitif, mencakup teori, algoritma, dan aplikasi di seluruh optimasi kombinatorial.
Kapan digunakan
Pemrograman Kendala paling cocok untuk masalah kombinatorial dengan kendala yang kompleks dan heterogen — penjadwalan, penyusunan jadwal, konfigurasi, dan perutean — di mana kelayakan sama pentingnya dengan optimalitas. Ini mengasumsikan masalah dapat dimodelkan dengan domain variabel diskrit atau dapat dihitung. CP kurang efektif untuk optimasi kontinu atau program linier skala besar, di mana pemecah Pemrograman Linier atau Pemrograman Campuran Bilangan Bulat (*Mixed-Integer Programming*) biasanya mendominasi. Ketika kendala memiliki struktur yang sangat terstruktur dan propagasi dapat memangkas sebagian besar ruang pencarian, CP mengungguli metaheuristik tujuan umum.
Batasan dan pertimbangan
- Skalabilitas: pencarian eksponensial dalam kasus terburuk membuat CP lambat pada instansi yang sangat besar dengan propagasi yang lemah.
- Membutuhkan pemodelan yang baik: heuristik pengurutan variabel/nilai yang buruk atau hilangnya kendala global menyebabkan pohon pencarian yang sangat besar secara tidak perlu.
- Domain kontinu: CP secara native dirancang untuk domain diskrit; masalah kontinu memerlukan ekstensi khusus atau pendekatan hibrida.
- Keahlian pemecah: penggunaan yang efektif menuntut keakraban dengan teknik pemodelan kendala dan pustaka kendala global spesifik pemecah.
Syarat dari sumber tidak menggantikan tinjauan ilmiah independen atau validasi oleh mesin analisis.
Kelebihan
- Pemodelan deklaratif: aturan dunia nyata yang kompleks diekspresikan langsung sebagai kendala tanpa menentukan prosedur pencarian.
- Pemangkasan yang kuat: propagasi kendala menghilangkan wilayah yang tidak layak sejak dini, sering kali mengurangi pencarian hingga berkali-kali lipat.
- Menangani kendala heterogen: kendala logis, aritmatika, global, dan yang ditentukan pengguna hidup berdampingan secara alami dalam satu model.
- Menjamin kelengkapan: pemecah baik menemukan solusi optimal atau membuktikan ketidaklayakan, tidak seperti metode heuristik.
Penerapan
- Penjadwalan karyawan dan perawat: menugaskan staf ke giliran kerja sambil memenuhi kendala ketersediaan, hukum ketenagakerjaan, dan keterampilan.
- Penyusunan jadwal: menyusun jadwal universitas atau sekolah yang tunduk pada kendala kapasitas ruangan, ketersediaan instruktur, dan kurikulum.
- Konfigurasi: merakit konfigurasi produk (komputer, kendaraan) dari katalog komponen di bawah kendala kompatibilitas dan sumber daya.
- Perutean kendaraan dan logistik: merencanakan rute pengiriman yang tunduk pada jendela waktu, kapasitas kendaraan, dan peraturan pengemudi.
- Lelang kombinatorial dan alokasi sumber daya: menugaskan sumber daya kepada penawar atau tugas di bawah kendala eksklusivitas dan anggaran.
Cara kerjanya
Cara kerjanya
Masalah dikodekan sebagai tripel Masalah Pemenuhan Kendala yang terdiri dari variabel X, domain terbatasnya D, dan himpunan kendala C. Setiap variabel x_i dapat ditugaskan nilai apa pun dari domain D_i-nya. Kendala mendefinisikan kombinasi nilai yang diizinkan di seluruh subset variabel, menerjemahkan aturan dunia nyata — batas kapasitas, relasi prasyarat, konflik sumber daya — ke dalam struktur matematis yang dapat dipertimbangkan oleh pemecah.
Rumus
\text{CSP} = \langle X, D, C \rangle \quad X = \{x_1, x_2, \ldots, x_n\},\; D = \{D_1, D_2, \ldots, D_n\}Sebelum dan selama pencarian, pemecah menerapkan konsistensi busur (*arc consistency*) dan algoritma konsistensi lokal lainnya untuk memangkas nilai domain yang tidak dapat berpartisipasi dalam solusi yang valid. Untuk setiap pasangan variabel yang dibatasi, konsistensi busur menghapus nilai dari domain satu variabel yang tidak memiliki nilai pendukung di domain yang lain. Propagasi ini dipicu berulang kali setelah setiap penugasan, secara drastis mengurangi ruang pencarian efektif.
Rumus
\text{AC}(x_i, x_j): \forall a \in D_i,\; \exists b \in D_j \text{ s.t. } c_{ij}(a, b) \text{ holds}Pemecah memilih variabel yang belum ditugaskan — biasanya menggunakan heuristik seperti nilai tersisa minimum (*minimum remaining values*) atau derajat (*degree*) — dan secara tentatif menugaskannya nilai dari domainnya yang telah dipangkas. Propagasi berjalan lagi; jika kontradiksi terdeteksi (domain kosong), pemecah melakukan *backtrack* ke titik pilihan terakhir dan mencoba nilai alternatif. *Backjumping* dan pencatatan *nogood* dapat lebih mempercepat pemulihan dari kegagalan.
Rumus
x_i \leftarrow a_i \in D_i,\quad \text{propagate},\quad \text{if fail: backtrack and reassign}Ketika semua variabel telah ditugaskan nilai yang konsisten dengan setiap kendala, penugasan lengkap S* merupakan solusi. Untuk masalah optimasi, fungsi tujuan memandu pencarian menuju solusi layak terbaik, dan strategi *branch-and-bound* secara progresif memperketat batas saat solusi yang lebih baik ditemukan, hingga optimum global disertifikasi atau batas waktu tercapai.
Rumus
S^* = \{(x_1, a_1^*), \ldots, (x_n, a_n^*)\} : \forall c \in C,\; c(a_1^*, \ldots, a_n^*) = \text{true}Kesalahan umum
- Melebihi-pembatasan model dengan kendala redundan atau bertentangan menyebabkan pemecah melaporkan ketidaklayakan secara keliru.
- Mengabaikan kendala global (misalnya, *alldifferent*, *cumulative*) melewatkan peluang propagasi yang disediakan oleh algoritma khusus secara gratis.
- Mengabaikan heuristik pencarian dan mengandalkan pengurutan variabel/nilai default dapat membuang waktu eksponensial pada pengurutan patologis.
- Mencampuradukkan pemenuhan kendala dengan optimasi: lupa menambahkan fungsi tujuan dan pengetatan batas hanya menghasilkan solusi layak pertama, bukan yang terbaik.
Pertanyaan yang sering diajukan
Bagaimana Pemrograman Kendala berbeda dari Pemrograman Linier Bilangan Bulat (*Integer Linear Programming*)?
Meskipun keduanya memecahkan masalah kombinatorial, ILP mengharuskan semua kendala dan tujuan bersifat linier, memungkinkan batas relaksasi LP yang efisien. CP tidak memberlakukan persyaratan linearitas seperti itu dan sebaliknya mengandalkan propagasi kendala dan pencarian sistematis. CP menangani kendala logis dan global yang kompleks dengan lebih alami, sedangkan ILP sering kali berskala lebih baik pada masalah dengan struktur linier yang kuat dan jumlah variabel yang besar.
Apa itu kendala global dan mengapa itu penting?
Kendala global adalah kendala tingkat tinggi atas sejumlah variabel arbitrer — misalnya, *alldifferent* (semua variabel mengambil nilai yang berbeda) atau *cumulative* (penggunaan sumber daya kapan saja tidak melebihi kapasitas). Kendala ini penting karena pemecah mengimplementasikan algoritma propagasi khusus yang sangat efisien untuk masing-masing, mencapai pemangkasan yang jauh lebih kuat daripada menguraikan kondisi yang sama menjadi banyak kendala biner, yang akan membiarkan sebagian besar ruang pencarian tidak terjelajahi.
Bisakah Pemrograman Kendala menemukan solusi optimal, atau hanya solusi yang layak?
CP dapat menemukan solusi optimal dengan menggabungkan pencarian kelayakan dengan fungsi tujuan. Pemecah menggunakan *branch-and-bound*: setelah solusi yang layak ditemukan, ia menambahkan kendala yang mengharuskan solusi berikutnya harus lebih baik, berlanjut hingga tidak ada peningkatan yang mungkin. Ini mensertifikasi optimalitas. Jika waktu terbatas, solusi terbaik yang ditemukan sejauh ini dikembalikan sebagai perkiraan.
Metode terkait
Sumber
Rossi, F., van Beek, P., & Walsh, T. (Eds.). (2006). Handbook of Constraint Programming. Elsevier.
ISBN: 978-0-444-52726-4Disalin.