Pengantar Praktis Pemrograman Kendala dengan CP-SAT dan Python

 (pganalyze.com)
1 poin oleh GN⁺ 2024-07-05 | 1 komentar | Bagikan ke WhatsApp
  • Pemrograman kendala (CP) adalah pendekatan deklaratif untuk memodelkan masalah optimisasi diskret bukan dengan kode prosedural, melainkan dengan variabel, domain, dan kendala, lalu membiarkan solver menemukan solusi yang memenuhi kondisi tersebut
  • Inti model adalah variabel sebagai nilai yang ingin dicari, domain sebagai rentang nilai yang mungkin, dan kendala yang membatasi hubungan antarvariabel; bila perlu, fungsi objektif dapat digunakan untuk memilih solusi yang lebih baik
  • Contoh pembagian biaya permen antara Alice, Bob, dan Carol menunjukkan alur memperbaiki solusi valid menjadi solusi yang lebih merata melalui alldifferent, maximum, dan minimize
  • Contoh praktik menyusun jadwal kerja mingguan untuk 4 karyawan, 7 hari, 3 shift, dan 2 peran menggunakan solver open source CP-SAT dari Google OR-Tools dan Python
  • Pada model yang sama, kondisi seperti batas 40 jam per minggu, jadwal kuliah, kombinasi orang yang tidak boleh bekerja bersama, pembagian kerja akhir pekan yang merata, permintaan cuti, dan minimisasi selisih jumlah shift dapat ditambahkan secara bertahap

Cara berpikir dasar dalam pemrograman kendala

  • Pemrograman kendala (CP) adalah paradigma deklaratif untuk menyelesaikan masalah optimisasi diskret
  • Pemrograman imperatif menuliskan prosedur untuk mencapai hasil secara berurutan, sedangkan pendekatan deklaratif mendeskripsikan kondisi hasil yang diinginkan dan membiarkan sistem eksekusi menemukan hasil tersebut
  • Dalam contoh mencari daftar orang dewasa, kode imperatif menelusuri daftar orang dan memeriksa Age >= 18, sedangkan SQL deklaratif mengekspresikan kondisinya secara langsung seperti SELECT person_name FROM people WHERE age >= 18;
  • CP juga mendeskripsikan hasil yang diinginkan sebagai model, dengan komponen inti berupa variabel, domain, dan kendala
    • Variabel menunjukkan apa yang ingin dicari
    • Domain adalah himpunan nilai yang dapat dimiliki variabel
    • Kendala membatasi hubungan antarvariabel

Variabel, domain, kendala, dan fungsi objektif

  • Solusi adalah penetapan nilai untuk setiap variabel yang berada di dalam domain masing-masing dan memenuhi semua kendala
  • Contoh biaya permen adalah masalah Alice, Bob, dan Carol yang masing-masing memiliki maksimal 20 dolar dan mengumpulkan uang untuk membeli permen seharga 50 dolar
    • Variabel a, b, c adalah jumlah uang yang dibayar masing-masing orang
    • Domain ketiga variabel adalah {0, ..., 20}
    • a + b + c == 50 menyesuaikan totalnya
    • a >= b membuat Alice membayar setidaknya sebanyak Bob
    • c % 5 == 0 membatasi jumlah Carol ke kelipatan 5
    • Agar ketiganya tidak membayar jumlah yang sama, dapat diberi a != b, a != c, b != c
  • Kondisi yang melibatkan banyak variabel dapat diekspresikan sebagai kendala global (global constraints), dan alldifferent(a, b, c) membuat ketiga variabel memiliki nilai yang semuanya berbeda
  • Solver menerima model sebagai input dan mengembalikan solusi yang valid
    • Contoh solusi a = 19, b = 11, c = 20 memenuhi semua kendala
    • Namun karena Carol membayar hampir dua kali lipat Bob, mungkin ada solusi yang lebih merata
  • Fungsi objektif meminimalkan atau memaksimalkan ekspresi tertentu di antara solusi yang memenuhi kendala
    • Tetapkan variabel baru x sebagai kontribusi terbesar dan gunakan maximum(x, [a, b, c])
    • Jika minimize: x diterapkan, hasilnya adalah a = 18, b = 17, c = 15, x = 18
    • Selisih antara kontribusi terbesar dan terkecil berkurang dari 9 dolar menjadi 3 dolar

