Metareasoning about propagators for constraint satisfaction
| dc.contributor.advisor | Horsch, Michael | en_US |
| dc.contributor.committeeMember | McQuillan, Ian | en_US |
| dc.contributor.committeeMember | Vassileva, Julita | en_US |
| dc.contributor.committeeMember | Bremner, Murray | en_US |
| dc.creator | Thompson, Craig Daniel Stewart | en_US |
| dc.date.accessioned | 2011-06-13T11:25:41Z | en_US |
| dc.date.accessioned | 2013-01-04T04:38:23Z | |
| dc.date.available | 2012-07-11T08:00:00Z | en_US |
| dc.date.available | 2013-01-04T04:38:23Z | |
| dc.date.created | 2011-05 | en_US |
| dc.date.issued | 2011-05 | en_US |
| dc.date.submitted | May 2011 | en_US |
| dc.description.abstract | Given the breadth of constraint satisfaction problems (CSPs) and the wide variety of CSP solvers, it is often very difficult to determine a priori which solving method is best suited to a problem. This work explores the use of machine learning to predict which solving method will be most effective for a given problem. We use four different problem sets to determine the CSP attributes that can be used to determine which solving method should be applied. After choosing an appropriate set of attributes, we determine how well j48 decision trees can predict which solving method to apply. Furthermore, we take a cost sensitive approach such that problem instances where there is a great difference in runtime between algorithms are emphasized. We also attempt to use information gained on one class of problems to inform decisions about a second class of problems. Finally, we show that the additional costs of deciding which method to apply are outweighed by the time savings compared to applying the same solving method to all problem instances. | en_US |
| dc.identifier.uri | http://hdl.handle.net/10388/etd-06132011-112541 | en_US |
| dc.language.iso | en_US | en_US |
| dc.subject | performance prediction | en_US |
| dc.subject | algorithm selection | en_US |
| dc.subject | propagation | en_US |
| dc.subject | machine learning | en_US |
| dc.title | Metareasoning about propagators for constraint satisfaction | en_US |
| dc.type.genre | Thesis | en_US |
| dc.type.material | text | en_US |
| thesis.degree.department | Computer Science | en_US |
| thesis.degree.discipline | Computer Science | en_US |
| thesis.degree.grantor | University of Saskatchewan | en_US |
| thesis.degree.level | Masters | en_US |
| thesis.degree.name | Master of Science (M.Sc.) | en_US |