Boosting autonomous search for CSPs via skylines
Introduction
Constraint programming (CP) is a widely employed technology for solving constraint satisfaction and optimization problems, that has successfully been employed to practical applications in various domains such as robotics [5], [39], rostering [21], [29], scheduling [36], [7], manufacturing [38], [2], supply chains [33], [27], allocation [35], [10] and bioinformatics [3], [1]. This technology allow users to model a problem as a constraint satisfaction problem (CSP), which can be seen as a formal problem representation mainly composed of an n-tuple of variables and an m-tuple of constraints. A CSP is solved once a n-tuple of values satisfying the constraints is found. The classical procedure for solving CSPs consists in employing a tree-data structure containing the possible solutions. Then, different algorithms can be used to explore and reach a solution, simple ones such as the well-known backtracking or more sophisticated ones such as the forward checking and maintaining arc consistency from the CP technology. In this context, two main phases are performed. The first one, called enumeration, assigns values to variables generating partial solutions that can be seen as branches of the tree. The second one, named propagation, tries to prune the tree by filtering from domains those values that do not lead to any solution.
The enumeration phase can be decomposed into two steps, the first one selects a variable from the problem and the second one temporarily assign a value to this variable. Both selections are controlled by the variable and value ordering heuristic, which together are known as the enumeration strategy. The enumeration strategy is an essential component of the solving process. A correct decision may dramatically reduce the solving time. In fact, perfect enumerations can reach a solution without performing backtracks on the search tree. However, much tuning can be done to choose the correct strategy, which in practice is a hard task as the performance of strategies is hard to predict. A modern proposal [23], named autonomous search (AS), addresses this concern. The idea is to let solvers adapt and control themselves during the solving phase in order to reach efficient solving processes but avoiding user involvement in tuning. In this way, simpler and powerful solvers will be available for non-expert users.
During the last two years, promising frameworks have incorporated AS in CP [15], [17], [30], [16], [37], [14], the goal is to provide adaptive solvers able to activate the most appropriate strategy on each part of the search tree. Strategies are selected on the fly from a quality rank and depending on their performance they may be replaced by more promising ones. A choice function is responsible for measuring the performance of strategies during the resolution. The performance is computed through several indicators which attempt to reflect the real state of progress in the problem resolution. An optimizer is commonly introduced to tune the computation of the choice function for a better rank generation. However, the optimization process is commonly costly and negatively impacts the performance of the whole resolution.
Considering the aforementioned concern, our research challenge is to boost the CSPs solving process by providing a more efficient way to rank the enumeration strategies. The main contribution of this paper is the design of an improved AS framework for CP able to reach faster resolution phases. On the one hand, the support of AS allow us to alleviate the burden of user involvement in solver tuning. On the other hand, the resolution process is enhanced by the integration of a powerful ranking technique from the database domain named skyline [8]. The use of skyline allows us to obviate the need for costly rank functions and optimizers, as a consequence the whole resolution is accelerated. We report encouraging results where the skyline-based approach is able to compete with previously reported autonomous search frameworks as well as to classic and more sophisticated heuristics such as impact-based search and .
The rest of this paper is organized as follows. Background information about CP and related works is presented in Section 2. The new approach based on skyline is described in Section 3. Section 4 presents the benchmark problems and the experimental results. Finally, in Section 5 we conclude.
Section snippets
Background information
In this section we briefly survey CSPs. Then, we present the related work.
The skyline approach
In this section we present our approach to boost AS solvers via skylines. We state that the use of skyline avoids the optimal configuration of the choice function leading to a faster solving process while preserving the quality of results. In the following, we survey briefly skyline and we present the details of our approach.
Experimental evaluation
In this Section we provide a performance evaluation of our approach. Experiments have been performed on a 2.33 GHz Intel Core2 Duo with 4 Gb RAM running Windows Vista, and the benchmarks employed are the following: n-queens (NQ) with n = {8, 10, 12, 15, 20, 50, 75}, magic squares (MS) with n = {3, 4, 5}, Sudoku, and knight tournament (Kn) with N = {5, 6}. The stop criterion is 65,535 steps, let us recall that a step refers to a request of the solver to instantiate a variable by enumeration. A portfolio
Conclusions
In this work, we have proposed an improved AS framework that employs skylines to perform adaptive enumeration processes. The main goal of skylines is to provide a more efficient and lightweight way to rank the enumeration strategies compared to the costly hyperheuristic used in previous approaches. The proposed skyline-based strategy is able to detect efficiently bad decisions concerning enumeration strategies allowing the solver to adapt itself while converging to an efficient strategy for the
Acknowledgements
Ricardo Soto is supported by Grant CONICYT/FONDECYT/INICIACION/ 11130459, Broderick Crawford is supported by Grant CONICYT/FONDECYT/ 1140897, and Fernando Paredes is supported by Grant CONICYT/FONDECYT/ 1130455.
References (40)
- et al.
Constraint programming for project-driven manufacturing
Int. J. Prod. Econ.
(2009) - et al.
Parameter tuning of a choice-function based hyperheuristic using particle swarm optimization
Expert Syst. Appl.
(2013) - et al.
A constraint programming based column generation approach to nurse rostering problems
Comput. OR
(2012) - et al.
Solving weighted CSP by maintaining arc consistency
Artif. Intell.
(2004) - et al.
Cell formation in group technology using constraint programming and Boolean satisfiability
Expert Syst. Appl.
(2012) - et al.
A constraint-based approach to fast and exact structure prediction in three-dimensional protein models
Constraints
(2006) - et al.
Constraint programming in structural bioinformatics
Constraints
(2008) - R. Barták, H. Rudová, Limited assignments: a new cutoff strategy for incomplete depth-first search, in: Proceedings of...
- et al.
Finding the maximal pose error in robotic mechanical systems using constraint programming
- et al.
Measuring search trees
Scheduling B2B meetings
The skyline operator
Boosting systematic search by weighting constraints
Solving the agricultural land allocation problem by constraint-based local search
An approach for dynamic split strategies in constraint solving
Skyline with presorting
Robustness in dynamic constraint satisfaction problems
Int. J. Innovat. Comput. Inform. Control
Dynamic selection of enumeration strategies for solving constraint satisfaction problems
Rom. J. Inf. Sci. Tech.
A hyperheuristic approach for dynamic enumeration strategy selection in constraint satisfaction
A framework for autonomous search in the eclipse solver
Cited by (13)
Maximum feasibility estimation
2021, Information SciencesA new metaheuristic based on vapor-liquid equilibrium for solving a new patient bed assignment problem
2020, Expert Systems with ApplicationsCitation Excerpt :Furthermore, we will improve the VLE algorithm by using an auto-adaptive approach such as (Zhao, Liu, Hao, Li, & Zuo, 2017), in order to measure the performance when there is no expert user to adjust the input parameters, and we try to solve the patient bed assignment problem. The integration of this new approach can lead the research toward new study lines, such as dynamically selecting the best enumeration strategy (in the search tree) during solving process according to performance indicators as analogously studied in (Soto et al., 2015; Soto et al., 2015; Soto et al., 2016; Soto et al., 2016). Carla Taramsco: Conceptualization, Formal analysis, Funding acquisition, Methodology, Resources, Supervision, Writing - original draft, Writing - review & editing.
Revealing household characteristics using connected home products
2019, Information SciencesCitation Excerpt :Solving CSPs consists of employing a tree data structure containing the possible solutions. Different algorithms can then be used to explore and reach a solution from simple ones, ranging from the well-known backtracking to more sophisticated ones such as forward checking and maintaining arc consistency [22,27]. Specific algorithms are also available for solving variants of CSPs such as dynamic CSPs [28], composite CSPs [29], weighted CSPs [30], fuzzy CSPs [31], and max-CSPs [32].
Using autonomous search for solving constraint satisfaction problems via new modern approaches
2016, Swarm and Evolutionary ComputationCitation Excerpt :Each approach (GA and PSO) is used as an optimizer for dynamic selection of strategies enumeration. Similar approaches have also been implemented for solving optimization problems instead of pure CSPs [20] and also implementing lightweight algorithms of selection as Skylines [21]. In Section 5, we provide a comparison of our approaches with the best AS optimizers reported in the literature.
A binary monkey search algorithm variation for solving the set covering problem
2020, Natural ComputingA new EEG software that supports emotion recognition by using an autonomous approach
2020, Neural Computing and Applications