TY - JOUR

T1 - Using autonomous search for solving constraint satisfaction problems via new modern approaches

AU - Soto, Ricardo

AU - Crawford, Broderick

AU - Olivares, Rodrigo

AU - Galleguillos, Cristian

AU - Castro, Carlos

AU - Johnson, Franklin

AU - Paredes, Fernando

AU - Norero, Enrique

N1 - Publisher Copyright:
© 2016 Elsevier B.V.

PY - 2016/10/1

Y1 - 2016/10/1

N2 - Constraint Programming is a powerful paradigm which allows the resolution of many complex problems, such as scheduling, planning, and configuration. These problems are defined by a set of variables and a set of constraints. Each variable has non-empty domain of possible value and each constraint involves some subset of the variables and specifies the allowable combinations of values for that subset. The resolution of these problems is carried out by a constraint satisfaction solver which explores a search tree of potential solutions. This exploration is controlled by the enumeration strategy, which is responsible for choosing the order in which variables and values are selected to generate the potential solution. There exist different ways to perform this selection, and depending on the quality of this decision, the efficiency of the solving process may dramatically vary. Autonomous search is a particular case of adaptive systems that aims at improving its solving performance by adapting itself to the problem at hand without manual configuration of an expert user. The goal is to improve their solving performance by modifying and adjusting themselves, either by self-adaptation or by supervised adaptation. This approach has been effectively applied to different optimization and satisfaction techniques such as constraint programming, metaheuristics, and SAT. In this paper, we present a new Autonomous Search approach for constraint programming based on four modern bio-inspired metaheuristics. The goal of those metaheuristics is to optimize the self-tuning phase of the constraint programming search process. We illustrate promising results, where the proposed approach is able to efficiently solve several well-known constraint satisfaction problems.

AB - Constraint Programming is a powerful paradigm which allows the resolution of many complex problems, such as scheduling, planning, and configuration. These problems are defined by a set of variables and a set of constraints. Each variable has non-empty domain of possible value and each constraint involves some subset of the variables and specifies the allowable combinations of values for that subset. The resolution of these problems is carried out by a constraint satisfaction solver which explores a search tree of potential solutions. This exploration is controlled by the enumeration strategy, which is responsible for choosing the order in which variables and values are selected to generate the potential solution. There exist different ways to perform this selection, and depending on the quality of this decision, the efficiency of the solving process may dramatically vary. Autonomous search is a particular case of adaptive systems that aims at improving its solving performance by adapting itself to the problem at hand without manual configuration of an expert user. The goal is to improve their solving performance by modifying and adjusting themselves, either by self-adaptation or by supervised adaptation. This approach has been effectively applied to different optimization and satisfaction techniques such as constraint programming, metaheuristics, and SAT. In this paper, we present a new Autonomous Search approach for constraint programming based on four modern bio-inspired metaheuristics. The goal of those metaheuristics is to optimize the self-tuning phase of the constraint programming search process. We illustrate promising results, where the proposed approach is able to efficiently solve several well-known constraint satisfaction problems.

KW - Autonomous search

KW - Constraint programming

KW - Constraint satisfaction problems

KW - Enumeration strategies

KW - Metaheuristics

KW - Optimizer-algorithms

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

U2 - 10.1016/j.swevo.2016.04.003

DO - 10.1016/j.swevo.2016.04.003

M3 - Article

AN - SCOPUS:84964595985

SN - 2210-6502

VL - 30

SP - 64

EP - 77

JO - Swarm and Evolutionary Computation

JF - Swarm and Evolutionary Computation

ER -