The complexity of integer bound propagation

DOI10.1613/JAIR.3248zbMATH Open1216.68238arXiv1401.3887OpenAlexW3103893175WikidataQ129518304 ScholiaQ129518304MaRDI QIDQ2996913FDOQ2996913

Authors: Lucas Bordeaux, George Katsirelos, Nina Narodytska, Moshe Y. Vardi 

Publication date: 4 May 2011

Published in: Journal of Artificial Intelligence Research (Search for Journal in Brave)

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 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 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 is in fact NP-complete, even when restricted to binary linear constraints.

Full work available at URL: https://arxiv.org/abs/1401.3887

Recommendations

• The complexity of reasoning with global constraints
• An Analysis of Slow Convergence in Interval Propagation
• Principles and Practice of Constraint Programming – CP 2004
• scientific article; zbMATH DE number 2080331
• Dynamic Analysis of Bounds Versus Domain Propagation

Mathematics Subject Classification ID

Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Analysis of algorithms and problem complexity (68Q25)

Cited In (3)

• An algorithm-independent measure of progress for linear constraint propagation
• An Analysis of Slow Convergence in Interval Propagation
• Domain reduction techniques for global NLP and MINLP optimization

This page was built for publication: The complexity of integer bound propagation

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2996913)