Skip to main content

TS

The complexity of integer bound propagation

Authors

Lucas Bordeaux, Georgios Katsirelos, Nina Narodytska and Moshe Vardi

MSR
Cambridge
UK

LRI
Universite Paris-Sud 11

NICTA

UNSW

Rice University

Abstract

Bound propagation is an important Artificial Intelligence technique used in Constraint Programming tools to deal with numerical constraints. It is typically embedded within a search procedure ("branch and prune") and used at every node of the search tree to narrow down the search space, so it is critical that it be fast. The procedure invokes constraint propagators until a common fixpoint is reached, but the known algorithms for this have a \emph{pseudo}-polynomial worst-case time complexity: they are fast indeed when the variables have a small numerical range, but they have the well-known problem of being prohibitively slow when these ranges are large. An important question is therefore whether \emph{strongly-}polynomial algorithms exist that compute the common bound consistent fixpoint of a set of constraints. This paper answers this question. In particular we show that this fixpoint computation \emph{is in fact NP-complete}, even when restricted to binary linear constraints

BibTeX Entry

  @article{Bordeaux_KNV_11,
    journal          = {Journal of Artificial Intelligence Research},
    author           = {Bordeaux, Lucas and Katsirelos, Georgios and Narodytska, Nina and Vardi, Moshe},
    number           = {1},
    month            = apr,
    volume           = {40},
    year             = {2011},
    title            = {The Complexity of Integer Bound Propagation},
    pages            = { 657--676}
  }

Download

Served by Apache on Linux on seL4.