Advanced search options

Sorted by: relevance · author · university · date | New search

You searched for `subject:(Branching heuristic)`

.
Showing records 1 – 2 of
2 total matches.

▼ Search Limiters

University of Waterloo

1. Liang, Jia. Machine Learning for SAT Solvers.

Degree: 2018, University of Waterloo

URL: http://hdl.handle.net/10012/14207

Boolean SAT solvers are indispensable tools in a variety of domains in computer science and engineering where efficient search is required. Not only does this relieve the burden on the users of implementing their own search algorithm, they also leverage the surprising effectiveness of modern SAT solvers. Thanks to many decades of cumulative effort, researchers have made persistent improvements to SAT technology to the point where nowadays the best solvers are routinely used to solve extremely large instances with millions of variables. Even though our current paradigm of SAT solvers runs in worst-case exponential time, it appears that the techniques and heuristics embedded in these solvers avert the worst-case exponential time in practice. The implementations of these various solver heuristics and techniques are vital to the solvers effectiveness in practice.
The state-of-the-art heuristics and techniques gather data during the run of the solver to inform their choices like which variable to branch on next or when to invoke a restart. The goal of these choices is to minimize the solving time. The methods in which these heuristics and techniques process the data generally do not have theoretical underpinnings. Consequently, understanding why these heuristics and techniques perform so well in practice remains a challenge and systematically improving them is rather difficult. This goes to the heart of this thesis, that is to utilize machine learning to process the data as part of an optimization problem to minimize solving time. Research in machine learning exploded over the past decade due to its success in extracting useful information out of large volumes of data. Machine learning outclasses manual handcoding in a wide variety of complex tasks where data are plentiful. This is also the case in modern SAT solvers where propagations, conflict analysis, and clause learning produces plentiful of data to be analyzed, and exploiting this data to the fullest is naturally where machine learning comes in. Many machine learning techniques have a theoretical basis that makes them easy to analyze and understand why they perform well.
The branching heuristic is the first target for injecting machine learning. First we studied extant branching heuristics to understand what makes a branching heuristics good empirically. The fundamental observation is that good branching heuristics cause lots of clause learning by triggering conflicts as quickly as possible. This suggests that variables that cause conflicts are a valuable source of data. Another important observation is that the state-of-the-art VSIDS branching heuristic internally implements an exponential moving average. This highlights the importance of accounting for the temporal nature of the data when deciding to branch. These observations led to our proposal of a series of machine learning-based branching heuristics with the common goal of selecting the branching variables to increase probability of inducing conflicts. These branching heuristics are shown empirically to…

Subjects/Keywords: Branching heuristic; Restart; Reinforcement learning; Sat solver; Machine learning; Optimization

Record Details Similar Records

❌

APA · Chicago · MLA · Vancouver · CSE | Export to Zotero / EndNote / Reference Manager

APA (6^{th} Edition):

Liang, J. (2018). Machine Learning for SAT Solvers. (Thesis). University of Waterloo. Retrieved from http://hdl.handle.net/10012/14207

Note: this citation may be lacking information needed for this citation format:

Not specified: Masters Thesis or Doctoral Dissertation

Chicago Manual of Style (16^{th} Edition):

Liang, Jia. “Machine Learning for SAT Solvers.” 2018. Thesis, University of Waterloo. Accessed July 15, 2020. http://hdl.handle.net/10012/14207.

Note: this citation may be lacking information needed for this citation format:

Not specified: Masters Thesis or Doctoral Dissertation

MLA Handbook (7^{th} Edition):

Liang, Jia. “Machine Learning for SAT Solvers.” 2018. Web. 15 Jul 2020.

Vancouver:

Liang J. Machine Learning for SAT Solvers. [Internet] [Thesis]. University of Waterloo; 2018. [cited 2020 Jul 15]. Available from: http://hdl.handle.net/10012/14207.

Note: this citation may be lacking information needed for this citation format:

Not specified: Masters Thesis or Doctoral Dissertation

Council of Science Editors:

Liang J. Machine Learning for SAT Solvers. [Thesis]. University of Waterloo; 2018. Available from: http://hdl.handle.net/10012/14207

Not specified: Masters Thesis or Doctoral Dissertation

University of Waterloo

2.
Park, Vincent Se-jin.
AN EMPIRICAL STUDY OF DIFFERENT *BRANCHING* STRATEGIES FOR CONSTRAINT SATISFACTION PROBLEMS.

Degree: 2004, University of Waterloo

URL: http://hdl.handle.net/10012/1193

Many real life problems can be formulated as constraint satisfaction problems <i>(CSPs)</i>. Backtracking search algorithms are usually employed to solve <i>CSPs</i> 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 <i>CSPs</i>. 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'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 <i>CSPs</i>. 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.

Subjects/Keywords: Computer Science; BRANCHING; BRANCHING STRATEGY; CONSTRAINT; CONSTRAINT SATISFACTION PROBLEM; CONSTRAINT PROGRAMMING; DOMAIN SPLITTING; K-WAY BRANCHING; 2-WAY BRANCHING; BACKTRACKING SEARCH; VARIABLE ORDERING; HEURISTIC; OPTIMIZATION; DOMAIN SIZE; LEAST COMMITMENT

Record Details Similar Records

❌

APA · Chicago · MLA · Vancouver · CSE | Export to Zotero / EndNote / Reference Manager

APA (6^{th} Edition):

Park, V. S. (2004). AN EMPIRICAL STUDY OF DIFFERENT BRANCHING STRATEGIES FOR CONSTRAINT SATISFACTION PROBLEMS. (Thesis). University of Waterloo. Retrieved from http://hdl.handle.net/10012/1193

Not specified: Masters Thesis or Doctoral Dissertation

Chicago Manual of Style (16^{th} Edition):

Park, Vincent Se-jin. “AN EMPIRICAL STUDY OF DIFFERENT BRANCHING STRATEGIES FOR CONSTRAINT SATISFACTION PROBLEMS.” 2004. Thesis, University of Waterloo. Accessed July 15, 2020. http://hdl.handle.net/10012/1193.

Not specified: Masters Thesis or Doctoral Dissertation

MLA Handbook (7^{th} Edition):

Park, Vincent Se-jin. “AN EMPIRICAL STUDY OF DIFFERENT BRANCHING STRATEGIES FOR CONSTRAINT SATISFACTION PROBLEMS.” 2004. Web. 15 Jul 2020.

Vancouver:

Park VS. AN EMPIRICAL STUDY OF DIFFERENT BRANCHING STRATEGIES FOR CONSTRAINT SATISFACTION PROBLEMS. [Internet] [Thesis]. University of Waterloo; 2004. [cited 2020 Jul 15]. Available from: http://hdl.handle.net/10012/1193.

Not specified: Masters Thesis or Doctoral Dissertation

Council of Science Editors:

Park VS. AN EMPIRICAL STUDY OF DIFFERENT BRANCHING STRATEGIES FOR CONSTRAINT SATISFACTION PROBLEMS. [Thesis]. University of Waterloo; 2004. Available from: http://hdl.handle.net/10012/1193

Not specified: Masters Thesis or Doctoral Dissertation