{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2023,1,28]],"date-time":"2023-01-28T00:49:02Z","timestamp":1674866942280},"reference-count":14,"publisher":"World Scientific Pub Co Pte Lt","issue":"05","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Int. J. Artif. Intell. Tools"],"published-print":{"date-parts":[[2008,10]]},"abstract":"<jats:p> Backtracking search is often the method of choice for solving constraint satisfaction and propositional satisfiability problems. Previous studies have shown that portfolios of backtracking algorithms \u2014 a selection of one or more algorithms plus a schedule for executing the algorithms \u2014 can dramatically improve performance on some instances. In this paper, we consider a setting that often arises in practice where the instances to be solved arise over time, the instances all belong to some class of problem instances, and a limit or deadline is placed on the computational resources that can be consumed in solving any instance. For such a scenario, we present a simple scheme for learning a good portfolio of backtracking algorithms from a small sample of instances. We demonstrate the effectiveness of our approach through an extensive empirical evaluation using two testbeds: real-world instruction scheduling problems and the widely used quasigroup completion problems. <\/jats:p>","DOI":"10.1142\/s0218213008004187","type":"journal-article","created":{"date-parts":[[2008,11,6]],"date-time":"2008-11-06T11:50:07Z","timestamp":1225972207000},"page":"835-856","source":"Crossref","is-referenced-by-count":5,"title":["PORTFOLIOS WITH DEADLINES FOR BACKTRACKING SEARCH"],"prefix":"10.1142","volume":"17","author":[{"given":"HUAYUE","family":"WU","sequence":"first","affiliation":[{"name":"School of Computer Science, University of Waterloo, Waterloo, Ontario, Canada"}]},{"given":"PETER","family":"VAN BEEK","sequence":"additional","affiliation":[{"name":"School of Computer Science, University of Waterloo, Waterloo, Ontario, Canada"}]}],"member":"219","published-online":{"date-parts":[[2011,11,21]]},"reference":[{"key":"rf3","doi-asserted-by":"publisher","DOI":"10.1016\/S1574-6526(06)80007-6"},{"key":"rf4","doi-asserted-by":"publisher","DOI":"10.1111\/j.1467-8640.2005.00278.x"},{"key":"rf5","doi-asserted-by":"publisher","DOI":"10.1145\/368273.368557"},{"key":"rf6","doi-asserted-by":"crossref","first-page":"205","DOI":"10.1613\/jair.834","volume":"14","author":"Debruyne R.","journal-title":"J. Artificial Intelligence Research"},{"key":"rf7","doi-asserted-by":"crossref","first-page":"73","DOI":"10.1613\/jair.1195","volume":"19","author":"Finkelstein L.","journal-title":"J. of Artificial Intelligence Research"},{"key":"rf8","doi-asserted-by":"publisher","DOI":"10.1007\/s10472-006-9036-z"},{"key":"rf10","doi-asserted-by":"publisher","DOI":"10.1145\/321296.321300"},{"key":"rf14","doi-asserted-by":"publisher","DOI":"10.1016\/S0004-3702(00)00081-3"},{"key":"rf16","doi-asserted-by":"publisher","DOI":"10.1023\/A:1006314320276"},{"key":"rf22","doi-asserted-by":"publisher","DOI":"10.1126\/science.275.5296.51"},{"key":"rf24","doi-asserted-by":"publisher","DOI":"10.1016\/S1571-0653(04)00332-4"},{"key":"rf30","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(93)90029-9"},{"key":"rf36","doi-asserted-by":"publisher","DOI":"10.1016\/S1574-6526(06)80008-8"},{"key":"rf37","volume-title":"Data Mining","author":"Witten I. H.","year":"2000"}],"container-title":["International Journal on Artificial Intelligence Tools"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S0218213008004187","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,7]],"date-time":"2019-08-07T02:28:08Z","timestamp":1565144888000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S0218213008004187"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2008,10]]},"references-count":14,"journal-issue":{"issue":"05","published-online":{"date-parts":[[2011,11,21]]},"published-print":{"date-parts":[[2008,10]]}},"alternative-id":["10.1142\/S0218213008004187"],"URL":"https:\/\/doi.org\/10.1142\/s0218213008004187","relation":{},"ISSN":["0218-2130","1793-6349"],"issn-type":[{"value":"0218-2130","type":"print"},{"value":"1793-6349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2008,10]]}}}