A lower bound for a constrained quadratic \(0\)-\(1\) minimization problem

DOI10.1016/S0166-218X(96)00026-1zbMath0879.90147OpenAlexW1975650096MaRDI QIDQ1356513

Alain Faye, Alain Billionnet

Publication date: 8 July 1997

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: http://www.elsevier.com/locate/dam

zbMATH Keywords

lower boundroof dualityquadratic pseudo-Boolean functionconstrained zero-one quadratic programminggreatest constant

Mathematics Subject Classification ID

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

Cites Work

• Unnamed Item
• Unnamed Item
• Upper-bounds for quadratic 0-1 maximization
• Maximizing a supermodular pseudoboolean function: A polynomial algorithm for supermodular cubic functions
• Unimodular functions
• Recognition problems for special classes of polynomials in 0-1 variables
• The Boolean quadratic polytope: Some characteristics, facets and relatives
• On the equivalence of paved-duality and standard linearization in nonlinear 0-1 optimization
• The basic algorithm for pseudo-Boolean programming revisited
• Unconstrained 0-1 optimization and Lagrangean relaxation
• Recognition of a class of unimodular functions
• Roof duality, complementation and persistency in quadratic 0–1 optimization
• Roof duality for polynomial 0–1 optimization
• Chvátal Cuts and Odd Cycle Inequalities in Quadratic 0–1 Optimization
• Minimum cuts and related problems

Related Items (4)

Un Algorithme pour la Bipartition d'un Graphe en Sous-graphes de Cardinalité Fixée ⋮ A polyhedral approach for a constrained quadratic 0-1 problem ⋮ Best reduction of the quadratic semi-assignment problem ⋮ Upper bounds and exact algorithms for \(p\)-dispersion problems

This page was built for publication: A lower bound for a constrained quadratic \(0\)-\(1\) minimization problem