{"id":{"repo_id":"regina","oai_identifier":"oai:uregina.scholaris.ca:10294/9161"},"canonical_url":"https://search.dev.ndltd.org/etd/regina/oai:uregina.scholaris.ca:10294/9161","repository":{"repo_id":"regina","name":"University of Regina","base_url":"https://uregina.scholaris.ca/server/oai/request"},"display":{"title":"Conditional Preference Networks: Constraints, Genuine Decision, and Aggregation","abstract":"A Conditional Preference Network (CP-net) graphically represents user's conditional ceteris paribus (all else being equal) preference statements, while a Tradeoffs enhanced CP-net (TCP-net) extends the CP-net with conditional relative importance statements. To construct the CP-net, a user specifies a (strict) partial order over the values of each variable, which is usually a total order. In case the order is not a total order, a Partial CP-net is used to capture the preferences. On the other hand, a Lexicographic Preference Tree (LP-tree) represents user's conditional lexicographic preferences. This thesis contributes to the models listed above. First, solving the Constrained CP-net model, a CP-net augmented to a set of hard constraints, requires dominance testing. Dominance testing is generally a PSPACEcomplete problem. This makes the Constrained CP-net very hard to apply in practice. In this regard, we alter the CP-net model by eliciting additional preferences and propose the CPR-net model. We show that constrained optimization with the CPRnet or the LP-tree does not require dominance testing, which allows us to develop efficient solving algorithms. However, both the CPR-net and the LP-tree are less expressive than the CP-net. Hence, we suggest a divide and conquer algorithm to answer dominance queries in the CP-net. In theory, the new algorithm outperforms the existing implementation of dominance testing. Second, we propose an algorithm that we call Search-Partial-CP to solve the Constrained Partial CP-net model. The anytime property of Search-Partial-CP ensures that the user can stop the execution as soon as a desired number of solutions is obtained. Then, we propose a linear time method to answer ordering queries in Partial CP-nets. Interestingly, applying ordering queries instead of dominance testing, in Search-Partial-CP, results in an efficient but incomplete solver. The solver can be applied if time is critical and completeness is not required. Third, to represent user's genuine decision, we introduce the notion of \\comfort". We define new binary relations and their semantics to capture both preferences and comfort. Then, we extend the CP-net to represent both preferences and comfort in a multi-attribute case. Fourth, we propose the Probabilistic TCP-net model that can be used to aggregate multi-users' preferences, or to represent single user's preferences with uncertainty. ii","abstract_html":"A Conditional Preference Network (CP-net) graphically represents user's conditional ceteris paribus (all else being equal) preference statements, while a Tradeoffs enhanced CP-net (TCP-net) extends the CP-net with conditional relative importance statements. To construct the CP-net, a user specifies a (strict) partial order over the values of each variable, which is usually a total order. In case the order is not a total order, a Partial CP-net is used to capture the preferences. On the other hand, a Lexicographic Preference Tree (LP-tree) represents user's conditional lexicographic preferences. This thesis contributes to the models listed above. First, solving the Constrained CP-net model, a CP-net augmented to a set of hard constraints, requires dominance testing. Dominance testing is generally a PSPACEcomplete problem. This makes the Constrained CP-net very hard to apply in practice. In this regard, we alter the CP-net model by eliciting additional preferences and propose the CPR-net model. We show that constrained optimization with the CPRnet or the LP-tree does not require dominance testing, which allows us to develop efficient solving algorithms. However, both the CPR-net and the LP-tree are less expressive than the CP-net. Hence, we suggest a divide and conquer algorithm to answer dominance queries in the CP-net. In theory, the new algorithm outperforms the existing implementation of dominance testing. Second, we propose an algorithm that we call Search-Partial-CP to solve the Constrained Partial CP-net model. The anytime property of Search-Partial-CP ensures that the user can stop the execution as soon as a desired number of solutions is obtained. Then, we propose a linear time method to answer ordering queries in Partial CP-nets. Interestingly, applying ordering queries instead of dominance testing, in Search-Partial-CP, results in an efficient but incomplete solver. The solver can be applied if time is critical and completeness is not required. Third, to represent user's genuine decision, we introduce the notion of \\comfort". We define new binary relations and their semantics to capture both preferences and comfort. Then, we extend the CP-net to represent both preferences and comfort in a multi-attribute case. Fourth, we propose the Probabilistic TCP-net model that can be used to aggregate multi-users' preferences, or to represent single user's preferences with uncertainty. ii","abstract_has_math":false,"creators":["Ahmed, Sultan Uddin"],"institution":"Faculty of Graduate Studies and Research, University of Regina","degree_name":"Doctor of Philosophy (PhD)","degree_level":"Doctoral -- first","degree_discipline":"Computer Science","degree_department":null,"school":null,"contributors":[],"advisors":["Mouhoub, Malek"],"committee_chairs":[],"committee_members":["Yang, Boting","Zilles, Sandra","Volodin, Andrei"],"year":2020,"date_issued":"2020-01","date_published":"2020-01","updated_at":"2026-07-24T04:03:29Z","subjects":[],"languages":["en"],"rights":[],"rights_urls":[],"identifier_entries":[{"key":"dc:identifier.doi","label":"DOI","values":["https://doi.org/10.82465/3948"],"render_values":[{"text":"https://doi.org/10.82465/3948","href":"https://doi.org/10.82465/3948","code":true}]}]},"links":{"outbound_url":"https://hdl.handle.net/10294/9161","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":["Yang, Boting","Zilles, Sandra","Volodin, Andrei"]},{"key":"dc:creator","label":"Author","values":["Ahmed, Sultan Uddin"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date.accessioned","label":"Dc Date Accessioned","values":["2020-08-26T22:09:46Z"]},{"key":"dc:date.available","label":"Dc Date Available","values":["2020-08-26T22:09:46Z"]},{"key":"dc:date.issued","label":"Date","values":["2020-01"]},{"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":["Doctoral -- first"]},{"key":"thesis:degree_name","label":"Degree Name","values":["Doctor of Philosophy (PhD)"]},{"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/3948"]},{"key":"dc:identifier.uri","label":"Identifier URI","values":["https://hdl.handle.net/10294/9161"]}]},{"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 Doctor of Philosophy in Computer Science, University of Regina. xi, 160 p."]},{"key":"dc:description.abstract","label":"Abstract","values":["A Conditional Preference Network (CP-net) graphically represents user's conditional ceteris paribus (all else being equal) preference statements, while a Tradeoffs enhanced CP-net (TCP-net) extends the CP-net with conditional relative importance statements. To construct the CP-net, a user specifies a (strict) partial order over the values of each variable, which is usually a total order. In case the order is not a total order, a Partial CP-net is used to capture the preferences. On the other hand, a Lexicographic Preference Tree (LP-tree) represents user's conditional lexicographic preferences. This thesis contributes to the models listed above. First, solving the Constrained CP-net model, a CP-net augmented to a set of hard constraints, requires dominance testing. Dominance testing is generally a PSPACEcomplete problem. This makes the Constrained CP-net very hard to apply in practice. In this regard, we alter the CP-net model by eliciting additional preferences and propose the CPR-net model. We show that constrained optimization with the CPRnet or the LP-tree does not require dominance testing, which allows us to develop efficient solving algorithms. However, both the CPR-net and the LP-tree are less expressive than the CP-net. Hence, we suggest a divide and conquer algorithm to answer dominance queries in the CP-net. In theory, the new algorithm outperforms the existing implementation of dominance testing. Second, we propose an algorithm that we call Search-Partial-CP to solve the Constrained Partial CP-net model. The anytime property of Search-Partial-CP ensures that the user can stop the execution as soon as a desired number of solutions is obtained. Then, we propose a linear time method to answer ordering queries in Partial CP-nets. Interestingly, applying ordering queries instead of dominance testing, in Search-Partial-CP, results in an efficient but incomplete solver. The solver can be applied if time is critical and completeness is not required. Third, to represent user's genuine decision, we introduce the notion of \\comfort". We define new binary relations and their semantics to capture both preferences and comfort. Then, we extend the CP-net to represent both preferences and comfort in a multi-attribute case. Fourth, we propose the Probabilistic TCP-net model that can be used to aggregate multi-users' preferences, or to represent single user's preferences with uncertainty. ii"]},{"key":"dc:title","label":"Title","values":["Conditional Preference Networks: Constraints, Genuine Decision, and Aggregation"]}]}],"canonical_facts":{"dc:contributor.advisor":["Mouhoub, Malek"],"dc:contributor.committeemember":["Yang, Boting","Zilles, Sandra","Volodin, Andrei"],"dc:creator":["Ahmed, Sultan Uddin"],"dc:date.accessioned":["2020-08-26T22:09:46Z"],"dc:date.available":["2020-08-26T22:09:46Z"],"dc:date.issued":["2020-01"],"dc:description":["A Thesis Submitted to the Faculty of Graduate Studies and Research In Partial Fulfillment of the Requirements for the Degree of Doctor of Philosophy in Computer Science, University of Regina. xi, 160 p."],"dc:description.abstract":["A Conditional Preference Network (CP-net) graphically represents user's conditional ceteris paribus (all else being equal) preference statements, while a Tradeoffs enhanced CP-net (TCP-net) extends the CP-net with conditional relative importance statements. To construct the CP-net, a user specifies a (strict) partial order over the values of each variable, which is usually a total order. In case the order is not a total order, a Partial CP-net is used to capture the preferences. On the other hand, a Lexicographic Preference Tree (LP-tree) represents user's conditional lexicographic preferences. This thesis contributes to the models listed above. First, solving the Constrained CP-net model, a CP-net augmented to a set of hard constraints, requires dominance testing. Dominance testing is generally a PSPACEcomplete problem. This makes the Constrained CP-net very hard to apply in practice. In this regard, we alter the CP-net model by eliciting additional preferences and propose the CPR-net model. We show that constrained optimization with the CPRnet or the LP-tree does not require dominance testing, which allows us to develop efficient solving algorithms. However, both the CPR-net and the LP-tree are less expressive than the CP-net. Hence, we suggest a divide and conquer algorithm to answer dominance queries in the CP-net. In theory, the new algorithm outperforms the existing implementation of dominance testing. Second, we propose an algorithm that we call Search-Partial-CP to solve the Constrained Partial CP-net model. The anytime property of Search-Partial-CP ensures that the user can stop the execution as soon as a desired number of solutions is obtained. Then, we propose a linear time method to answer ordering queries in Partial CP-nets. Interestingly, applying ordering queries instead of dominance testing, in Search-Partial-CP, results in an efficient but incomplete solver. The solver can be applied if time is critical and completeness is not required. Third, to represent user's genuine decision, we introduce the notion of \\comfort". We define new binary relations and their semantics to capture both preferences and comfort. Then, we extend the CP-net to represent both preferences and comfort in a multi-attribute case. Fourth, we propose the Probabilistic TCP-net model that can be used to aggregate multi-users' preferences, or to represent single user's preferences with uncertainty. ii"],"dc:identifier.doi":["https://doi.org/10.82465/3948"],"dc:identifier.uri":["https://hdl.handle.net/10294/9161"],"dc:language.iso":["en"],"dc:publisher":["Faculty of Graduate Studies and Research, University of Regina"],"dc:title":["Conditional Preference Networks: Constraints, Genuine Decision, and Aggregation"],"dc:type":["master thesis"],"thesis:degree_discipline":["Computer Science"],"thesis:degree_level":["Doctoral -- first"],"thesis:degree_name":["Doctor of Philosophy (PhD)"],"thesis:institution_name":["Faculty of Graduate Studies and Research, University of Regina"]},"updated_at":"2026-07-24T04:03:29Z"}