Tractability-preserving transformations of global cost functions

DOI10.1016/J.ARTINT.2016.06.005zbMath1385.68040arXiv1502.02414OpenAlexW2267187671MaRDI QIDQ309935

Simon de Givry, Patricia Gutierrez, Jean-Philippe Métivier, Christian Bessiere, Samir Loudni, Patrice Boizumault, David Allouche, Ka Lun Leung, Thomas Schiex, Yi Wu, Jimmy Ho-man Lee

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 complexitydecompositionconstraint satisfaction problemconstraint programminggraphical modelcost function networkglobal cost functionsweighted constraint satisfaction problem

Mathematics Subject Classification ID

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

Related Items (3)

Multi-language evaluation of exact solvers in graphical model discrete optimization ⋮ Multiple-choice knapsack constraint in graphical models ⋮ Triangle-based consistencies for cost function networks

Uses Software

• ToulBar2
• SLIDE

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The weighted grammar constraint
• Arc consistency for soft constraints
• Solving weighted CSP by maintaining arc consistency
• High-order consistency in valued constraint satisfaction
• Reformulation of global constraints based on constraints checkers
• Mendelian error detection in complex pedigrees using weighted constraint satisfaction tech\-niques
• Soft arc consistency revisited
• Reasoning from last conflict(s) in constraint programming
• Optimization, approximation, and complexity classes
• A language and a program for stating and solving combinatorial problems
• Radio link frequency assignment
• Introducing global constraints in CHIP
• 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
• Parametrized complexity theory.
• On global warming: Flow-based soft global constraints
• Nonserial dynamic programming
• Consistency Techniques for Flow-Based Projection-Safe Global Cost Functions in Weighted Constraint Satisfaction
• On the Desirability of Acyclic Database Schemes
• Mini-buckets
• Bounds Arc Consistency for Weighted CSPs
• 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
• Principles and Practice of Constraint Programming – CP 2004

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