{"id":{"repo_id":"regina","oai_identifier":"oai:uregina.scholaris.ca:10294/7673"},"canonical_url":"https://search.dev.ndltd.org/etd/regina/oai:uregina.scholaris.ca:10294/7673","repository":{"repo_id":"regina","name":"University of Regina","base_url":"https://uregina.scholaris.ca/server/oai/request"},"display":{"title":"Using Conflict and Support Counts for Variable and Value Ordering in CSPs","abstract":"A Constraint Satisfaction Problem (CSP) is a very powerful framework for representing and solving constraint problems. Many real world computational problems in Artificial Intelligence and other areas of computer science can be formulated as CSPs. Problems such as scheduling and timetabling in operations research, map-coloring problem and Boolean satisfiability are some of the examples that can be represented and solved with a CSP framework. Solving a CSP is about searching for a solution in a huge search space. Very often, much search efforts are wasted on the part of the search space that does not lead to a solution. Therefore many search algorithms and heuristic techniques have been proposed to solve CSPs efficiently by reducing the search space. Variable and Value Ordering is one of them. Many experiments and analyses have been conducted to show that good ordering of variables and values can significantly reduce the size of the search space and thus make the search more efficient. Many heuristics have been proposed for ordering variables or values. One such heuristics works by gathering information during search to guide subsequent decision in selecting variables. The heuristic gathers and records information about failures in the form of constraint weight during constraint propagation. Constraints will be assigned weights based on the information gathered. Each variable in the constraint graph will have a weighted degree which is the sum of the weights of the constraints the variable is involved in. In this thesis I will propose a variant of this heuristic where the weight of a constraint is also based on the conflict and support counts of each variable attached to this constraint. The conflict and support counts information is gathered during constraint propagation. The weight of the constraint is the ratio of conflict to support counts. I will also propose a dynamic value ordering heuristic based on the support and conflict count information. Experiments have been conducted on the proposed heuristics using the renowned benchmarks which include random, quasi-random, pattern and real world instances. The test results show that the proposed variable ordering heuristic perform well in the cases of hard random and quasi-random instances. The test results also show that combining the proposed variable and value ordering heuristics can improve the performance significantly in some difficult problems.","abstract_html":"A Constraint Satisfaction Problem (CSP) is a very powerful framework for representing and solving constraint problems. Many real world computational problems in Artificial Intelligence and other areas of computer science can be formulated as CSPs. Problems such as scheduling and timetabling in operations research, map-coloring problem and Boolean satisfiability are some of the examples that can be represented and solved with a CSP framework. Solving a CSP is about searching for a solution in a huge search space. Very often, much search efforts are wasted on the part of the search space that does not lead to a solution. Therefore many search algorithms and heuristic techniques have been proposed to solve CSPs efficiently by reducing the search space. Variable and Value Ordering is one of them. Many experiments and analyses have been conducted to show that good ordering of variables and values can significantly reduce the size of the search space and thus make the search more efficient. Many heuristics have been proposed for ordering variables or values. One such heuristics works by gathering information during search to guide subsequent decision in selecting variables. The heuristic gathers and records information about failures in the form of constraint weight during constraint propagation. Constraints will be assigned weights based on the information gathered. Each variable in the constraint graph will have a weighted degree which is the sum of the weights of the constraints the variable is involved in. In this thesis I will propose a variant of this heuristic where the weight of a constraint is also based on the conflict and support counts of each variable attached to this constraint. The conflict and support counts information is gathered during constraint propagation. The weight of the constraint is the ratio of conflict to support counts. I will also propose a dynamic value ordering heuristic based on the support and conflict count information. Experiments have been conducted on the proposed heuristics using the renowned benchmarks which include random, quasi-random, pattern and real world instances. The test results show that the proposed variable ordering heuristic perform well in the cases of hard random and quasi-random instances. The test results also show that combining the proposed variable and value ordering heuristics can improve the performance significantly in some difficult problems.","abstract_has_math":false,"creators":["Yong, Ket Wei"],"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":["Yang, Boting","Sadaoui, Samira"],"year":2016,"date_issued":"2016-02","date_published":"2016-02","updated_at":"2026-07-24T04:03:38Z","subjects":[],"languages":["en"],"rights":[],"rights_urls":[],"identifier_entries":[{"key":"dc:identifier.doi","label":"DOI","values":["https://doi.org/10.82465/4441"],"render_values":[{"text":"https://doi.org/10.82465/4441","href":"https://doi.org/10.82465/4441","code":true}]}]},"links":{"outbound_url":"https://hdl.handle.net/10294/7673","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","Sadaoui, Samira"]},{"key":"dc:creator","label":"Author","values":["Yong, Ket Wei"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date.accessioned","label":"Dc Date Accessioned","values":["2017-06-19T22:10:20Z"]},{"key":"dc:date.available","label":"Dc Date Available","values":["2017-06-19T22:10:20Z"]},{"key":"dc:date.issued","label":"Date","values":["2016-02"]},{"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/4441"]},{"key":"dc:identifier.uri","label":"Identifier URI","values":["https://hdl.handle.net/10294/7673"]}]},{"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.viii, 85 p."]},{"key":"dc:description.abstract","label":"Abstract","values":["A Constraint Satisfaction Problem (CSP) is a very powerful framework for representing and solving constraint problems. Many real world computational problems in Artificial Intelligence and other areas of computer science can be formulated as CSPs. Problems such as scheduling and timetabling in operations research, map-coloring problem and Boolean satisfiability are some of the examples that can be represented and solved with a CSP framework. Solving a CSP is about searching for a solution in a huge search space. Very often, much search efforts are wasted on the part of the search space that does not lead to a solution. Therefore many search algorithms and heuristic techniques have been proposed to solve CSPs efficiently by reducing the search space. Variable and Value Ordering is one of them. Many experiments and analyses have been conducted to show that good ordering of variables and values can significantly reduce the size of the search space and thus make the search more efficient. Many heuristics have been proposed for ordering variables or values. One such heuristics works by gathering information during search to guide subsequent decision in selecting variables. The heuristic gathers and records information about failures in the form of constraint weight during constraint propagation. Constraints will be assigned weights based on the information gathered. Each variable in the constraint graph will have a weighted degree which is the sum of the weights of the constraints the variable is involved in. In this thesis I will propose a variant of this heuristic where the weight of a constraint is also based on the conflict and support counts of each variable attached to this constraint. The conflict and support counts information is gathered during constraint propagation. The weight of the constraint is the ratio of conflict to support counts. I will also propose a dynamic value ordering heuristic based on the support and conflict count information. Experiments have been conducted on the proposed heuristics using the renowned benchmarks which include random, quasi-random, pattern and real world instances. The test results show that the proposed variable ordering heuristic perform well in the cases of hard random and quasi-random instances. The test results also show that combining the proposed variable and value ordering heuristics can improve the performance significantly in some difficult problems."]},{"key":"dc:title","label":"Title","values":["Using Conflict and Support Counts for Variable and Value Ordering in CSPs"]}]}],"canonical_facts":{"dc:contributor.advisor":["Mouhoub, Malek"],"dc:contributor.committeemember":["Yang, Boting","Sadaoui, Samira"],"dc:creator":["Yong, Ket Wei"],"dc:date.accessioned":["2017-06-19T22:10:20Z"],"dc:date.available":["2017-06-19T22:10:20Z"],"dc:date.issued":["2016-02"],"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.viii, 85 p."],"dc:description.abstract":["A Constraint Satisfaction Problem (CSP) is a very powerful framework for representing and solving constraint problems. Many real world computational problems in Artificial Intelligence and other areas of computer science can be formulated as CSPs. Problems such as scheduling and timetabling in operations research, map-coloring problem and Boolean satisfiability are some of the examples that can be represented and solved with a CSP framework. Solving a CSP is about searching for a solution in a huge search space. Very often, much search efforts are wasted on the part of the search space that does not lead to a solution. Therefore many search algorithms and heuristic techniques have been proposed to solve CSPs efficiently by reducing the search space. Variable and Value Ordering is one of them. Many experiments and analyses have been conducted to show that good ordering of variables and values can significantly reduce the size of the search space and thus make the search more efficient. Many heuristics have been proposed for ordering variables or values. One such heuristics works by gathering information during search to guide subsequent decision in selecting variables. The heuristic gathers and records information about failures in the form of constraint weight during constraint propagation. Constraints will be assigned weights based on the information gathered. Each variable in the constraint graph will have a weighted degree which is the sum of the weights of the constraints the variable is involved in. In this thesis I will propose a variant of this heuristic where the weight of a constraint is also based on the conflict and support counts of each variable attached to this constraint. The conflict and support counts information is gathered during constraint propagation. The weight of the constraint is the ratio of conflict to support counts. I will also propose a dynamic value ordering heuristic based on the support and conflict count information. Experiments have been conducted on the proposed heuristics using the renowned benchmarks which include random, quasi-random, pattern and real world instances. The test results show that the proposed variable ordering heuristic perform well in the cases of hard random and quasi-random instances. The test results also show that combining the proposed variable and value ordering heuristics can improve the performance significantly in some difficult problems."],"dc:identifier.doi":["https://doi.org/10.82465/4441"],"dc:identifier.uri":["https://hdl.handle.net/10294/7673"],"dc:language.iso":["en"],"dc:publisher":["Faculty of Graduate Studies and Research, University of Regina"],"dc:title":["Using Conflict and Support Counts for Variable and Value Ordering in CSPs"],"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:38Z"}