Pengantar Praktis Pemrograman Kendala dengan CP-SAT dan Python

Pengantar praktis menggunakan pemrograman kendala: CP-SAT dan Python

Paradigma deklaratif

• Pemrograman kendala (CP) adalah paradigma deklaratif untuk menyelesaikan masalah optimisasi diskret
• Berbeda dengan pemrograman imperatif, kita mendeskripsikan hasil yang diinginkan dan program akan menurunkan hasilnya sendiri
• Sebagai contoh, dijelaskan perbedaan antara pendekatan imperatif dan pendekatan deklaratif saat mengekstrak daftar orang dewasa

Dasar-dasar pemrograman kendala (CP)

• Model: mendeskripsikan hasil yang diinginkan dari suatu masalah
• Variabel: nilai yang ingin dicari, dan setiap variabel memiliki domain (himpunan nilai yang diperbolehkan)
• Kendala: mendeskripsikan hubungan antarvariabel
• Solusi: menetapkan nilai ke variabel sehingga memenuhi kendala

Contoh praktis dengan Python dan CP-SAT

• Masalah: membuat jadwal kerja mingguan karyawan
• Membuat model: menggunakan CP-SAT untuk membuat model kosong
• Data: mendefinisikan daftar karyawan dan peran, hari kerja, serta shift kerja
• Mendefinisikan variabel: membuat variabel boolean yang menunjukkan apakah tiap karyawan bekerja
• Menambahkan kendala: menambahkan kendala pada variabel sesuai deskripsi masalah

Menyelesaikan model

• Penyelesaian: menyelesaikan model dan memperoleh hasil
• Kendala tambahan: menambahkan kendala tambahan seperti mencegah lembur, membatasi jam kerja karyawan tertentu, dan mencegah tumpang tindih jam kerja antar karyawan tertentu

Di tengah jalan: status penyelesaian

• Status penyelesaian: mengembalikan status seperti optimal, layak, tidak layak, atau tidak diketahui
• Contoh: menjelaskan tiap status melalui contoh sederhana

"Maaf, Emma"

• Status tidak layak: tidak mungkin Emma libur 5 hari pada hari kerja
• Usulan alternatif: mengusulkan agar Emma hanya libur 3 hari pada hari kerja

Tujuan: distribusi jam kerja yang merata

• Menambahkan tujuan: menambahkan tujuan untuk mendistribusikan jam kerja secara merata
• Hasil: jam kerja tiap karyawan terdistribusi secara merata

Kesimpulan

• Pengenalan konsep dasar: memperkenalkan konsep dasar pemrograman kendala dan menjelaskannya melalui contoh praktis
• Pratinjau artikel berikutnya: artikel berikutnya akan membahas cara menggunakan pemrograman kendala untuk pemilihan indeks di Postgres

Opini GN⁺

• Kegunaan pemrograman kendala: sangat berguna untuk menyelesaikan masalah optimisasi yang kompleks
• Kekuatan CP-SAT: CP-SAT yang dikembangkan sebagai bagian dari proyek OR-Tools milik Google menawarkan performa yang kuat
• Contoh penerapan nyata: dapat diterapkan pada masalah dunia nyata seperti pembuatan jadwal kerja karyawan
• Hal yang perlu dipertimbangkan saat mengadopsi teknologi: saat mengadopsi teknologi baru, perlu mempertimbangkan kurva belajar dan masalah integrasi dengan sistem yang sudah ada
• Rekomendasi proyek serupa: solver komersial seperti IBM CPLEX dan Gurobi juga menawarkan fungsi serupa

[GN⁺]

Komentar Hacker News

• Pernah menggunakan solver constraint di masa lalu, dan alat-alat ini menunjukkan performa yang sangat mengagumkan

  • Masalahnya adalah hampir tidak ada materi untuk pemula
  • Sebagian besar materi membahas cara menyelesaikan Sudoku atau berupa bahan riset yang sangat teknis
  • Akan bagus jika alat yang bisa menyelesaikan lebih banyak masalah menjadi lebih mudah diakses
  • Mudah diakses tetap berarti programmer masih diperlukan

• Sedang menulis ulang bab singkat tentang penggunaan MiniZinc dan Python dari buku lama saya

  • MiniZinc adalah sistem constraint programming
  • Ada kursus yang bagus di Coursera yang menggunakan MiniZinc

• Banyak program berusaha memiliki satu representasi data tunggal, tetapi dalam kebanyakan kasus itu tidak rasional

  • Diperlukan banyak distorsi agar algoritme bisa berjalan pada representasi baru
  • Saya selalu merasa sayang karena kita tidak lebih sering mengubah representasi
  • Jika representasi diubah, kita bisa mendapatkan representasi yang sangat ringkas, dan itu memungkinkan eksekusi yang lebih cepat

• Saya punya klien yang menjalankan sports camp

  • Anak-anak bisa meminta olahraga yang mereka inginkan dan teman mereka
  • Ini menciptakan masalah penjadwalan yang sulit bagi manusia
  • Saya membangun sistem sederhana menggunakan alat optimisasi berbasis OR-Tools
  • Sekarang penjadwalan selesai hanya dengan beberapa klik

• Pernah banyak menggunakan solver pada awal 2000-an

  • Saat ini saya mengerjakan software (web) yang menggunakan Python
  • Senang melihat pembahasan mendalam tentang topik ini
  • Mengubah constraint menjadi model adalah 90% dari pekerjaan dan merupakan bagian yang paling sulit

• Saya penasaran apakah ada CAD parametrik yang pada dasarnya bekerja dengan solver constraint

  • Di tahap awal, sering terasa merepotkan harus menebak nilai parameter yang sebenarnya belum penting
  • Sebagai gantinya, saya ingin memberi constraint pada parameter yang saya pedulikan dan mengoptimalkan sisanya

• Saya penasaran bagaimana perbandingannya dengan mixed-integer programming