Trap escape for local search by backtracking and conflict reverse

Paper


Duong, Huu-Phuoc, Duong, Thach-Thao, Pham, Duc Nghia, Sattar, Abdul and Duong, Anh Duc. 2013. "Trap escape for local search by backtracking and conflict reverse." Jaeger, Manfred, Nielsen, Thomas Dyhre and Viappiani, Paolo (ed.) 12th Scandinavian Conference on Artificial Intelligence (SCAI 2013). Aalborg, Denmark 20 - 22 Nov 2013 Amsterdam. https://doi.org/10.3233/978-1-61499-330-8-85
Paper/Presentation Title

Trap escape for local search by backtracking and conflict reverse

Presentation TypePaper
AuthorsDuong, Huu-Phuoc (Author), Duong, Thach-Thao (Author), Pham, Duc Nghia (Author), Sattar, Abdul (Author) and Duong, Anh Duc (Author)
EditorsJaeger, Manfred, Nielsen, Thomas Dyhre and Viappiani, Paolo
Journal or Proceedings TitleFrontiers in Artificial Intelligence and Applications
ERA Conference ID44019
Journal Citation257, pp. 85-94
Number of Pages10
Year2013
Place of PublicationAmsterdam
ISSN0922-6389
1879-8314
ISBN9781614993292
9781614993308
Digital Object Identifier (DOI)https://doi.org/10.3233/978-1-61499-330-8-85
Web Address (URL) of Paperhttps://ebooks.iospress.nl/publication/35449
Conference/Event12th Scandinavian Conference on Artificial Intelligence (SCAI 2013)
Scandinavian Conference on Artificial Intelligence
Event Details
Scandinavian Conference on Artificial Intelligence
SCAI
Rank
B
B
B
B
B
B
B
Event Details
12th Scandinavian Conference on Artificial Intelligence (SCAI 2013)
Event Date
20 to end of 22 Nov 2013
Event Location
Aalborg, Denmark
Abstract

This paper presents an efficient trap escape strategy in stochastic local search for Satisfiability. The proposed method aims to enhance local search by providing an alternative local minima escaping strategy. Our variable selection scheme provides a novel local minima escaping mechanism to explore new solution areas. Conflict variables are hypothesized as variables recently selected near local minima. Hence, a list of backtracked conflict variables is retrieved from local minima. The new strategy selects variables in the backtracked variable list based on the clause-weight scoring function and stagnation weights and variable weights as tiebreak criteria. This method is an alternative to the conventional method of selecting variables in a randomized unsatisfied clause. The proposed tiebreak method favors high stagnation weights and low variable weights during trap escape phases. The new strategies are examined on verification benchmark and SAT Competition 2011 and 2012 application and crafted instances. Our experiments show that proposed strategy has comparable performance with state-of-the-art local search solvers for SAT.

Keywordslocal search; SAT; Stagnation; Trap escape
ANZSRC Field of Research 2020460210. Satisfiability and optimisation
Byline AffiliationsVietnam National University, Vietnam
Griffith University
University of Information Technology, Vietnam
Institution of OriginUniversity of Southern Queensland
Permalink -

https://research.usq.edu.au/item/q7112/trap-escape-for-local-search-by-backtracking-and-conflict-reverse

  • 57
    total views
  • 3
    total downloads
  • 2
    views this month
  • 0
    downloads this month

Export as

Related outputs

