Upper-bounds for quadratic 0-1 maximization

DOI10.1016/0167-6377(90)90044-6zbMath0699.90073OpenAlexW2065941671WikidataQ59561080 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 boundslinearizationcomplementationmajorizationquadratic pseudo-Boolean function

Mathematics Subject Classification ID

Quadratic programming (90C20) Boolean programming (90C09)

Related Items

A hierarchy of relaxations and convex hull characterizations for mixed- integer zero-one programming problems, Mathematical Programming Models and Exact Algorithms, A simultaneous lifting strategy for identifying new classes of facets for the Boolean quadric polytope, A lower bound for a constrained quadratic \(0\)-\(1\) minimization problem, A computational study of exact subgraph based SDP bounds for max-cut, stable set and coloring, A Hierarchy of Subgraph Projection-Based Semidefinite Relaxations for Some NP-Hard Graph Optimization Problems, The max-cut problem and quadratic 0-1 optimization; polyhedral aspects, relaxations and bounds, A Max-flow approach to improved lower bounds for quadratic unconstrained binary optimization (QUBO), A pseudo-Boolean consensus approach to nonlinear 0-1 optimization, Efficient branch-and-bound algorithms for weighted MAX-2-SAT, Analyzing quadratic unconstrained binary optimization problems via multicommodity flows, Pseudo-Boolean optimization, Block linear majorants in quadratic 0--1 optimization, Lagrangean decompositions for the unconstrained binary quadratic programming problem, A linearization framework for unconstrained quadratic (0-1) problems, Simulated annealing for the unconstrained quadratic pseudo-Boolean function, A hierarchy of relaxations leading to the convex hull representation for general discrete optimization problems

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