Probing-Based Variable Selection Heuristics for NCSPs

Victor Reyes, Ignacio Araya

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

2 Scopus citations

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.

Original languageEnglish
Title of host publicationProceedings - 2014 IEEE 26th International Conference on Tools with Artificial Intelligence, ICTAI 2014
PublisherIEEE Computer Society
Pages16-23
Number of pages8
ISBN (Electronic)9781479965724
DOIs
StatePublished - 12 Dec 2014
Externally publishedYes
Event26th IEEE International Conference on Tools with Artificial Intelligence, ICTAI 2014 - Limassol, Cyprus
Duration: 10 Nov 201412 Nov 2014

Publication series

NameProceedings - International Conference on Tools with Artificial Intelligence, ICTAI
Volume2014-December
ISSN (Print)1082-3409

Conference

Conference26th IEEE International Conference on Tools with Artificial Intelligence, ICTAI 2014
Country/TerritoryCyprus
CityLimassol
Period10/11/1412/11/14

Keywords

  • branch & bound
  • interval-based solvers
  • probing
  • variable ordering heuristics

Fingerprint

Dive into the research topics of 'Probing-Based Variable Selection Heuristics for NCSPs'. Together they form a unique fingerprint.

Cite this