Diversify Intensification Phases in Local Search for SAT with a New Probability Distribution

Paper

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

Paper/Presentation Title	Diversify Intensification Phases in Local Search for SAT with a New Probability Distribution
Presentation Type	Paper
Authors	Duong, Thach-Thao (Author), Pham, Duc-Nghia (Author) and Sattar, Abdul (Author)
Editors	Cranefield, Stephen and Nayak, Abhaya
Journal or Proceedings Title	Lecture Notes in Artificial Intelligence (Book series)
ERA Conference ID	42498
Journal Citation	8272, pp. 166-177
Number of Pages	12
Year	2013
Place of Publication	Switzerland
ISBN	9783319036793
	9783319036809
Digital Object Identifier (DOI)	https://doi.org/10.1007/978-3-319-03680-9_18
Web Address (URL) of Paper	https://link.springer.com/chapter/10.1007/978-3-319-03680-9_18
Conference/Event	26th Australasian Joint Conference on Artificial Intelligence (AI 2013)
	Australasian Joint Conference on Artificial Intelligence
Event Details	Australasian Joint Conference on Artificial Intelligence AI Rank B B B B B B B
Event Details	26th Australasian Joint Conference on Artificial Intelligence (AI 2013) Event Date 01 to end of 06 Dec 2013 Event Location Dunedin, New Zealand
Abstract	A key challenge in developing efficient local search solvers is to intelligently balance diversification and intensification. This study proposes a heuristic that integrates a new dynamic scoring function and two different diversification criteria: variable weights and stagnation weights. Our new dynamic scoring function is formulated to enhance the diversification capability in intensification phases using a user-defined diversification parameter. The formulation of the new scoring function is based on a probability distribution to adjust the selecting priorities of the selection between greediness on scores and diversification on variable properties. The probability distribution of variables on greediness is constructed to guarantee the synchronization between the probability distribution functions and score values. Additionally, the new dynamic scoring function is integrated with the two diversification criteria. The experiments show that the new heuristic is efficient on verification benchmark, crafted and random instances.
Keywords	Artificial intelligence; Distribution functions
ANZSRC Field of Research 2020	460210. Satisfiability and optimisation
Byline Affiliations	Griffith University
Institution of Origin	University of Southern Queensland

Permalink -

https://research.usq.edu.au/item/q710z/diversify-intensification-phases-in-local-search-for-sat-with-a-new-probability-distribution

64
total views
3
total downloads
1
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

Trap escape for local search by backtracking and conflict reverse

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

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

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