Membuat model jadwal kerja dengan CP-SAT dan Python

  • Contoh praktik adalah masalah membuat jadwal kerja mingguan untuk toko kecil
    • Toko buka setiap hari dari pukul 08.00 hingga 20.00
    • Satu hari terdiri dari tiga shift: Morning, Afternoon, Evening, dan setiap shift berdurasi 4 jam
    • Ada dua peran: Cashier dan Restocker
    • Karyawannya adalah Phil, Emma, David, dan Rebecca
  • CP-SAT adalah solver CP open source yang termasuk dalam Google OR-Tools
  • Model kosong dibuat dengan cp_model.CpModel() dari ortools.sat.python
  • Peran yang dapat dilakukan tiap karyawan adalah sebagai berikut
    • Phil: Restocker
    • Emma: Cashier, Restocker
    • David: Cashier, Restocker
    • Rebecca: Cashier
  • Jadwal kerja direpresentasikan sebagai variabel boolean yang menggabungkan karyawan, peran, hari, dan shift
    • schedule["Emma"]["Restocker"]["Monday"]["Evening"] bernilai 1 jika Emma bekerja sebagai Restocker pada shift malam hari Senin, dan 0 jika tidak
    • model.new_bool_var() membuat variabel dengan domain {0, 1}

Kendala dasar jadwal kerja

  • Karena diperlukan tepat satu kasir di setiap slot waktu, jumlah peran Cashier untuk setiap hari dan shift harus 1
  • Petugas restock hanya diperlukan satu shift per hari, sehingga jumlah total peran Restocker untuk setiap hari ditetapkan 1
  • Agar shift restock Evening pada hari sebelumnya tidak langsung berlanjut ke shift restock Morning pada hari berikutnya, jumlah kedua penugasan dibatasi tidak melebihi 1
  • Satu karyawan tidak dapat memegang dua peran sekaligus pada shift yang sama, sehingga jumlah peran per karyawan, hari, dan shift harus paling banyak 1
  • Agar peran yang tidak memenuhi kualifikasi tidak ditugaskan, semua variabel peran yang tidak dapat dilakukan karyawan tersebut dikunci ke 0
  • Jam kerja maksimal per hari adalah 8 jam, yaitu 2 shift
    • Jika Morning dan Evening ditugaskan pada hari yang sama, akan muncul waktu menganggur 4 jam selama Afternoon
    • Dengan membatasi jumlah penugasan Morning dan Evening per karyawan dan hari menjadi paling banyak 1, model sekaligus mencegah lebih dari 2 shift per hari dan waktu menganggur di tengah

Menjalankan solver dan hasil awal

  • Untuk menyelesaikan model, buat cp_model.CpSolver() dan panggil solver.solve(model)
  • Setelah mendapatkan solusi, nilai variabel schedule dibaca dengan solver.value(...)
  • Jadwal kerja awal memenuhi semua kendala dasar, tetapi hasilnya Rebecca mendapat 14 shift dalam seminggu
  • Untuk menghindari lembur, tambahkan kendala yang membatasi kerja mingguan tiap karyawan hingga maksimal 40 jam, yaitu 10 shift
  • Phil adalah mahasiswa penuh waktu, jadi ia hanya bekerja tepat 4 shift per minggu dan tidak dapat bekerja pada Morning dan Afternoon di hari kerja karena kuliah
  • Agar Phil dan Emma tidak bekerja pada shift yang sama, jumlah penugasan keduanya dibatasi paling banyak 1 untuk setiap hari dan shift
  • Pekerjaan akhir pekan yang tidak disukai semua orang dibagi ke empat karyawan masing-masing 2 shift dari total 8 shift pada Sabtu dan Minggu

