caa a22 4500 463202686 CHVBK 20180405153116.0 cr unu---uuuuu 170326e20071201xx s 000 0 eng 10.1007/s10732-007-9020-8 doi (NATIONALLICENCE)springer-10.1007/s10732-007-9020-8 The island confinement method for reducing search space in local search methods [Elektronische Daten] [H. Fang, Y. Kilani, J. Lee, P. Stuckey] Typically local search methods for solving constraint satisfaction problems such as GSAT, WalkSAT, DLM, and ESG treat the problem as an optimisation problem. Each constraint contributes part of a penalty function in assessing trial valuations. Local search examines the neighbours of the current valuation, using the penalty function to determine a "better” neighbour valuation to move to, until finally a solution which satisfies all the constraints is found. In this paper we investigate using some of the constraints as "hard” constraints, that are always satisfied by every trial valuation visited, rather than as part of a penalty function. In this way these constraints reduce the possible neighbours in each move and also the overall search space. The treating of some constraints as hard requires that the space of valuations that are satisfied is "connected” in order to guarantee that a solution can be found from any starting position within the region; thus the concept of islands and the name "island confinement method” arises. Treating some constraints as hard provides new difficulties for the search mechanism since the search space becomes more jagged, and there are more deep local minima. A new escape strategy is needed. To demonstrate the feasibility and generality of our approach, we show how the island confinement method can be incorporated in, and significantly improve, the search performance of two successful local search procedures, DLM and ESG, on SAT problems arising from binary CSPs. Springer Science+Business Media, LLC, 2007 Local search nationallicence SAT nationallicence Constraint satisfaction nationallicence Fang H. Department of Computer Science, Yale University, New Haven, USA aut Kilani Y. Department of Computer Science and Engineering, The Chinese University of Hong Kong, Shatin, N.T., Hong Kong aut Lee J. Department of Computer Science and Engineering, The Chinese University of Hong Kong, Shatin, N.T., Hong Kong aut Stuckey P. NICTA Victoria Laboratory, Department of Computer Science and Software Engineering, University of Melbourne, Melbourne, Australia aut Journal of Heuristics Springer US; http://www.springer-ny.com 13/6(2007-12-01), 557-585 1381-1231 13:6<557 2007 13 10732 https://doi.org/10.1007/s10732-007-9020-8 text/html Onlinezugriff via DOI 1 research-article jats NATIONALLICENCE 856 40 https://doi.org/10.1007/s10732-007-9020-8 text/html Onlinezugriff via DOI NATIONALLICENCE 700 1- Fang H. Department of Computer Science, Yale University, New Haven, USA aut NATIONALLICENCE 700 1- Kilani Y. Department of Computer Science and Engineering, The Chinese University of Hong Kong, Shatin, N.T., Hong Kong aut NATIONALLICENCE 700 1- Lee J. Department of Computer Science and Engineering, The Chinese University of Hong Kong, Shatin, N.T., Hong Kong aut NATIONALLICENCE 700 1- Stuckey P. NICTA Victoria Laboratory, Department of Computer Science and Software Engineering, University of Melbourne, Melbourne, Australia aut NATIONALLICENCE 773 0- Journal of Heuristics Springer US; http://www.springer-ny.com 13/6(2007-12-01), 557-585 1381-1231 13:6<557 2007 13 10732 Metadata rights reserved Springer special CC-BY-NC licence nationallicence BK010053 XK010053 XK010000 NATIONALLICENCE NATIONALLICENCE NL-springer