<?xml version="1.0" encoding="UTF-8"?><?xml-stylesheet type="text/xsl" href="static/style.xsl"?><OAI-PMH xmlns="http://www.openarchives.org/OAI/2.0/" xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance" xsi:schemaLocation="http://www.openarchives.org/OAI/2.0/ http://www.openarchives.org/OAI/2.0/OAI-PMH.xsd"><responseDate>2026-11-22T15:19:02Z</responseDate><request verb="GetRecord" identifier="oai:uwspace.uwaterloo.ca:10012/1193" metadataPrefix="dim">https://dspacemainprd01.lib.uwaterloo.ca/server/oai/request</request><GetRecord><record><header><identifier>oai:uwspace.uwaterloo.ca:10012/1193</identifier><datestamp>2017-03-21T19:17:18Z</datestamp><setSpec>com_10012_9924</setSpec><setSpec>com_10012_1</setSpec><setSpec>col_10012_9930</setSpec><setSpec>col_10012_6</setSpec></header><metadata><dim:dim xmlns:dim="http://www.dspace.org/xmlns/dspace/dim" xmlns:doc="http://www.lyncode.com/xoai" xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance" xsi:schemaLocation="http://www.dspace.org/xmlns/dspace/dim http://www.dspace.org/schema/dim.xsd">
   <dim:field mdschema="dc" element="contributor" qualifier="author" lang="en" authority="ceacb65d-4a33-4130-971e-f8fec0da0e5a" confidence="600">Park, Vincent Se-jin</dim:field>
   <dim:field mdschema="dc" element="date" qualifier="accessioned">2006-08-22T14:26:36Z</dim:field>
   <dim:field mdschema="dc" element="date" qualifier="available">2006-08-22T14:26:36Z</dim:field>
   <dim:field mdschema="dc" element="date" qualifier="issued" lang="en">2004</dim:field>
   <dim:field mdschema="dc" element="date" qualifier="submitted" lang="en">2004</dim:field>
   <dim:field mdschema="dc" element="identifier" qualifier="uri">http://hdl.handle.net/10012/1193</dim:field>
   <dim:field mdschema="dc" element="description" qualifier="abstract" lang="en">Many real life problems can be formulated as constraint satisfaction problems &amp;lt;i&amp;gt;(CSPs)&amp;lt;/i&amp;gt;.    Backtracking search algorithms are usually employed to solve &amp;lt;i&amp;gt;CSPs&amp;lt;/i&amp;gt; and in backtracking search the choice of branching strategies can be critical since they specify how a search algorithm can instantiate a variable and how a problem can be reduced into subproblems; that is, they define a search tree.   In spite of the apparent importance of the branching strategy, there have been only a few empirical studies about different branching strategies and they all have been tested exclusively for numerical constraints.   In this thesis, we employ the three most commonly used branching strategies in solving finite domain &amp;lt;i&amp;gt;CSPs&amp;lt;/i&amp;gt;.   These branching strategies are described as follows: first, a branching strategy with strong commitment assigns its variables in the early stage of the search as in k-Way branching; second, 2-Way branching guides a search by branching one side with assigning a variable and the other with eliminating the assigned value; third, the domain splitting strategy, based on the least commitment principle, branches by dividing a variable&amp;apos;s domain rather than by assigning a single value to a variable.   In our experiments, we compared the efficiency of different branching strategies in terms of their execution times  and the number of choice points in solving finite domain &amp;lt;i&amp;gt;CSPs&amp;lt;/i&amp;gt;.    Interestingly, our experiments provide evidence that the choice of branching strategy for finite domain problems does not matter much in most cases--provided we are using an effective variable ordering heuristic--as domain splitting and 2-Way branching end up simulating k-Way branching.    However, for an optimization problem with large domain size, the branching strategy with the least commitment principle can be more efficient than the other strategies.   This empirical study will hopefully interest other practitioners to take different branching schemes into consideration in designing heuristics.</dim:field>
   <dim:field mdschema="dc" element="format" lang="en">application/pdf</dim:field>
   <dim:field mdschema="dc" element="format" qualifier="extent">483787 bytes</dim:field>
   <dim:field mdschema="dc" element="format" qualifier="mimetype">application/pdf</dim:field>
   <dim:field mdschema="dc" element="language" qualifier="iso" lang="en">en</dim:field>
   <dim:field mdschema="dc" element="publisher" lang="en">University of Waterloo</dim:field>
   <dim:field mdschema="dc" element="rights" lang="en">Copyright: 2004, 
  Park, Vincent Se-jin. All rights reserved.</dim:field>
   <dim:field mdschema="dc" element="subject" lang="en">Computer Science</dim:field>
   <dim:field mdschema="dc" element="subject" lang="en">BRANCHING</dim:field>
   <dim:field mdschema="dc" element="subject" lang="en">BRANCHING STRATEGY</dim:field>
   <dim:field mdschema="dc" element="subject" lang="en">CONSTRAINT</dim:field>
   <dim:field mdschema="dc" element="subject" lang="en">CONSTRAINT SATISFACTION PROBLEM</dim:field>
   <dim:field mdschema="dc" element="subject" lang="en">CONSTRAINT PROGRAMMING</dim:field>
   <dim:field mdschema="dc" element="subject" lang="en">DOMAIN SPLITTING</dim:field>
   <dim:field mdschema="dc" element="subject" lang="en">K-WAY BRANCHING</dim:field>
   <dim:field mdschema="dc" element="subject" lang="en">2-WAY BRANCHING</dim:field>
   <dim:field mdschema="dc" element="subject" lang="en">BACKTRACKING SEARCH</dim:field>
   <dim:field mdschema="dc" element="subject" lang="en">VARIABLE ORDERING</dim:field>
   <dim:field mdschema="dc" element="subject" lang="en">HEURISTIC</dim:field>
   <dim:field mdschema="dc" element="subject" lang="en">OPTIMIZATION</dim:field>
   <dim:field mdschema="dc" element="subject" lang="en">DOMAIN SIZE</dim:field>
   <dim:field mdschema="dc" element="subject" lang="en">LEAST COMMITMENT</dim:field>
   <dim:field mdschema="dc" element="title" lang="en">AN EMPIRICAL STUDY OF DIFFERENT BRANCHING STRATEGIES FOR CONSTRAINT SATISFACTION PROBLEMS</dim:field>
   <dim:field mdschema="dc" element="type" lang="en">Master Thesis</dim:field>
   <dim:field mdschema="dc" element="pending" lang="en">false</dim:field>
   <dim:field mdschema="uws-etd" element="degree" qualifier="department" lang="en">School of Computer Science</dim:field>
   <dim:field mdschema="uws-etd" element="degree" lang="en">Master of Mathematics</dim:field>
   <dim:field mdschema="uws" element="typeOfResource" lang="en">Text</dim:field>
   <dim:field mdschema="uws" element="peerReviewStatus" lang="en">Unreviewed</dim:field>
   <dim:field mdschema="uws" element="scholarLevel" lang="en">Graduate</dim:field>
   <dim:field mdschema="others" element="access-status">open.access</dim:field>
</dim:dim>
</metadata></record></GetRecord></OAI-PMH>