Sökning: L773:1538 7755 OR L773:1055 9965 >
Solving Satisfactio...
Solving Satisfaction Problems using Large-Neighbourhood Search
-
- Björdal, Gustav, 1991- (författare)
- Uppsala universitet,Datalogi
-
- Flener, Pierre (författare)
- Uppsala universitet,Datalogi
-
- Pearson, Justin (författare)
- Uppsala universitet,Datalogi
-
visa fler...
-
- Stuckey, Peter J. (författare)
- Faculty of Information Technology, Monash University, Melbourne, Australia
-
- Tack, Guido (författare)
- Faculty of Information Technology, Monash University, Melbourne, Australia
-
visa färre...
-
(creator_code:org_t)
- 2020-09-02
- 2020
- Engelska.
-
Ingår i: Principles and Practice of Constraint Programming. - Cham : Springer International Publishing. - 9783030584740 - 9783030584757 ; , s. 55-71
- Relaterad länk:
-
https://urn.kb.se/re...
-
visa fler...
-
https://doi.org/10.1...
-
visa färre...
Abstract
Ämnesord
Stäng
- Large-neighbourhood search (LNS) improves an initial solution, hence it is not directly applicable to satisfaction problems. In order to use LNS in a constraint programming (CP) framework to solve satisfaction problems, we usually soften some hard-to-satisfy constraints by replacing them with penalty-function constraints. LNS is then used to reduce their penalty to zero, thus satisfying the original problem. However, this can give poor performance as the penalties rarely cause propagation and therefore do not drive each CP search, and by extension the LNS search, towards satisfying the replaced constraints until very late. Our key observation is that entirely replacing a constraint is often overkill, as the propagator for the replaced constraint could have performed some propagation without causing backtracking. We propose the notion of a non-failing propagator, which is subsumed just before causing a backtrack. We show that, by only making a few changes to an existing CP solver, any propagator can be made non-failing without modifying its code. Experimental evaluation shows that non-failing propagators, when used in conjunction with penalties, can greatly improve LNS performance compared to just having penalties. This allows us to leverage the power of the many sophisticated propagators that already exist in CP solvers, in order to use LNS for solving hard satisfaction problems and for finding initial solutions to hard-to-satisfy optimisation problems.
Ämnesord
- NATURVETENSKAP -- Data- och informationsvetenskap -- Datavetenskap (hsv//swe)
- NATURAL SCIENCES -- Computer and Information Sciences -- Computer Sciences (hsv//eng)
Nyckelord
- Computer Science
- Datavetenskap
Publikations- och innehållstyp
- ref (ämneskategori)
- kon (ämneskategori)
Hitta via bibliotek
Till lärosätets databas