{"id":{"repo_id":"regina","oai_identifier":"oai:uregina.scholaris.ca:10294/16084"},"canonical_url":"https://search.dev.ndltd.org/etd/regina/oai:uregina.scholaris.ca:10294/16084","repository":{"repo_id":"regina","name":"University of Regina","base_url":"https://uregina.scholaris.ca/server/oai/request"},"display":{"title":"Constraint propagation and variable ordering heuristics for solving Constrained Partial CP-nets","abstract":"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.","abstract_html":"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.","abstract_has_math":false,"creators":["Hossain, Md. Shahadet"],"institution":"Faculty of Graduate Studies and Research, University of Regina","degree_name":"Master of Science (MSc)","degree_level":"Master's","degree_discipline":"Computer Science","degree_department":null,"school":null,"contributors":[],"advisors":["Mouhoub, Malek"],"committee_chairs":[],"committee_members":["Fan, Lisa"],"year":2023,"date_issued":"2023-03","date_published":"2023-03","updated_at":"2026-07-24T04:03:27Z","subjects":[],"languages":["en"],"rights":[],"rights_urls":[],"identifier_entries":[{"key":"dc:identifier.doi","label":"DOI","values":["https://doi.org/10.82465/3840"],"render_values":[{"text":"https://doi.org/10.82465/3840","href":"https://doi.org/10.82465/3840","code":true}]}]},"links":{"outbound_url":"https://hdl.handle.net/10294/16084","outbound_label":"Handle","outbound_source":"dc:identifier.uri"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor.advisor","label":"Advisor","values":["Mouhoub, Malek"]},{"key":"dc:contributor.committeemember","label":"Committee Member","values":["Fan, Lisa"]},{"key":"dc:creator","label":"Author","values":["Hossain, Md. Shahadet"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date.accessioned","label":"Dc Date Accessioned","values":["2023-07-18T17:59:23Z"]},{"key":"dc:date.available","label":"Dc Date Available","values":["2023-07-18T17:59:23Z"]},{"key":"dc:date.issued","label":"Date","values":["2023-03"]},{"key":"dc:publisher","label":"Institution","values":["Faculty of Graduate Studies and Research, University of Regina"]},{"key":"dc:type","label":"Dc Type","values":["master thesis"]},{"key":"thesis:degree_discipline","label":"Discipline","values":["Computer Science"]},{"key":"thesis:degree_level","label":"Degree Level","values":["Master's"]},{"key":"thesis:degree_name","label":"Degree Name","values":["Master of Science (MSc)"]},{"key":"thesis:institution_name","label":"Thesis Institution Name","values":["Faculty of Graduate Studies and Research, University of Regina"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language.iso","label":"Language (ISO)","values":["en"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier.doi","label":"DOI","values":["https://doi.org/10.82465/3840"]},{"key":"dc:identifier.uri","label":"Identifier URI","values":["https://hdl.handle.net/10294/16084"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description","label":"Description","values":["A Thesis Submitted to the Faculty of Graduate Studies and Research In Partial Fulfillment of the Requirements for the Degree of Master of Science in Computer Science, University of Regina. x, 58 p."]},{"key":"dc:description.abstract","label":"Abstract","values":["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."]},{"key":"dc:title","label":"Title","values":["Constraint propagation and variable ordering heuristics for solving Constrained Partial CP-nets"]}]}],"canonical_facts":{"dc:contributor.advisor":["Mouhoub, Malek"],"dc:contributor.committeemember":["Fan, Lisa"],"dc:creator":["Hossain, Md. Shahadet"],"dc:date.accessioned":["2023-07-18T17:59:23Z"],"dc:date.available":["2023-07-18T17:59:23Z"],"dc:date.issued":["2023-03"],"dc:description":["A Thesis Submitted to the Faculty of Graduate Studies and Research In Partial Fulfillment of the Requirements for the Degree of Master of Science in Computer Science, University of Regina. x, 58 p."],"dc:description.abstract":["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."],"dc:identifier.doi":["https://doi.org/10.82465/3840"],"dc:identifier.uri":["https://hdl.handle.net/10294/16084"],"dc:language.iso":["en"],"dc:publisher":["Faculty of Graduate Studies and Research, University of Regina"],"dc:title":["Constraint propagation and variable ordering heuristics for solving Constrained Partial CP-nets"],"dc:type":["master thesis"],"thesis:degree_discipline":["Computer Science"],"thesis:degree_level":["Master's"],"thesis:degree_name":["Master of Science (MSc)"],"thesis:institution_name":["Faculty of Graduate Studies and Research, University of Regina"]},"updated_at":"2026-07-24T04:03:27Z"}