Constraint Programming: Suatu Pendekatan dalam Declarative Programming Dewi Mairiza Fakultas Ilmu Komputer Universitas Indonesia Kampus UI Depok, 16424, Indonesia Phone: +6221 7863419 - Fax: +6221 7863415
[email protected]
Abstrak Pemrograman berbasis constraint (Constraint Programming) adalah suatu pendekatan deklaratif dalam problem solving dengan cara mendeskripsikan permasalahan menjadi himpunan batasan–batasan (constraints). Untuk menyelesaikan kombinatorial atau permasalahan optimisasi (optimization problems) dalam constraint programming, kita cukup memodelkan permasalahan sebagai suatu constraint satisfaction problem, dan selanjutnya solver yang akan mencari solusi atas permasalahan tersebut. Dalam memodelkan permasalahan, kita menggunakan variables, domains, dan constraints yang merepresentasikan himpunan penyelesaian. Constraint programming berkaitan dengan logic programming. Beberapa logic program dapat diterjemahkan ke dalam constraint program, dan sebaliknya. Pendekatan ini banyak digunakan dalam aplikasi komersial seperti Artificial Intelligent, Planning, Scheduling, Bioinformatics, Options Trading, Aerospace, dan sebagainya. Kata kunci: constraint, variable, domain, satisfaction, optimization, declarative.
1. Pengantar Pemrograman berbasis constraint (Constraint Programming atau CP) adalah salah satu topik yang cukup menarik dalam pengembangan bahasa pemrograman khususnya dalam bidang Artificial Intelligent pada sepuluh tahun terakhir. Sebuah constraint pada dasarnya merupakan relasi dari beberapa variable yang memiliki nilai yang dinyatakan dalam suatu domain. Constraint memberikan batasan terhadap nilai yang mungkin untuk suatu variable. Pemrograman deklaratif (Declarative Programming) adalah suatu pendekatan dalam pemrograman computer (computer programming) dengan memberikan dekripsi dari kondisi-kondisi yang ada tanpa mempedulikan interpretasi dari langkah-langkah yang diperlukan untuk mendapatkan penyelesaian. Sehingga perbedaan dari declarative programming adalah pendekatan ini tidak menyediakan instruksi-instruksi yang harus dieksekusi untuk mendapatkan solusi. Declarative programming meliputi pemrograman fungsional (functional programming) dan pemrograman logic (logic programming). Functional programming terkait dengan evaluasi terhadap fungsi matematik dan banyak digunakan dalam parallel computing, sedangkan logic programming berkaitan dengan logika matematik pada pemrograman komputer.
Saat ini, constraint programming banyak diaplikasikan dalam aplikasi optimization problems yang bersifat operasional dan taktis, dimana memerlukan solusi yang realtime namun teknik pemrograman secara matematis belum mencukupi untuk menyelesaikan permasalahannya. Biasanya permasalahan ini meliputi logical constraint yang dapat diselesaikan secara efisien dengan constraint programming. Karena kemampuannya dalam menyelesaikan permasalahan yang cukup sulit untuk diselesaikan (hard-real life problem) inilah, maka pendekatan ini banyak diminati sebagai metode yang digunakan untuk memodelkan kombinatorial dan optimization problems. Selain itu, constraint juga banyak diaplikasikan dalam bidang komersial terutama dalam bidang planning and scheduling, sequencing, dan configuration problems. Dalam aplikasi supply chain management, pendekatan constraint digunakan untuk menyusun jadwal tentang bagaimana sebuah produk harus dibuat pada jumlah mesin yang terbatas sehingga mendapatkan profit maksimal. Dalam options trading, constraint dapat diaplikasikan untuk mendapatkan profit optimal dalam membeli atau menjual options (put options dan call options). Selain itu pendekatan ini juga banyak diaplikasikan dalam planning dan scheduling transportasi, workload, penjadwalan mata pelajaran, dsbnya. Beberapa kelebihan dari constraint programming: outputnya singkat programnya sederhana sehingga dapat dengan mudah diadaptasi bila terjadi perubahan requirements karena programnya dapat dibuat dan dimodifikasi dengan cepat, maka sangat mungkin untuk bereksperimen mendapatkan penyelesaian dengan program terbaik (efisien) dan waktu komputasi tercepat.
2. Constraints Satisfaction Problem Berdasarkan domainnya, constraint programming terbagi atas dua bagian yaitu constraint satisfaction dan constraint solving [1]. Constraint satisfaction terkait dengan permasalahan yang domainnya terbatas (finite domains) dan biasanya disebut sebagai Constraint Satisfaction Problems (CSP) sedangkan constraint solving menggunakan variable yang domainnya tak terbatas (infinite domains) sehingga lebih kompleks dan harus diselesaikan dengan non linear equation, algebra atau metode numerik dan tidak hanya sekedar kombinasi dan searching. CSP berfungsi untuk medapatkan nilai dari variables yang memenuhi semua constraints. Selanjutnya dalam tulisan ini penulis hanya membahas mengenai constraint programming dan constraint satisfaction dalam domain yang terbatas CSP didefinisikan sebagai: • himpunan variables X = {x1, …, xn} • domain yang merupakan himpunan terbatas dari nilai yang mungkin untuk setiap variables (Di) • himpunan constraints yang membatasi nilai yang mungkin untuk setiap variables
Dalam constraint programming terdapat tiga tahapan yang harus selalu ada, yaitu: 1. deklarasi domains dari setiap variables 2. deskripsi dari constraints poblem (problem model) 3. mencari solusi yang tepat dengan menggunakan backtrack search, atau mencari solusi optimal berdasarkan branch-and-bound search. Solusi dalam CSP adalah suatu pemetaan nilai dari domain setiap variables yang memenuhi semua constraints. Terdapat tiga macam solusi yang bisa didapatkan oleh CSP: - hanya satu solusi - semua solusi - sebuah solusi optimal (Constraint Satisfaction Optimization Problem) Solusi dari sebuah CSP diperoleh melalui pencarian (searching) secara sistematik terhadap semua nilai dari variable yang mungkin berdasarkan constraints yang ada. Dalam hal ini metode searching untuk mendapatkan solusi dapat dibagi atas dua kelompok utama, yaitu melalui solusi partial (partial value assignments) dan solusi lengkap (complete value assignments) terhadap semua variables secara stochastic. Dalam constraint programming juga dikenal istilah constraint propagation, yaitu memangkas atau memendekkan pencarian dengan menggunakan constraints yang ada. Setiap constraints memiliki algoritma filtering yang dapat mengurangi jumlah domain dari variables yang ada dalam constraint tersebut, dengan cara membuang nilai yang tidak mungkin menjadi solusi permasalahan. Algoritma ini dipanggil setiap kali sebuah domain dari variable dalam constraint mengalami perubahan dan perubahan ini dipropagasikan terhadap domain dari variables lainnya dan begitu seterusnya. Untuk menutupi kekurangan dari local propagation (incompleteness/lack of shortage), dilakukan pengelompokan beberapa constraints menjadi sebuah special constraint yang disebut sebagai global constraint. Global constraints adalah kumpulan dari beberapa conatraints kecil yang diperlakukan sebagai sebuah unit yang lebih besar (gabungan). Sebagai contoh adalah constraints “all_different, cumulative, cycle, etc”.
3. Constraint Optimization Kadangkala dalam kehidupan nyata kita membutuhkan suatu solusi yang terbaik. Standar dari teknik constraint satisfaction adalah hanya mencari solusi-solusi yang mungkin, tapi ini dapat diperluas untuk mendapatkan solusi yang optimal. Untuk mendapatkan solusi yang optimal digunakan Constraint Satisfaction Optimization Problem (CSOP). Kualitas dari solusi biasanya diukur berdasarkan suatu fungsi yang disebut objective function. CSOP terdiri atas sebuah CSP standar dan sebuah fungsi optimisasi yang memetakan setiap solusi terhadap nilai numeriknya. Sebagian besar aplikasi industri menggunakan konsep CSOP ini.
Algoritma yang paling banyak digunakan untuk mendapatkan solusi yang optimal dalam CSOP adalah Branch and Bound (B&B). Algroritma B&B ini menggunakan heuristic function yang memetakan partial labeling terhadap suatu nilai numerik dengan algoritma depth first search untuk mendapatkan solusi. Dalam proses pencarian, bila nilai domain melewati constraint yang ada, maka subtree yang ada di bawah partial labeling tersebut dipangkas untuk melakukan propagasi. Solusi yang paling optimal berdasarkan constraint dipilih sebagai solusi.
4. Aplikasi Constraint Programming Dalam bagian ini akan dijelaskan beberapa permasalahan dalam constraint dan bagaimana memodelkannya. Assignment Problem Terdapat beberapa pekerjaan yang harus dialokasikan, seperti kapal ke tempat berlabuhnya, pesawat ke hangarnya, kru terhadap penerbangan pesawat, mata pelajaran dalam suatu kelas, pekerjaan dalam sebuah toko, artis/aktor terhadap syuting film, dsbnya. Contoh sederhana berikut ini menjelaskan tentang sebuah pabrik yang memiliki empat pekerja yaitu W1, W2, W3, dan W4, dan empat produk yaitu P1, P2, P3, dan P4. Permasalahannya adalah bagaimana membagi pekerja terhadap produk bila diinginkan setiap pekerja bertanggung jawab terhadap satu produk dan satu produk hanya dikerjakan oleh satu pekerja sehingga total profit perusahaan minimal 19 satuan [2]. Profit yang dihasilkan oleh pekerja Wi terhadap produk Pi diperlihatkan pada Tabel 1. Tabel 1 – Profit yang Dihasilkan Pekerja
W1 W2 W3 W4
P1 7 8 4 3
P2 1 2 3 1
P3 3 5 7 6
P4 4 1 2 3
Kenyataan bahwa setiap pekerja berkerja pada produk yang berbeda dapat digambarkan sebagai suatu himpunan pertidaksamaan binary atau bisa menggunakan global constraint all-different. Untuk menggambarkan profit dari pekerja, kita bisa menggunakan constraint element, kemudian jumlah profit perorangan harus paling rendah 19. Didefinisikan EWi sebagai profit dari pekerja Wi. Model constraint dari permasalahan adalah: EW1+EW2+EW3+EW4 #>= 19 Programnya dengan menggunakan Sicstus Prolog dapat dilihat di Lampiran.
Scheduling dalam Transportasi Scheduling adalah permasalahan dalam menentukan jadwal yang tepat atas suatu pekerjaan terhadap sumber daya yang tersedia sesuai dengan constraint yang harus dipenuhi. Contohnya adalah deadlines problem, resource capacities, precedence constraints pada suatu urutan pekerjaan, dsbnya. Salah satu permasalahan utama di Indonesia adalah transportasi. Tidak hanya permasalahan kemacetan lalu lintas tapi juga kurang berfungsinya sarana angkutan sehingga menyebabkan inefisiensi dan ketidaknyamanan para pemakai jalan. Jakarta sebagai kota tersibuk di Indonesia telah menjalankan proyek busway sebagai sarana transportasi umum yang dijanjikan dapat mengatasi masalah kemacetan dan kenyamanan dalam transportasi. Namun sudah hampir dua tahun proyek ini dijalankan, masalah kemacetan lalu lintas masih saja terjadi. Saat ini, pemerintah berencana untuk mengembangkan monorail sebagai alternatif solusi untuk mengatasi permasalahan kemacetan lalu lintas ini. Walaupun demikian, meskipun sudah banyak sarana transportasi yang cukup nyaman tapi tidak dijalankan dengan baik tentu tidak ada artinya juga. Salah satu cara yang dapat dilakukan untuk memaksimalkan pemanfaatan sarana transportasi umum ini adalah memodelkan pola tingkah laku masyarakat dalam transportasi kemudian merancang dan merencanakan schedule yang optimal dari sarana transportasi di atas, sehingga tidak saling tumpang tindih tapi malah memudahkan dan berguna bagi masyarakat. Constraint programming dapat memodelkan dan menyelesaikan permasalahan pada penjadwalan transportasi untuk mendapatkan solusi terbaik. Solusi terbaik berarti bagaimana mengalokasikan sumber daya yang minimal (busway dan monorail) untuk melayani maksimal jumlah pemakai jasa transportasi umum. Jika sarana transportasi umum mudah untuk didapatkan, memiliki penjadwalan yang optimal, dan nyaman tentu masyarakat akan memilih menggunakan fasilitas ini sebagai trasportasi utama mereka terutama masyarakat yang selama ini memilih menggunakan mobil pribadi yang walaupun kurang efisien tapi lebih nyaman dan mudah didapatkan. Dampak lebih jauh permasalahan kemacetan lalu lintas juga dapat diselesaikan melalu cara ini. Constraint dalam Bioinformatics Dalam bioinformatic, constraint programming digunakan untuk merancang 3D struktur protein pada susunan asam amino (struktur 3D yang menentukan fungsi protein).
Gambar 1 – 3D Protein Structure Selain itu, constraint juga digunakan dalam menganalisa urutan dari DNA, misalnya dalam memperkirakan jarak antara DNA dan membandingkan DNA.
Gambar 2 – Analisa Urutan dari DNA 5. Kesimpulan Dalam tulisan ini, penulis menjelaskan pengantar singkat mengenai pemrograman berbasis constraint (Constraint Programming atau CP) yang merupakan salah satu bentuk dari pendekatan pemrograman declarative (declarative proramming) yang banyak digunakan dalam menyelesaikan hard-real life problems. CP terdiri atas tiga bagian utama yaitu variables, domains, dan constraints yang membatasi nilai dari variables. CP juga dapat digunakan untuk mendapatkan solusi optimal (Constraint Satisfaction Optimization Problem atau CSOP). CP dan CSOP diaplikasikan dalam beberapa bidang planning and scheduling, bioinformatics, options trading, dsbnya yang tentunya juga dapat diaplikasikan dalam berbagai sektor kehidupan di Indonesia.
Daftar Pustaka: [1]
[2]
[3] [4] [5]
[6] [7] [8] [9]
Roman Bartak – Charles University in Prague, NASSLLI2003, Foundations of Constraint Satisfaction, http://kti.mff.cuni.cz/~bartak/, accessed on June 29 2005. Roman Bartak – Charles University in Prague, Practical Constraints: A Tutorial on Modelling with Constraints, CPDC 2003, http://kti.mff.cuni.cz/~bartak/, accessed on June 29 2005. Roman Bartak – Charles University in Prague, Constraint Programming – What is behind? http://kti.mff.cuni.cz/~bartak/, accessed on June 29 2005. Manfred W. Padberg & Minendra P. Rijal, Location, Scheduling, Design, and Integer Programming, Kluwer Academic Publisher, USA, 1996. Roman Bartak – Charles University in Prague, Constraint-Based Scheduling: An Introduction for Newcomers, http://kti.mff.cuni.cz/~bartak/, accessed on June 29 2005. Kim Marriott and Peter J Stuckey, Programming with Constraints, An Introduction, MIT Press, Cambridge Maasachusetts. Edward Tsang, Foundations of Constraint Satisfaction, Academic Press, University of Essex. Francisco Azevedo, Constraint Solving Over Multi-Valued Logics; Application to Digital Circuits, IOS Press, Netherland 2003. Robert Klein, Scheduling of Resource-Constrained Projects, Kluwer Academic Publisher, USA 1999.
Lampiran % Author: Dewi % Date: 7/14/2005 :- use_module(library(clpfd)). /* Goal: to schedule the workers to the products in a company. | ?- assignment(X). */ % The first way = by using Workers as variables and Products as Values assignment(X) :X=[W1, W2, W3, W4], domain([W1, W2, W3, W4], 1, 4), element(W1, [7, 1, 3, 4], EW1), element(W2, [8, 2, 5, 1], EW2), element(W3, [4, 3, 7, 2], EW3), element(W4, [3, 1, 6, 3], EW4), all_different([W1, W2, W3, W4]), EW1+EW2+EW3+EW4 #>= 19, labeling([ff], X).
% If we want to find an optimal solution, we have to append the following algorithm /* EW1+EW2+EW3+EW4=E, maximize(labeling([ff],X), E).
% another way, by using products as variables and workers as values /* assignment(X):*/ /* Y=[P1, P2, P3, P4], domain(Y, 1, 4), all_different(Y), element(P1, [7, 8, 4, 3], EP1), element(P2, [1, 2, 3, 1], EP2), element(P3, [3, 5, 7, 6], EP3), element(P4, [4, 1, 2, 3], EP4), EP1+EP2+EP3+EP4 #>= 19, labeling([ff], Y). */
