Analysis and extension of the Inc* on the satisfiability testing problem

Mohamed Bader; R. Poli

Analysis and extension of the Inc* on the satisfiability testing problem

Mohamed Bader
, R. Poli

Research output: Chapter in Book/Report/Conference proceeding › Chapter (peer-reviewed) › peer-review

189 Downloads (Pure)

Abstract

Inc (star) is a general algorithm that can be used in conjunction with any local search heuristic and that has the potential to substantially improve the overall performance of the heuristic. The general idea of the algorithm is the following. Rather than attempting to directly solve a difficult problem, the algorithm dynamically chooses a smaller instance of the problem, and then increases the size of the instance only after the previous simplified instances have been solved, until the full size of the problem is reached. Genetic programming is used to discover new strategies for Inc^*. Preliminary experiments on the satisfiability problem (SAT) problem have shown that Inc^* is a competitive approach. In this paper we enhance Inc^* and we experimentally test it on larger set of benchmarks, including big instances of SAT. Furthermore, we provide an analysis of the algorithm's behaviour.

Original language	English
Title of host publication	Evolutionary Computation, 2008. CEC 2008. (IEEE World Congress on Computational Intelligence). IEEE Congress on
Place of Publication	Hong Kong
Publisher	Institute of Electrical and Electronics Engineers Inc.
Pages	3342-3349
Number of pages	8
ISBN (Print)	9781424418220
Publication status	Published - Jun 2008
Event	2008 IEEE World Congress on Computational Intelligence - Hong Kong Duration: 1 Jun 2008 → 6 Jun 2008

Conference

Conference	2008 IEEE World Congress on Computational Intelligence
Period	1/06/08 → 6/06/08

Keywords

Genetic Programming
SAT
Combinatorial Optimization

Access to Document

wcci2008.pdfFinal published version, 365 KB

http://ieeexplore.ieee.org/xpls/abs_all.jsp?arnumber=4631250&tag=1

Cite this

@inbook{db577faf5887436ba311d23654e30ff3,

title = "Analysis and extension of the Inc* on the satisfiability testing problem",

abstract = "Inc (star) is a general algorithm that can be used in conjunction with any local search heuristic and that has the potential to substantially improve the overall performance of the heuristic. The general idea of the algorithm is the following. Rather than attempting to directly solve a difficult problem, the algorithm dynamically chooses a smaller instance of the problem, and then increases the size of the instance only after the previous simplified instances have been solved, until the full size of the problem is reached. Genetic programming is used to discover new strategies for Inc*. Preliminary experiments on the satisfiability problem (SAT) problem have shown that Inc* is a competitive approach. In this paper we enhance Inc* and we experimentally test it on larger set of benchmarks, including big instances of SAT. Furthermore, we provide an analysis of the algorithm's behaviour.",

keywords = "Genetic Programming, SAT, Combinatorial Optimization",

author = "Mohamed Bader and R. Poli",

note = "Funders: EPSRC (grants EP/C523377/1 and EP/C523385/1). Additional Information: DOI: 10.1109/CEC.2008.4631250.; 2008 IEEE World Congress on Computational Intelligence ; Conference date: 01-06-2008 Through 06-06-2008",

year = "2008",

month = jun,

language = "English",

isbn = "9781424418220",

pages = "3342--3349",

booktitle = "Evolutionary Computation, 2008. CEC 2008. (IEEE World Congress on Computational Intelligence). IEEE Congress on",

publisher = "Institute of Electrical and Electronics Engineers Inc.",

address = "United States",

}

Bader, M & Poli, R 2008, Analysis and extension of the Inc* on the satisfiability testing problem. in Evolutionary Computation, 2008. CEC 2008. (IEEE World Congress on Computational Intelligence). IEEE Congress on. Institute of Electrical and Electronics Engineers Inc., Hong Kong, pp. 3342-3349, 2008 IEEE World Congress on Computational Intelligence, 1/06/08. <http://ieeexplore.ieee.org/xpls/abs_all.jsp?arnumber=4631250&tag=1>

Analysis and extension of the Inc* on the satisfiability testing problem. / Bader, Mohamed; Poli, R.
Evolutionary Computation, 2008. CEC 2008. (IEEE World Congress on Computational Intelligence). IEEE Congress on. Hong Kong: Institute of Electrical and Electronics Engineers Inc., 2008. p. 3342-3349.

Research output: Chapter in Book/Report/Conference proceeding › Chapter (peer-reviewed) › peer-review

TY - CHAP

T1 - Analysis and extension of the Inc* on the satisfiability testing problem

AU - Bader, Mohamed

AU - Poli, R.

N1 - Funders: EPSRC (grants EP/C523377/1 and EP/C523385/1). Additional Information: DOI: 10.1109/CEC.2008.4631250.

PY - 2008/6

Y1 - 2008/6

N2 - Inc (star) is a general algorithm that can be used in conjunction with any local search heuristic and that has the potential to substantially improve the overall performance of the heuristic. The general idea of the algorithm is the following. Rather than attempting to directly solve a difficult problem, the algorithm dynamically chooses a smaller instance of the problem, and then increases the size of the instance only after the previous simplified instances have been solved, until the full size of the problem is reached. Genetic programming is used to discover new strategies for Inc*. Preliminary experiments on the satisfiability problem (SAT) problem have shown that Inc* is a competitive approach. In this paper we enhance Inc* and we experimentally test it on larger set of benchmarks, including big instances of SAT. Furthermore, we provide an analysis of the algorithm's behaviour.

AB - Inc (star) is a general algorithm that can be used in conjunction with any local search heuristic and that has the potential to substantially improve the overall performance of the heuristic. The general idea of the algorithm is the following. Rather than attempting to directly solve a difficult problem, the algorithm dynamically chooses a smaller instance of the problem, and then increases the size of the instance only after the previous simplified instances have been solved, until the full size of the problem is reached. Genetic programming is used to discover new strategies for Inc*. Preliminary experiments on the satisfiability problem (SAT) problem have shown that Inc* is a competitive approach. In this paper we enhance Inc* and we experimentally test it on larger set of benchmarks, including big instances of SAT. Furthermore, we provide an analysis of the algorithm's behaviour.

KW - Genetic Programming

KW - SAT

KW - Combinatorial Optimization

M3 - Chapter (peer-reviewed)

SN - 9781424418220

SP - 3342

EP - 3349

BT - Evolutionary Computation, 2008. CEC 2008. (IEEE World Congress on Computational Intelligence). IEEE Congress on

PB - Institute of Electrical and Electronics Engineers Inc.

CY - Hong Kong

T2 - 2008 IEEE World Congress on Computational Intelligence

Y2 - 1 June 2008 through 6 June 2008

ER -

Analysis and extension of the Inc* on the satisfiability testing problem

Abstract

Conference

Keywords

Access to Document

Fingerprint

Cite this