The partial constraint satisfaction problem: Facets and lifting theorems

被引：50

作者：

Koster, AMCA ^{[1
]}

van Hoesel, SPM ^{[1
]}

Kolen, AWJ ^{[1
]}

机构：

[1] Maastricht Univ, Dept Quantitat Ecol, NL-6200 MD Maastricht, Netherlands

来源：

OPERATIONS RESEARCH LETTERS | 1998年 / 23卷 / 3-5期

关键词：

integer programming; constraint satisfaction; facets; lifting;

D O I：

10.1016/S0167-6377(98)00043-1

中图分类号：

C93 [管理学]; O22 [运筹学];

学科分类号：

070105 ; 12 ; 1201 ; 1202 ; 120202 ;

摘要：

We study the polyhedral structure of the partial constraint satisfaction problem (PCSP). Among the problems that can be formulated as such are the maximum satisfiability problem and a fairly general model of frequency assignment problems. We present lifting theorems and classes of facet defining inequalities, and we provide preliminary experiments. (C) 1998 Elsevier Science B.V. All rights reserved.

引用

页码：89 / 97

页数：9

共 6 条

[1]

Aardal K., 1996, 96011 MAASTR U

[2]

Garey M. R., 1976, Theoretical Computer Science, V1, P237, DOI 10.1016/0304-3975(76)90059-1

[3]

KOLEN AWJ, 1997, GENETIC ALGORITHM PA

[4]

Muller R., 1996, Integer Programming and Combinatorial Optimization. 5th International IPCO Conference Proceedings, P430

[5]

Nemhauser GL, 1988, INTEGER COMBINATORIA

[6] THE BOOLEAN QUADRIC POLYTOPE - SOME CHARACTERISTICS, FACETS AND RELATIVES [J].

PADBERG, M .

MATHEMATICAL PROGRAMMING, 1989, 45 (01) :139-172

← 1 →