Tractability-preserving transformations of global cost functions

DOI10.1016/J.ARTINT.2016.06.005zbMATH Open1385.68040arXiv1502.02414OpenAlexW2267187671MaRDI QIDQ309935FDOQ309935

Authors: David Allouche, Christian Bessiere, Patrice Boizumault, Simon de Givry, Patricia Gutierrez, K. L. Leung, Samir Loudni, Jean-Philippe Métivier, Thomas Schiex, J. H. M. Lee, Yi Wu 

Publication date: 7 September 2016

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

Abstract: Enforcing local consistencies in cost function networks is performed by applying so-called Equivalent Preserving Transformations (EPTs) to the cost functions. As EPTs transform the cost functions, they may break the property that was making local consistency enforcement tractable on a global cost function. A global cost function is called tractable projection-safe when applying an EPT to it is tractable and does not break the tractability property. In this paper, we prove that depending on the size r of the smallest scopes used for performing EPTs, the tractability of global cost functions can be preserved (r = 0) or destroyed (r > 1). When r = 1, the answer is indefinite. We show that on a large family of cost functions, EPTs can be computed via dynamic programming-based algorithms, leading to tractable projection-safety. We also show that when a global cost function can be decomposed into a Berge acyclic network of bounded arity cost functions, soft local consistencies such as soft Directed or Virtual Arc Consistency can directly emulate dynamic programming. These different approaches to decomposable cost functions are then embedded in a solver for extensive experiments that confirm the feasibility and efficiency of our proposal.

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

Recommendations

• Triangle-based consistencies for cost function networks
• Consistency techniques for flow-based projection-safe global cost functions in weighted constraint satisfaction
• Principles and Practice of Constraint Programming – CP 2004
• Consistency techniques for polytime linear global cost functions in weighted constraint satisfaction
• Soft arc consistency revisited

zbMATH Keywords

computational complexitydecompositiongraphical modelconstraint programmingconstraint satisfaction problemcost function networkglobal cost functionsweighted constraint satisfaction problem

Mathematics Subject Classification ID

Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Analysis of algorithms and problem complexity (68Q25) Combinatorial optimization (90C27) Dynamic programming (90C39)

Cites Work

• Soft arc consistency revisited
• Optimization, approximation, and complexity classes
• Handbook of constraint programming.
• Introducing global constraints in CHIP
• Parametrized complexity theory.
• Principles and Practice of Constraint Programming – CP 2004
• Reformulation of global constraints based on constraints checkers
• Reasoning from last conflict(s) in constraint programming
• Nonserial dynamic programming
• On the Desirability of Acyclic Database Schemes
• Title not available (Why is that?)
• A language and a program for stating and solving combinatorial problems
• Radio link frequency assignment
• A dynamic programming approach for consistency and propagation for knapsack constraints
• Reduction operations in fuzzy or valued constraint satisfaction
• Grammar constraints
• Consistency techniques for polytime linear global cost functions in weighted constraint satisfaction
• Multi-language evaluation of exact solvers in graphical model discrete optimization
• Computational protein design as an optimization problem
• On global warming: Flow-based soft global constraints
• Consistency techniques for flow-based projection-safe global cost functions in weighted constraint satisfaction
• Mini-buckets
• Bounds arc consistency for weighted CSPs
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• The weighted grammar constraint
• The Decision Problem for a Class of First‐Order Formulas in Which all Disjunctions are Binary
• Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems
• Principles and Practice of Constraint Programming – CP 2003
• Arc consistency for soft constraints
• Solving weighted CSP by maintaining arc consistency
• High-order consistency in valued constraint satisfaction
• Mendelian error detection in complex pedigrees using weighted constraint satisfaction tech\-niques

Cited In (5)

• Valued constraint satisfaction problems
• Multiple-choice knapsack constraint in graphical models
• A globally concave, symmetric, flexible cost function
• Multi-language evaluation of exact solvers in graphical model discrete optimization
• Triangle-based consistencies for cost function networks

Uses Software

• ToulBar2
• SLIDE

This page was built for publication: Tractability-preserving transformations of global cost functions

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