Tractability-preserving transformations of global cost functions

DOI10.1016/J.ARTINT.2016.06.005zbMATH Open1385.68040OpenAlexW2267187671MaRDI 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)

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

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)

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.

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

Cites work

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

Cited in

(5)

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

Describes a project that uses

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)