CHVATAL CUTS AND ODD CYCLE INEQUALITIES IN QUADRATIC 0 - 1 OPTIMIZATION

作     者：BOROS, E CRAMA, Y HAMMER, PL 

作者机构：RUTGERS STATE UNIVRUTCORNEW BRUNSWICKNJ 08903 UNIV LIMBURGDEPT QUANTITAT ECON6200 MD MAASTRICHTNETHERLANDS 

出 版 物：《SIAM JOURNAL ON DISCRETE MATHEMATICS》 (工业与应用数学会离散数学杂志)

年 卷 期：1992年第5卷第2期

页      面：163-177页

核心收录：

学科分类：07[理学] 0701[理学-数学] 070101[理学-基础数学] 

主　　题：UNCONSTRAINED QUADRATIC 0 - 1 PROGRAMMING PSEUDO-BOOLEAN FUNCTIONS WEIGHTED 2-SATISFIABILITY MAXIMUM CUT PROBLEM CHVATAL CUT CHVATAL CLOSURE 

摘      要：In this paper a new lower bound for unconstrained quadratic 0-1 minimization is investigated. It is shown that this bound can be computed by solving a linear programming problem of polynomial size in the number of variables;and it is shown that the polyhedron S[3], defined by the constraints of this LP formulation is precisely the first Chvatal closure of the polyhedron associated with standard linearization procedures. By rewriting the quadratic minimization problem as a balancing problem in a weighted signed graph, it can be seen that the polyhedron defined by the odd cycle inequalities is equivalent, in a certain sense, with S[3]. As a corollary, a compact linear programming formulation is presented for the maximum cut problem for the case of weakly bipartite graphs.