Partial compilation of constraint problems

Simple item page
dc.contributor.advisorO'Sullivan, Barry
dc.contributor.advisorEscamocher, Guillaume
dc.contributor.authorBalogh, Andreaen
dc.contributor.funderScience Foundation Ireland
dc.contributor.funderEuropean Regional Development Fund
dc.date.accessioned2026-01-08T08:53:48Z
dc.date.available2026-01-08T08:53:48Z
dc.date.issued2024en
dc.date.submitted2024en
dc.description.abstractConstraint Programming (CP) is a powerful paradigm for solving combinatorial problems, but due to a large search space, solving can be very time consuming. Diagnosis, planning, product configuration are example use-cases [XBZ+ 21]. These problems are often used in an online setting, where a user expresses queries with additional constraints that are, together with the same problem instance, used many times to answer queries related to model counting, satisfiability, equivalence, etc. Most such queries are NP-hard problems. Knowledge Compilation (KC) methods were developed to deal with the complexity of solving combinatorial problems online by creating a representation offline that is able to answer queries in time that is polynomial in the size of the representation [DM02]. Finding compact representations is often the bottleneck of compilation methods. Due to time or memory limits, compilation may timeout leaving the user without any compiled representation. One approach that is sometimes used is partial compilation whereby a subset of the solutions to the initial constraints are compiled, e.g. those that are considered most important or most likely to be useful. There are many use-cases where some solution loss is acceptable. For example, one might wish to compile a large subset of solutions to an embedded device where space is at a premium [OP06], or in a diagnosis setting, where storing the most likely solutions (diagnoses) might be sufficient. In the CP and SAT (Boolean Satisfiability) communities, various methods have been implemented to reduce search time of solvers. Inspired by this, we investigate whether knowledge compilation benefits from these methods. Namely, we look at the effects of symmetry breaking and backbone relaxation. Symmetry breaking constraints can be added to a combinatorial problem to eliminate symmetries, in the expectation that this will reduce the number of states to be explored, both solutions and non-solutions, thereby speeding-up search. We explore whether breaking symmetries leads to a more compact representation, and if these can be compiled within less time and memory. The utility of symmetry breaking is that symmetric solutions can be reconstructed. We consider four compilers and four highly symmetrical problems to show the effect of symmetry breaking. Another approach we explore is relaxing the definition of backbones, denoted as selective backbone. The selective backbone is a set of assignments that is part of a subset of solutions that optimises a scoring function. Such a scoring function could be maximising the model count of the compilation after assigning the selective backbone, or the ratio between the model count and the compiled representation size. Large selective backbones allow for smaller representations but also eliminate more solutions. We compare different methods of computing the selective backbone that offers the best compromise. We propose four iterative heuristic types and a variety of scoring functions. Some depend on statistical information about variables, some approximate the model count and some calculate the true model count at each iteration. In order to deem our approach successful two criteria must be satisfied: that there is a significant reduction in size and that the important subset of solutions is kept. Since many subsets of solutions exist, representing the most preferred, most likely, most compact, or most important ones for the user is important. For this reason, we look at different ways to define the importance of a variable. In case of unweighted instances, all variables have the same importance, whereas for weighted instances weights represent a preference or probability. This shows that the most important subset is selected, not just the largest one. We conduct experiments on a variety of instances from the domains of circuit design, planning and a generated dataset difficult for model counting. The iterative heuristics we propose to obtain selective backbones are monotonically decreasing the number of solutions represented. Because of this, identifying the number of iterations where the representation is compact enough is important. We propose a method that infers, from a set of small instances, the percentage of variables that need to be assigned for the representation to be compact This is especially important in case the initial problem does not compile, since instead of trying to compile at every iteration we can first assign all proposed variables and then compile.en
dc.description.statusNot peer revieweden
dc.description.versionAccepted Versionen
dc.format.mimetypeapplication/pdfen
dc.identifier.citationBalogh, A. 2024. Partial compilation of constraint problems. PhD Thesis, University College Cork.en
dc.identifier.endpage151en
dc.identifier.urihttps://hdl.handle.net/10468/18385
dc.language.isoenen
dc.publisherUniversity College Corken
dc.relation.projectinfo:eu-repo/grantAgreement/SFI/Research Centres Programme::Phase 2/12/RC/2289_P2/IE/INSIGHT_Phase 2 /en
dc.relation.projectinfo:eu-repo/grantAgreement/SFI/Research Centres Programme/16/RC/3918/IE/Confirm Centre for Smart Manufacturing/en
dc.rights© 2024, Andrea Balogh.en
dc.rights.urihttps://creativecommons.org/licenses/by-nc-nd/4.0/en
dc.subjectKnowledge Compilation (KC)en
dc.subjectConstraint Programming (CP)en
dc.subjectBoolean Satisfiability (SAT)en
dc.titlePartial compilation of constraint problemsen
dc.typeDoctoral thesisen
dc.type.qualificationlevelDoctoralen
dc.type.qualificationnamePhD - Doctor of Philosophyen
Files
Original bundle
Now showing 1 - 2 of 2
Thumbnail Image
Name:
BaloghA_PhD2024.pdf
Size:
3.6 MB
Format:
Adobe Portable Document Format
Description:
Full Text E-thesis
Download
Thumbnail Image
Name:
3. 120227786 - Andrea Balogh - Submission for Examination Form.pdf
Size:
547.25 KB
Format:
Adobe Portable Document Format
License bundle
Now showing 1 - 1 of 1
Thumbnail Image
Name:
license.txt
Size:
5.2 KB
Format:
Item-specific license agreed upon to submission
Description:
Download
Collections
Research Theses
College of Science, Engineering and Food Science - Doctoral Theses
Computer Science - Doctoral Theses
Insight Centre for Data Analytics - Doctoral Theses