Constraint propagation and variable ordering heuristics for solving Constrained Partial CP-nets

Representing, reasoning and finding Pareto optimal solutions from users' qualitative conditional preferences is one of the interesting research topics in Artificial Intelligence(AI). A conditional Preference Network (CP-net) is one of the extensively used graph models to represent these conditional preferences. Based on user-specific partial order for every value of a set of variables, a CP-net is constructed in ceteris paribus (all else being equal). A Partial CP-net can be used if a user does not specify the order for every variable value. The Search-Partial-CP algorithm can be used for reasoning and producing a set of Pareto optimal solutions from the partial CP-net along with user-defined hard constraints. This thesis contributes towards the improvement of the Search-Partial-CP algorithm along with the addition of functionality to increase usability. We address the challenges we face, in practice, when searching for a solution from a partial CP-net and a set of hard constraints using the Search-Partial-CP algorithm. The first reason for choosing this backtrack search algorithm is due to its ability to work with an acyclic partial CP-net and hard constraints. Secondly, it reduces the run time complexity by removing infeasible or dominated outcomes early from the search space. Finally, this algorithm can be stopped after finding the first feasible solution in cases where finding one optimal solution is enough. However, when we need to find multiple Pareto optimal solutions, a different approach can be integrated to compare those solutions, such as dominance testing or ordering query. A new heuristic for variable ordering is introduced to find the Pareto optimal solutions faster without adding complexity to the existing algorithm. The complexity of finding the first solution in Search-Partial-CP is the same as the underlying constraint satisfaction problem (CSP). Existing variable ordering heuristics orders all the variables of the CSP based on their constraints. The proposed heuristic works simultaneously with the algorithm and orders the subset of the variables that are not dependent on any other variable at that particular time. While producing the Pareto optimal solution set using Search-Partial-CP, dominance testing is performed. A comparative study is provided by running both dominance query and ordering query for the same set of CP-nets and corresponding hard constraints that are randomly generated through the RB model. Unless we apply some assumption, the algorithm for dominance testing is PSPACE-complete. However, it can be reduced to NP or can also be solved in polynomial time.

Name thesis:degree_name

Master of Science (MSc)

Level thesis:degree_level

Master's

Discipline thesis:degree_discipline

Computer Science

Grantor dc:publisher

Faculty of Graduate Studies and Research, University of Regina

Year dc:date.issued

2023

Author dc:creator

• Hossain, Md. Shahadet

Advisor dc:contributor.advisor

• Mouhoub, Malek

Committee member dc:contributor.committeemember

• Fan, Lisa

Language dc:language.iso

en

DOI

https://doi.org/10.82465/3840

OAI identifier oai:identifier

oai:uregina.scholaris.ca:10294/16084