Tractability-preserving Transformations of Global Cost Functions

Autor: Simon de Givry, Jimmy H. M. Lee, David Allouche, Patricia Gutierrez, Samir Loudni, Yi Wu, Jean-Philippe Métivier, Patrice Boizumault, K. L. Leung, Christian Bessiere, Thomas Schiex
Přispěvatelé: Unité de Mathématiques et Informatique Appliquées de Toulouse (MIAT INRA), Institut National de la Recherche Agronomique (INRA), Agents, Apprentissage, Contraintes (COCONUT), Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier (LIRMM), Université de Montpellier (UM)-Centre National de la Recherche Scientifique (CNRS)-Université de Montpellier (UM)-Centre National de la Recherche Scientifique (CNRS), Equipe CODAG - Laboratoire GREYC - UMR6072, Groupe de Recherche en Informatique, Image, Automatique et Instrumentation de Caen (GREYC), Université de Caen Normandie (UNICAEN), Normandie Université (NU)-Normandie Université (NU)-École Nationale Supérieure d'Ingénieurs de Caen (ENSICAEN), Normandie Université (NU)-Centre National de la Recherche Scientifique (CNRS)-Université de Caen Normandie (UNICAEN), Normandie Université (NU)-Centre National de la Recherche Scientifique (CNRS), Unité de Biométrie et Intelligence Artificielle (UBIA), Artificial Intelligence Research Institute / Spanish Scientific Research Council (IIIA / CSIC), Universitat Autònoma de Barcelona [Barcelona] (UAB), Centre National de la Recherche Scientifique (CNRS)-Université de Montpellier (UM)-Centre National de la Recherche Scientifique (CNRS)-Université de Montpellier (UM), Groupe de Recherche en Informatique, Image et Instrumentation de Caen (GREYC), Centre National de la Recherche Scientifique (CNRS)-École Nationale Supérieure d'Ingénieurs de Caen (ENSICAEN), Normandie Université (NU)-Normandie Université (NU)-Université de Caen Normandie (UNICAEN), Normandie Université (NU)-Centre National de la Recherche Scientifique (CNRS)-École Nationale Supérieure d'Ingénieurs de Caen (ENSICAEN), Normandie Université (NU), Universitat Autònoma de Barcelona (UAB), Agence Nationale de la Recherche' [ANR-10-BLA-0214], 'Partenariat Hubert Curien PROCORE' [28680VH], Research Grants Council of Hong Kong SAR grant [CUHK413710, F-HK019/12T], 'Consulat General de France de Hong Kong', Schiex, Thomas, Agence Nationale de la Recherche (France), Research Grants Council (Hong Kong)
Jazyk: angličtina
Rok vydání: 2016
Předmět:
Zdroj: Artificial Intelligence
Artificial Intelligence, Elsevier, 2016, 238, pp.166-189. ⟨10.1016/j.artint.2016.06.005⟩
Artificial Intelligence (238), 166-189. (2016)
Digital.CSIC. Repositorio Institucional del CSIC
instname
ISSN: 0004-3702
DOI: 10.1016/j.artint.2016.06.005⟩
Popis: Graphical model processing is a central problem in artificial intelligence. The optimization of the combined cost of a network of local cost functions federates a variety of famous problems including CSP, SAT and Max-SAT but also optimization in stochastic variants such as Markov Random Fields and Bayesian networks. Exact solving methods for these problems typically include branch and bound and local inference-based bounds. In this paper we are interested in understanding when and how dynamic programming based optimization can be used to efficiently enforce soft local consistencies on Global Cost Functions, defined as parameterized families of cost functions of unbounded arity. Enforcing local consistencies in cost function networks is performed by applying so-called Equivalence Preserving Transformations (EPTs) to the cost functions. These EPTs may transform global cost functions and make them intractable to optimize. We identify as tractable projection-safe those global cost functions whose optimization is and remains tractable after applying the EPTs used for enforcing arc consistency. We also provide new classes of cost functions that are tractable projection-safe thanks to dynamic programming. We show that dynamic programming can either be directly used inside filtering algorithms, defining polynomially DAG-filterable cost functions, or emulated by arc consistency filtering on a Berge-acyclic network of bounded-arity cost functions, defining Berge-acyclic network-decomposable cost functions. We give examples of such cost functions and we provide a systematic way to define decompositions from existing decomposable global constraints. These two approaches to enforcing consistency in global cost functions are then embedded in a solver for extensive experiments that confirm the feasibility and efficiency of our proposal.
This work has been partly funded by the “Agence Nationale de la Recherche” (ANR-10-BLA-0214), a “Partenariat Hubert Curien PROCORE” grant number 28680VH, the Research Grants Council of Hong Kong SAR grant CUHK413710, and the “Consulat Général de France de Hong Kong” with Research Grants Council of Hong Kong SAR joint grant F-HK019/12T.
Databáze: OpenAIRE
Externí odkaz: