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

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

zbMATH Keywords

integer programmingconstraint satisfactionfacetslifting

Mathematics Subject Classification ID

Integer programming (90C10)

Cites Work

• Title not available (Why is that?)
• 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)