Reducing search space in local search for constraint satisfaction

H. Fang, Y. Kilani, J. H.M. Lee, P. J. Stuckey

Research output: Contribution to conferencePaper

2 Citations (Scopus)

Abstract

Typically local search methods for solving constraint satisfaction problems such as GSAT, WalkSAT and DLM treat the problem as an optimization 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 valuations to move to, until finally a solution which satisfies all constraints is found. In this paper we investigate using some of the constraints, rather than as part of a penalty function, as "hard" constraints, that are always satisfied by every trial valuation visited. In this way the 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. Treating some constraints as hard also provides 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. We show in this paper how, for DIMACS translations of binary CSPs, treating some constraints as hard can significantly improve search performance of the DLM local search method.

Original languageEnglish
Pages28-33
Number of pages6
Publication statusPublished - 1 Dec 2002
Externally publishedYes
EventNational Conference on Artificial Intelligence (AAAI-02), 14th Innovative Applications of Artificial Intelligence Conference (IAAI-02) - Edmonton, Alta., Canada
Duration: 28 Jul 20021 Aug 2002
Conference number: 18th

Conference

ConferenceNational Conference on Artificial Intelligence (AAAI-02), 14th Innovative Applications of Artificial Intelligence Conference (IAAI-02)
CountryCanada
CityEdmonton, Alta.
Period28/07/021/08/02

Keywords

  • Binary CSP
  • Local search
  • SAT

Cite this

Fang, H., Kilani, Y., Lee, J. H. M., & Stuckey, P. J. (2002). Reducing search space in local search for constraint satisfaction. 28-33. Paper presented at National Conference on Artificial Intelligence (AAAI-02), 14th Innovative Applications of Artificial Intelligence Conference (IAAI-02), Edmonton, Alta., Canada.
Fang, H. ; Kilani, Y. ; Lee, J. H.M. ; Stuckey, P. J. / Reducing search space in local search for constraint satisfaction. Paper presented at National Conference on Artificial Intelligence (AAAI-02), 14th Innovative Applications of Artificial Intelligence Conference (IAAI-02), Edmonton, Alta., Canada.6 p.
@conference{1c23b339da1f4cdbbe9f142509d6dd5f,
title = "Reducing search space in local search for constraint satisfaction",
abstract = "Typically local search methods for solving constraint satisfaction problems such as GSAT, WalkSAT and DLM treat the problem as an optimization 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 valuations to move to, until finally a solution which satisfies all constraints is found. In this paper we investigate using some of the constraints, rather than as part of a penalty function, as {"}hard{"} constraints, that are always satisfied by every trial valuation visited. In this way the 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. Treating some constraints as hard also provides 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. We show in this paper how, for DIMACS translations of binary CSPs, treating some constraints as hard can significantly improve search performance of the DLM local search method.",
keywords = "Binary CSP, Local search, SAT",
author = "H. Fang and Y. Kilani and Lee, {J. H.M.} and Stuckey, {P. J.}",
year = "2002",
month = "12",
day = "1",
language = "English",
pages = "28--33",
note = "National Conference on Artificial Intelligence (AAAI-02), 14th Innovative Applications of Artificial Intelligence Conference (IAAI-02) ; Conference date: 28-07-2002 Through 01-08-2002",

}

Fang, H, Kilani, Y, Lee, JHM & Stuckey, PJ 2002, 'Reducing search space in local search for constraint satisfaction' Paper presented at National Conference on Artificial Intelligence (AAAI-02), 14th Innovative Applications of Artificial Intelligence Conference (IAAI-02), Edmonton, Alta., Canada, 28/07/02 - 1/08/02, pp. 28-33.

Reducing search space in local search for constraint satisfaction. / Fang, H.; Kilani, Y.; Lee, J. H.M.; Stuckey, P. J.

2002. 28-33 Paper presented at National Conference on Artificial Intelligence (AAAI-02), 14th Innovative Applications of Artificial Intelligence Conference (IAAI-02), Edmonton, Alta., Canada.

Research output: Contribution to conferencePaper

TY - CONF

T1 - Reducing search space in local search for constraint satisfaction

AU - Fang, H.

AU - Kilani, Y.

AU - Lee, J. H.M.

AU - Stuckey, P. J.

PY - 2002/12/1

Y1 - 2002/12/1

N2 - Typically local search methods for solving constraint satisfaction problems such as GSAT, WalkSAT and DLM treat the problem as an optimization 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 valuations to move to, until finally a solution which satisfies all constraints is found. In this paper we investigate using some of the constraints, rather than as part of a penalty function, as "hard" constraints, that are always satisfied by every trial valuation visited. In this way the 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. Treating some constraints as hard also provides 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. We show in this paper how, for DIMACS translations of binary CSPs, treating some constraints as hard can significantly improve search performance of the DLM local search method.

AB - Typically local search methods for solving constraint satisfaction problems such as GSAT, WalkSAT and DLM treat the problem as an optimization 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 valuations to move to, until finally a solution which satisfies all constraints is found. In this paper we investigate using some of the constraints, rather than as part of a penalty function, as "hard" constraints, that are always satisfied by every trial valuation visited. In this way the 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. Treating some constraints as hard also provides 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. We show in this paper how, for DIMACS translations of binary CSPs, treating some constraints as hard can significantly improve search performance of the DLM local search method.

KW - Binary CSP

KW - Local search

KW - SAT

UR - http://www.scopus.com/inward/record.url?scp=0036923170&partnerID=8YFLogxK

M3 - Paper

AN - SCOPUS:0036923170

SP - 28

EP - 33

ER -

Fang H, Kilani Y, Lee JHM, Stuckey PJ. Reducing search space in local search for constraint satisfaction. 2002. Paper presented at National Conference on Artificial Intelligence (AAAI-02), 14th Innovative Applications of Artificial Intelligence Conference (IAAI-02), Edmonton, Alta., Canada.