Upper-bounds for quadratic 0-1 maximization

DOI10.1016/0167-6377(90)90044-6zbMath0699.90073WikidataQ59561080 ScholiaQ59561080MaRDI QIDQ913658

Peter L. Hammer, Endre Boros, Yves Cramer

Publication date: 1990

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

Full work available at URL: https://doi.org/10.1016/0167-6377(90)90044-6

zbMATH Keywords

upper bounds; linearization; complementation; majorization; quadratic pseudo-Boolean function

Mathematics Subject Classification ID

90C20: Quadratic programming

90C09: Boolean programming

Related Items

Efficient branch-and-bound algorithms for weighted MAX-2-SAT, Pseudo-Boolean optimization, Block linear majorants in quadratic 0--1 optimization, A hierarchy of relaxations leading to the convex hull representation for general discrete optimization problems, A Max-flow approach to improved lower bounds for quadratic unconstrained binary optimization (QUBO), A pseudo-Boolean consensus approach to nonlinear 0-1 optimization, Analyzing quadratic unconstrained binary optimization problems via multicommodity flows, A linearization framework for unconstrained quadratic (0-1) problems, The max-cut problem and quadratic 0-1 optimization; polyhedral aspects, relaxations and bounds, Simulated annealing for the unconstrained quadratic pseudo-Boolean function, A hierarchy of relaxations and convex hull characterizations for mixed- integer zero-one programming problems, A lower bound for a constrained quadratic \(0\)-\(1\) minimization problem, A simultaneous lifting strategy for identifying new classes of facets for the Boolean quadric polytope

Cites Work

• Unnamed Item
• The Boolean quadratic polytope: Some characteristics, facets and relatives
• On the equivalence of paved-duality and standard linearization in nonlinear 0-1 optimization
• On the equivalence between roof duality and Lagrangian duality for unconstrained \(0\)-\(1\) quadratic programming problems
• Nonlinear 0–1 programming: I. Linearization techniques
• Nonlinear 0–1 programming: II. Dominance relations and algorithms
• Roof duality, complementation and persistency in quadratic 0–1 optimization
• Methods of Nonlinear 0-1 Programming
• Chvátal Cuts and Odd Cycle Inequalities in Quadratic 0–1 Optimization