×

Upper-bounds for quadratic 0-1 maximization. (English) Zbl 0699.90073

Three different approaches (complementation, majorization, and linearization) introduced by the third author, P. Hansen and B. Simeone [Math. Program. 28, 121-155 (1984; Zbl 0574.90066)] are generalized to obtain upper bounds for the maximum of a quadratic pseudo- Boolean function over \(\{0,1\}^ n\).
Reviewer: T.Sawik

MSC:

90C09 Boolean programming
90C20 Quadratic programming

Citations:

Zbl 0574.90066
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Adams, W. P.; Dearing, P. M., On the equivalence between roof-duality and Lagrangian duality for unconstrained 0-1 quadratic programming problems, (Technical Report No. URI-061 (1988), The Clemson University) · Zbl 0794.90038
[2] Balas, E.; Mazzola, J. B., Nonlinear 0-1 programming: I, Linearization techniques, Math. Programming, 30, 1-21 (1984) · Zbl 0553.90067
[3] Balas, E.; Mazzola, J. B., Nonlinear 0-1 programming: II, Dominance relations and algorithms, Math. Programming, 30, 22-45 (1984) · Zbl 0553.90068
[4] Boros, E.; Crama, Y.; Hammer, P. L., Chvátal cuts and odd cycle inequalities in quadratic 0-1 optimization (1989), manuscript · Zbl 0761.90069
[5] Bourjolly, J.-M.; Hammer, P. L.; Pulleyblank, W. R.; Simeone, B., Combinatorial methods for bounding a quadratic pseudo-Boolean function (1988), manuscript
[6] Crama, Y., Linearization techniques and concave extensions in non-linear 0-1 optimization, (RUTCOR Research Report 32-88 (1988), Rutgers University: Rutgers University New Brunswick, NJ)
[7] de Simone, C., The cut polytope and the Boolean quadratic polytype, (RUTCOR Research REport 53-88 (1988), Rutgers University: Rutgers University New Brunswick, NJ)
[8] Garey, M. R.; Johnson, D. S., Computers and Intractability, A Guide to the Theory of NP-completeness (1979), W.H. Freeman Co: W.H. Freeman Co New York · Zbl 0411.68039
[9] Hammer, P. L.; Hansen, P.; Simeone, B., Roof duality, complementation and persistency in quadratic 0-1 optimization, Math. Programming, 28, 121-155 (1984) · Zbl 0574.90066
[10] Hansen, P., Methods of nonlinear 0-1 programming, Ann. Discrete Math., 5, 53-70 (1979) · Zbl 0426.90063
[11] Hansen, P.; Lu, S. H., On the equivalence of paved-duality and standard linearization, (RUTCOR Research Report 30-87 (1987), Rutgers University: Rutgers University New Brunswick, NJ) · Zbl 0744.90060
[12] Lu, S. H.; Simeone, B., On the equivalence of roof-duality and paved-duality in quadratic 0-1 optimization, (RUTCOR Research Report 22-87 (1987), Rutgers University: Rutgers University New Brunswick, NJ) · Zbl 0744.90060
[13] Padberg, M., The Boolean quadric polytope: Some characteristics, facets and relative, Math. Programming, 45, 139-172 (1989) · Zbl 0675.90056
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.