Constraint Satisfaction Problems(CSP) have deep roots in many of the well-known real world problems like bin packing, bioinformatics, clustering, combinatorial mathematics, design and configuration, network design, partitioning, timetabling, scheduling, planning, resource allocation.etc. These problems are inherently combinatorial in nature due to the constraints they have to satisfy. Problems like Boolean Satisfiability (SAT), Satisfiability Modulo Theories (SMT) and Answer Set Programming (ASP) can also be modeled as CSP.
A problem modeled as CSP can be effectively solved using CSP solvers which applies techniques like Constraint propagation, Backtracking and local search. However, CSP solvers are not widely used due to inherent difficulty of modeling a problem as CSP. Consequently, an expert has to identify the constraints and their domains to model a problem as CSP.
Loosely put, constraint acquisition is a technique by which a problem can be modeled as CSP. The learner can acheive this either by passive or active constraint acquisition. In passive constraint acquisition the user provides examples (both positive and negative) that helps the learner to learn the target constraint network. Constrastingly, in active constraint acquisition it is the learner who asks queries. The learned constraint network can then be used with different initial domains with CSP solvers. In this seminar, Quick and Mulitple constraint acquisition techniques are reviewed and the challenges, future scope and work is discussed.| Week | Work done during week | Discussion in Meeting | Readings |
|---|---|---|---|
| 17th July --- 23th July | Literature Survey | To read and shortlist papers on Machine Learning in CSP | Readings |
| 24th July --- 30th July | Literature Survey | Read more papers on applying ML/ RL methods in solving CSP | Readings |
| 31st Jul --- 6st Aug | Literature Survey | Focused on survey papers and SAT problems | Readings |
| 7th Aug --- 13th Aug | Literature Survey | More Readings | Readings |
| 14th Aug --- 20st Aug | Finalize on Seminar Topic | Further Reading on the Seminar Topic | Readings |
| 28th Aug --- 18th Sept | Collected Literature on Constriant Acquisition | Zotero report of papers | Readings |
| 3rd Oct --- 9th Oct | Worked out and discussed Non-trivial examples | Start the report writing | Readings |