Probing-Based Variable Selection Heuristics for NCSPs

Victor Reyes, Ignacio Araya

Resultado de la investigación: Capítulo del libro/informe/acta de congresoContribución a la conferenciarevisión exhaustiva

2 Citas (Scopus)

Resumen

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.

Idioma originalInglés
Título de la publicación alojadaProceedings - 2014 IEEE 26th International Conference on Tools with Artificial Intelligence, ICTAI 2014
EditorialIEEE Computer Society
Páginas16-23
Número de páginas8
ISBN (versión digital)9781479965724
DOI
EstadoPublicada - 12 dic 2014
Publicado de forma externa
Evento26th IEEE International Conference on Tools with Artificial Intelligence, ICTAI 2014 - Limassol, Chipre
Duración: 10 nov 201412 nov 2014

Serie de la publicación

NombreProceedings - International Conference on Tools with Artificial Intelligence, ICTAI
Volumen2014-December
ISSN (versión impresa)1082-3409

Conferencia

Conferencia26th IEEE International Conference on Tools with Artificial Intelligence, ICTAI 2014
País/TerritorioChipre
CiudadLimassol
Período10/11/1412/11/14

Huella

Profundice en los temas de investigación de 'Probing-Based Variable Selection Heuristics for NCSPs'. En conjunto forman una huella única.

Citar esto