The Nemhauser-Trotter reduction and lifted message passing for the weighted CSP

DOI10.1007/978-3-319-59776-8_31MaRDI QIDQ2011611zbMATH OpenOpenAlexFDO

Authors Hong Xu, T. K. Satish Kumar, Sven Koenig

Publication date 4 August 2017

Full work available at URL https://doi.org/10.1007/978-3-319-59776-8_31

Mathematics Subject Classification ID

Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Approximation methods and heuristics in mathematical programming (90C59)

Recommendations

• Solving weighted CSP by maintaining arc consistency
• Solving Max-SAT as weighted CSP
• Local Consistency in Weighted CSPs and Inference in Max-SAT
• Solving weighted constraint satisfaction problems with memetic/exact hybrid algorithms
• A new solver for the minimum weighted vertex cover problem

Cites work

• A new approach to the maximum-flow problem
• A new solver for the minimum weighted vertex cover problem
• Convergence of Min-Sum Message-Passing for Convex Optimization
• DARN! A weighted constraint solver for RNA motif localization
• scientific article; zbMATH DE number 2243357 (Why is no real title available?)
• Information, Physics, and Computation
• Multi-language evaluation of exact solvers in graphical model discrete optimization
• Probabilistic graphical models.
• Semiring-based CSPs and valued CSPs: Frameworks, properties, and comparison
• Vertex packings: Structural properties and algorithms

Describes a project that uses

Uses Software

• CP-nets
• Boost
• Gurobi
• DARN!
• BGL

This page was built for publication: The Nemhauser-Trotter reduction and lifted message passing for the weighted CSP

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