Title :
Probing-Based Variable Selection Heuristics for NCSPs
Author :
Reyes, Victor ; Araya, Ignacio
Author_Institution :
Univ. Tec. Federico Santa Maria, Valparaiso, Chile
Abstract :
Interval branch & bound solvers are commonly used for solving numerical constraint satisfaction problems. They alternate filtering/contraction and branching steps in order to find small boxes containing all the solutions of the problem. The branching basically consists in generating two sub problems by dividing the domain of one variable into two. The selection of this variable is the topic of this work. Several heuristics have been proposed so far, most of them using local information from the current node (e.g., Domain sizes, partial derivative images over the current box, etc). We propose instead an approach based on past information. This information is provided by a preprocessing phase of the algorithm (probing) and is used during the search. In simple words, our algorithm attempts to identify the most important variables in a series of cheap test runs. As a result of probing, the variables are weighted. These weights are then considered by the selection heuristic during the search. Experiments stress the interest of using techniques based on past information in interval branch & bound solvers.
Keywords :
constraint satisfaction problems; tree searching; NCSP; branching step; contraction step; filtering step; interval branch-and-bound solvers; numerical constraint satisfaction problem; probing-based variable selection heuristics; variable selection; Algorithm design and analysis; Arrays; Heuristic algorithms; Input variables; Robustness; Search problems; Standards; branch & bound; interval-based solvers; probing; variable ordering heuristics;
Conference_Titel :
Tools with Artificial Intelligence (ICTAI), 2014 IEEE 26th International Conference on
Conference_Location :
Limassol
DOI :
10.1109/ICTAI.2014.14