Status solusi: OPTIMAL, INFEASIBLE, FEASIBLE, UNKNOWN

  • Solver menerima model dan mengembalikan status serta solusi
  • OPTIMAL berarti solver telah menemukan solusi yang tidak memiliki solusi lain yang lebih baik
    • Misalnya, saat x + y >= 5 dan x + y diminimalkan, (x, y) = (5, 0) adalah solusi optimal
    • (x, y) = (3, 2) juga memiliki nilai objektif yang sama, sehingga dapat menjadi solusi optimal
  • INFEASIBLE berarti tidak ada cara menetapkan nilai ke variabel yang dapat memenuhi kendala
    • Misalnya, jika x ∈ {0, ..., 10} tetapi diminta x >= 15, itu tidak mungkin
  • Jika solver dihentikan karena batas waktu akibat masalah besar atau fungsi objektif yang kompleks, ada dua status yang mungkin muncul
    • FEASIBLE: solusi yang memenuhi kendala telah ditemukan, tetapi belum diketahui apakah optimal
    • UNKNOWN: solusi belum ditemukan, dan belum diketahui apakah solusi ada atau tidak

Permintaan cuti dan pembagian yang adil

  • Jika ditambahkan kendala bahwa Emma ingin libur dari Senin hingga Jumat, status solver menjadi INFEASIBLE
    • Sebab jadwal tidak dapat diisi tanpa melanggar kendala lain
  • Jika kondisinya diubah sehingga Emma hanya libur dari Senin hingga Rabu, jadwal kerja dapat dibuat
    • Phil bekerja tepat 4 shift sesuai keinginannya
    • Emma mendapat 6 shift, David 10 shift, dan Rebecca 8 shift
  • Untuk membuat jumlah shift antara Emma, David, dan Rebecca lebih merata, tambahkan fungsi objektif
    • Buat variabel integer total_shifts yang menunjukkan total jumlah shift setiap karyawan
    • model.new_int_var(0, 10, ...) membuat variabel integer dengan nilai dari 0 hingga 10
    • Karena Phil paruh waktu, ia dikecualikan, lalu jumlah shift minimum dan maksimum dilacak dengan model.add_min_equality(...) dan model.add_max_equality(...)
    • model.minimize(max_shifts - min_shifts) meminimalkan selisih antara jumlah shift maksimum dan minimum
  • Hasil akhir adalah Phil 4 shift, Emma 6 shift, David 9 shift, dan Rebecca 9 shift
    • Karena Emma libur 3 hari, ia mendapat 6 shift
    • David dan Rebecca dibagi sama rata, masing-masing 9 shift

Kode contoh dan topik berikutnya

  • Model ini membuat jadwal kerja yang sekaligus memenuhi permintaan pemilik toko dan kebutuhan karyawan
  • Dengan terus menambahkan kendala ke model CP yang sama, kita dapat memeriksa apakah permintaan memungkinkan, lalu mencari pembagian yang lebih adil di antara solusi yang memungkinkan menggunakan fungsi objektif
  • Kode contoh tersedia di pganalyze GitHub
  • Topik artikel berikutnya adalah cara menggunakan pemrograman kendala untuk pemilihan indeks di Postgres

Bacaan terkait

