The partial constraint satisfaction problem: Facets and lifting theorems

DOI10.1016/S0167-6377(98)00043-1zbMATH Open0957.90095OpenAlexW2144306116MaRDI QIDQ1306379FDOQ1306379

Authors Arie M. C. A. Koster, Stan Van Hoesel, Antoon W. J. Kolen 

Publication date 1998

Published in Operations Research Letters (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/s0167-6377(98)00043-1

zbMATH Keywords

integer programmingconstraint satisfactionfacetslifting

Mathematics Subject Classification ID

Integer programming (90C10)

Recommendations

• Publication:3489491
• Solving partial constraint satisfaction problems with tree decomposition
• Lifting theorems and facet characterization for a class of clique partitioning inequalities
• The Polytope of Tree-Structured Binary Constraint Satisfaction Problems
• The generalized assignment problem: Valid inequalities and facets

Cites work

• scientific article; zbMATH DE number 193411 (Why is no real title available?)
• Some simplified NP-complete graph problems
• The Boolean quadratic polytope: Some characteristics, facets and relatives
• Transitive packing

Cited in

(19)

• A new approach to partial constraint satisfaction problems
• The power of linear programming for general-valued CSPs
• Lifting Bell inequalities
• Erratum to ``Comparison of column generation models for channel assignment in cellular networks
• Solving frequency assignment problems via tree-decomposition
• Combining VNS with constraint programming for solving anytime optimization problems
• Models and solution techniques for frequency assignment problems
• A study of the quadratic semi-assignment polytope
• A genetic algorithm for the partial binary constraint satisfaction problem: an application to a frequency assignment problem
• Train and test tightness of LP relaxations in structured prediction
• Soft arc consistency revisited
• Generalized network design problems.
• An improved algorithm to determine lower bounds for the fixed spectrum frequency assignment problem
• The Polytope of Tree-Structured Binary Constraint Satisfaction Problems
• A variable neighborhood search algorithm to generate piano fingerings for polyphonic sheet music
• Comparison of column generation models for channel assignment in cellular networks
• ANALYSIS OF L-STRUCTURE OF POLYHEDRON IN THE PARTIAL MAX SAT PROBLEM
• Minimization of locally defined submodular functions by optimal soft arc consistency
• Generalized network design polyhedra

This page was built for publication: The partial constraint satisfaction problem: Facets and lifting theorems

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