Learning when to use lazy learning in constraint solving. / Gent, Ian P.; Jefferson, Chris; Kotthoff, Lars; Miguel, Ian; Moore, Neil C. A.; Nightingale, Peter; Petrie, Karen.
ECAI 2010: 19th European conference on artificial intelligence, 16-20 August 2010, Lisbon, Portugal - including Prestigious applications of artificial intelligence (PAIS-2010) proceedings. ed. / Helder Coelho; Rudi Studer; Michael Wooldridge. Amsterdam : IOS Press, 2010. p. 873-878 (Frontiers in artificial intelligence and applications).Research output: Chapter in Book/Report/Conference proceeding › Other chapter contribution
}
TY - CHAP
T1 - Learning when to use lazy learning in constraint solving
A1 - Gent,Ian P.
A1 - Jefferson,Chris
A1 - Kotthoff,Lars
A1 - Miguel,Ian
A1 - Moore,Neil C. A.
A1 - Nightingale,Peter
A1 - Petrie,Karen
AU - Gent,Ian P.
AU - Jefferson,Chris
AU - Kotthoff,Lars
AU - Miguel,Ian
AU - Moore,Neil C. A.
AU - Nightingale,Peter
AU - Petrie,Karen
PB - IOS Press
CY - Amsterdam
PY - 2010
Y1 - 2010
N2 - Learning in the context of constraint solving is a technique by which previously unknown constraints are uncovered during search and used to speed up subsequent search. Recently, lazy learning, similar to a successful idea from satisfiability modulo theories solvers, has been shown to be an effective means of incorporating constraint learning into a solver. Although a powerful technique to reduce search in some circumstances, lazy learning introduces a substantial overhead, which can outweigh its benefits. Hence, it is desirable to know beforehand whether or not it is expected to be useful. We approach this problem using machine learning (ML). We show that, in the context of a large benchmark set, standard ML approaches can be used to learn a simple, cheap classifier which performs well in identifying instances on which lazy learning should or should not be used. Furthermore, we demonstrate significant performance improvements of a system using our classifier and the lazy learning and standard constraint solvers over a standard solver. Through rigorous cross-validation across the different problem classes in our benchmark set, we show the general applicability of our learned classifier. © 2010 The authors and IOS Press. All rights reserved.
AB - Learning in the context of constraint solving is a technique by which previously unknown constraints are uncovered during search and used to speed up subsequent search. Recently, lazy learning, similar to a successful idea from satisfiability modulo theories solvers, has been shown to be an effective means of incorporating constraint learning into a solver. Although a powerful technique to reduce search in some circumstances, lazy learning introduces a substantial overhead, which can outweigh its benefits. Hence, it is desirable to know beforehand whether or not it is expected to be useful. We approach this problem using machine learning (ML). We show that, in the context of a large benchmark set, standard ML approaches can be used to learn a simple, cheap classifier which performs well in identifying instances on which lazy learning should or should not be used. Furthermore, we demonstrate significant performance improvements of a system using our classifier and the lazy learning and standard constraint solvers over a standard solver. Through rigorous cross-validation across the different problem classes in our benchmark set, we show the general applicability of our learned classifier. © 2010 The authors and IOS Press. All rights reserved.
UR - http://www.scopus.com/inward/record.url?partnerID=yv4JPVwI&eid=2-s2.0-77956051101&md5=80ab99f75715abdcae5348765788d509
U2 - 10.3233/978-1-60750-606-5-873
DO - 10.3233/978-1-60750-606-5-873
M1 - Other chapter contribution
SN - 9781607506058
BT - ECAI 2010
T2 - ECAI 2010
A2 - Wooldridge,Michael
ED - Wooldridge,Michael
T3 - Frontiers in artificial intelligence and applications
T3 - en_GB
SP - 873
EP - 878
ER -