1 komentar

 
GN⁺ 2024-07-05
Opini Hacker News

  • Dulu saya pernah mencoba constraint solver, dan hal-hal yang bisa dilakukannya terasa benar-benar seperti sulap. Masalahnya, tidak banyak materi yang cocok untuk pemula
    Kebanyakan hanya tentang memecahkan Sudoku (Hello World di bidang ini), atau literatur riset primer yang sangat teknis dan hanya ditujukan untuk pakar domain
    Sayangnya, kalau alat seperti ini menjadi lebih mudah diakses, rasanya akan ada sangat banyak masalah yang bisa diselesaikan. Yang dimaksud mudah diakses di sini pun tetap berarti masih membutuhkan programmer, dan membentuk sebuah masalah ke dalam DSL constraint bukanlah bidang yang bisa dilakukan dengan baik oleh kebanyakan orang

    • Menurut saya alasan alat seperti ini belum cukup mudah diakses adalah karena sebagian besar solver berbasis mixed-integer programming (MIP), sehingga domain harus ditulis sebagai persamaan matematika. Untuk itu, pengguna harus memahami domain sekaligus matematika agar bisa menulis constraint dengan benar
      Namun MIP bukan satu-satunya jenis solver. Ada juga constraint solver berbasis local search, dan pendekatan ini tidak dibatasi oleh keharusan memodelkan semua constraint sebagai relasi atau persamaan antar variabel integer
      Dalam solver local search, constraint umumnya diperlakukan sebagai black box yang memberi tahu seberapa baik sebuah solusi tertentu. Karena itu, sulit menjamin solusi optimal kecuali mencoba semua kemungkinan solusi, tetapi biasanya bisa menemukan solusi suboptimal dalam waktu yang masuk akal
      Timefold Solver adalah salah satu solver berbasis local search seperti ini. Pengguna memberi anotasi pada domain agar solver dapat mengetahui variabel dan nilai-nilai yang mungkin. Jadi constraint menangani Shift dan Employee, bukan int, dan juga bisa mengakses metodenya
      Pengungkapan: saya bekerja di Timefold Solver
    • Tepat sekali. Sintaks atau API nyata dari constraint solver terlalu sederhana sehingga bisa dipelajari dengan cepat. Bagian yang benar-benar membutuhkan waktu dan keahlian adalah memodelkan masalah dengan cara seperti ini, sementara contoh berskala dan berkompleksitas nyata yang bisa dijadikan rujukan nyaris tidak ada
      Saya punya pengalaman sekitar 5 tahun menyelesaikan masalah penjadwalan dengan MiniZinc, tetapi sayangnya semua kode itu tertutup sehingga tidak akan dirilis sebagai open source
      Saya ingin membuat contoh constraint programming yang lengkap, termasuk containerization, visualisasi, dan modeling, tetapi hambatannya adalah menemukan masalah yang benar-benar layak diselesaikan dan memiliki data open source yang bisa digunakan
    • Saya setuju bahwa reduction jauh lebih sulit daripada teorinya sendiri. "SAT/SMT by Example" dari Dennis Yurichev (https://smt.st/) adalah materi yang bagus untuk topik ini, tetapi cukup mengintimidasi
    • Pernyataan bahwa “sebagian besar materi hanya tentang memecahkan Sudoku atau literatur riset untuk pakar domain” itu tepat. Saya pernah mencoba memakai SAT solver untuk rule engine, tetapi sama sekali tidak punya gambaran bagaimana harus menggunakannya
      Setelah cukup banyak menebak-nebak, saya berhasil membuat proof of concept dasar, tetapi tidak bisa menskalakannya sampai tingkat yang benar-benar dibutuhkan. Kesenjangan antara implementasi mainan dan sesuatu yang lebih substantif sangat besar
    • Saya sudah lama menulis kode, tetapi sekarang agak berkarat. Tahun lalu saya membuat optimizer tim sepak bola dengan OR-Tools dari Google, dengan constraint pilihan seperti ingin satu tim dengan teman, serta kondisi seperti menyeimbangkan kemampuan antar tim
      LLM membantu membawa saya cukup cepat ke arah yang kira-kira benar. Saat ini memang gagal mendapatkan hasil yang benar-benar tepat, tetapi cukup membantu sehingga saya bisa menyelesaikan sisanya sendiri

  • Inti dari semua ini adalah belajar cara memodelkan sesuatu dalam bentuk yang bisa dikirim ke solver. Setelah itu, bagaimana menyajikan solusi yang dihasilkan agar bisa dipahami manusia
    Sayangnya, sebagian besar program mencoba mempertahankan data dalam satu representasi saja, yang berlawanan dengan cara berpikir ini. Dalam kebanyakan kasus, itu tidak masuk akal, dan banyak kerumitan muncul karena harus menyesuaikan algoritme dengan representasi baru
    Tulisan ini juga menyinggung hal tersebut di bagian awal dengan sedikit membahas gaya deklaratif. Saya selalu menyesal kode saya tidak lebih sering melakukan konversi antar representasi. Dengan begitu kita bisa mendapat representasi yang sangat ringkas, dan karena menjadi ringkas, sering kali juga mendapatkan keuntungan ganda berupa performa yang lebih cepat
    Tentu saya sadar bahwa pada akhirnya ini juga menggambarkan banyak data pipeline: struktur yang menghabiskan sebagian besar waktunya untuk mentransformasi data dan mencabangkannya ke berbagai lokasi komputasi

  • Di salah satu buku lama saya yang kini sedang saya tulis ulang, ada bab pendek tentang penggunaan MiniZinc di Python: https://leanpub.com/pythonai/read#constraint-programming-wit...
    MiniZinc adalah sistem constraint programming. Ada juga kursus Coursera yang bagus yang menggunakan MiniZinc

    • Saya penasaran apakah ada tautan ke kursus Coursera itu

  • Setelah belajar ekonometrika, saya banyak memakai solver saat mengambil master riset operasi pada awal 2000-an. Sekarang saya bekerja di perangkat lunak web dengan Python, dan senang melihat tulisan mendalam tentang topik ini
    Saya menyukai topik ini, dan membaca tulisan tersebut membangkitkan banyak kenangan. Saya juga kembali menyadari bahwa memindahkan constraint ke dalam model (variabel, struktur, dan sebagainya) adalah 90% pekerjaan sekaligus bagian tersulit

    • Saat master, saya memakai program bernama GAMS
      Struktur sintaksnya benar-benar berformat bebas
      https://www.gams.com/latest/docs/UG_GAMSPrograms.html#UG_GAM...
    • LLM bisa cukup membantu untuk memindahkan constraint ke dalam model. Saya ingin mencoba adapter yang mengubah keluaran LLM menjadi model constraint
      Kelihatannya seperti buah yang cukup mudah dipetik, tetapi saya penasaran apakah orang lain juga akan mendapat manfaatnya
    • Menurut saya bagian tersulit adalah menjalankannya di lingkungan operasional sambil meminimalkan masalah. Menskalakan dan membuatnya tangguh terhadap perubahan data membutuhkan waktu lama

  • Ada klien yang menjalankan kamp olahraga anak-anak. Anak-anak bisa meminta olahraga yang ingin mereka ikuti dan teman yang ingin mereka satu kelompok dengannya.
    Karena itu muncul masalah penjadwalan yang sulit diselesaikan manusia, dan dulu setiap tahun pekerjaan ini memakan tenaga selama beberapa minggu. Saya membuatkan sistem sederhana yang menghubungkan data klien ke optimizer berbasis OR-Tools, dan sekarang penjadwalan selesai hanya dengan beberapa klik.

    • Benar. Jika data, constraint, dan fungsi utilitas dimasukkan dengan benar ke dalam sistem, kita bisa menemukan banyak solusi yang cukup baik dengan sangat cepat.
      Saya melatih liga basket dan ada 8 periode. Tidak ada pemain yang boleh bermain 2 periode lebih banyak daripada pemain lain. Jumlah lineup yang mungkin per pertandingan tetap astronomis meski harus memenuhi constraint waktu bermain.
      Menemukan kumpulan lineup yang memenuhi constraint sangat mudah, tetapi menemukan kumpulan lineup yang optimal atau mendekati optimal sangat sulit. Akan lebih menarik lagi kalau harus memperhitungkan pemain yang datang terlambat atau absen tanpa kabar.
      *Tidak selalu sepenuhnya memungkinkan
    • Tulisan blog yang menjelaskan secara rinci bagaimana ini dilakukan pasti akan sangat populer.

  • Saya penasaran apakah ada CAD parametrik yang terutama bekerja sebagai constraint solver.
    Terlalu sering saya terganggu karena harus menebak secara kasar nilai parameter yang awalnya tidak saya pedulikan. Akan bagus kalau parameter yang saya minati bisa dijadikan constraint, lalu sisanya dioptimalkan.

  • Saya penasaran bagaimana pendekatan ini dibandingkan dengan mixed-integer programming. Bagaimana kalau untuk masalah fisika?

    • Banyak masalah bisa diformulasikan dengan kedua pendekatan. MILP selalu memiliki fungsi objektif, dan constraint-nya selalu berupa kombinasi linear dari variabel keputusan.
      Karena Gurobi luar biasa cepat, kadang layak memaksakan masalah agar masuk ke bentuk MILP demi mendapatkan solusi.
    • CP-SAT hanya untuk integer, jadi sepertinya kurang cocok untuk fisika. Bilangan real bisa diskalakan, tetapi tidak sebaik menangani floating-point secara langsung.
      Keunggulan CP-SAT adalah menangani variabel dan constraint Boolean serta integer jauh lebih efisien daripada MIP solver, terutama pada constraint tingkat tinggi seperti all_different.
    • Saya menduga secara umum keduanya mirip. https://www.amazon.com/gp/product/1107658799/ adalah buku terakhir yang saya baca tentang topik ini, dan banyak membahas ide yang sama.
      Khususnya bagian dalam tulisan ini yang mencoba meminimalkan suatu nilai menurut saya pada dasarnya menuliskan hal yang sama secara langsung.