Moving Objects Segmentation in Video Sequence based on Bayesian network
Duong, Thach-Thao and Duong, Anh-Duc. 2010. "Moving Objects Segmentation in Video Sequence based on Bayesian network." 8th IEEE-RIVF International Conference on Computing and Communication Technologies: Research, Innovation and Vision for the Future (RIVF 2010). Hanoi, Vietnam 01 - 04 Nov 2010 https://doi.org/10.1109/RIVF.2010.5633458
Trap Avoidance in Local Search Using Pseudo-Conflict Learning
Pham, Duc Nghia, Duong, Thach-Thao and Sattar, Abdul. 2012. "Trap Avoidance in Local Search Using Pseudo-Conflict Learning." 26th AAAI Conference on Artificial Intelligence (AAAI 2012). Toronto, Canada 22 - 26 Jul 2012 United States.
Weight-Enhanced Diversification in Stochastic Local Search for Satisfiability
Duong, Thach-Thao, Pham, Duc Nghia, Sattar, Abdul and Newton, M. A. Hakim. 2013. "Weight-Enhanced Diversification in Stochastic Local Search for Satisfiability." Rossi, Francesca (ed.) 23rd International Joint Conference on Artificial Intelligence (IJCAI 2013). Beijing, China 03 - 09 Aug 2013
Integrated data envelopment analysis: Linear vs. nonlinear model
Mahdiloo, Mahdi, Toloo, Mehdi, Duong, Thach-Thao, Saen, Reza Farzipoor and Tatham, Peter. 2018. "Integrated data envelopment analysis: Linear vs. nonlinear model." European Journal of Operational Research. 268 (1), pp. 255-267. https://doi.org/10.1016/j.ejor.2018.01.008
Some comments on improving discriminating power in data envelopment models based on deviation variables framework
Mahdiloo, Mahdi, Lim, Sungmook, Duong, Thach-Thao and Harvie, Charles. 2021. "Some comments on improving discriminating power in data envelopment models based on deviation variables framework." European Journal of Operational Research. 295 (1), pp. 394-397. https://doi.org/10.1016/j.ejor.2021.02.056
Diversify Intensification Phases in Local Search for SAT with a New Probability Distribution
Duong, Thach-Thao, Pham, Duc-Nghia and Sattar, Abdul. 2013. "Diversify Intensification Phases in Local Search for SAT with a New Probability Distribution." Cranefield, Stephen and Nayak, Abhaya (ed.) 26th Australasian Joint Conference on Artificial Intelligence (AI 2013). Dunedin, New Zealand 01 - 06 Dec 2013 Switzerland. https://doi.org/10.1007/978-3-319-03680-9_18
A Study of Local Minimum Avoidance Heuristics for SAT
Duong, Thach-Thao, Pham, Duc Nghia and Sattar, Abdul. 2012. "A Study of Local Minimum Avoidance Heuristics for SAT." De Raedt, Luc, Bessiere, Christian, Dubois, Didier, Doherty, Patrick, Frasconi, Paolo, Heintz, Fredrik and Lucas, Peter (ed.) 20th European Conference on Artificial Intelligence (ECAI 2012). Montpellier, France 27 - 31 Aug 2012 Netherlands. https://doi.org/10.3233/978-1-61499-098-7-300
A Method to Avoid Duplicative Flipping in Local Search for SAT
Duong, Thach-Thao, Pham, Duc Nghia and Sattar, Abdul. 2012. "A Method to Avoid Duplicative Flipping in Local Search for SAT." Thielscher, Michael and Zhang, Dongmo (ed.) 25th Australasian Joint Conference on Artificial Intelligence (AI 2012). Sydney, Australia 04 - 07 Dec 2012 Berlin. https://doi.org/10.1007/978-3-642-35101-3_19
Unsupervised Learning for Image Classification based on Distribution of Hierarchical Feature Tree
Duong, Thach-Thao, Lim, Joo-Hwee, Vu, Hai-Quan and Chevallet, Jean-Pierre. 2008. "Unsupervised Learning for Image Classification based on Distribution of Hierarchical Feature Tree." 2008 IEEE International Conference on Research, Innovation and Vision for the Future in Computing and Communication Technologies (RIVF 2008). Ho Chi Minh, Vietnam 13 - 17 Jul 2008 United States. https://doi.org/10.1109/RIVF.2008.4586371
Image retrieval based on visual information concepts and automatic image annotation
Ly, Quoc Ngoc, Duong, Anh Doc, Duong, Thach Thao and Ngo, Duc Thanh. 2006. "Image retrieval based on visual information concepts and automatic image annotation." Duc, Duong Anh, Dong, Thuy Thi Bich, Ho, Tu-Bao and Nguyen, Dinh Thuc (ed.) 1st International Conference on Theories and Applications of Computer Science (ICTACS 2006). Ho Chi Minh City, Vietnam 03 - 05 Aug 2006 United States. https://doi.org/10.1142/9789812772671_0006