A tight bound for the Boolean quadratic optimization problem and its use in a branch and bound algorithm. (English) Zbl 0658.90066

Known duality statements are used to find tight bounds for the branch and bound process in solving Boolean quadratic optimization problems. To solve the corresponding continuous and partial problem, a Newton-like procedure is indicated. Superlinear convergence, however, is only obtained in partial cases.


90C09 Boolean programming
90C20 Quadratic programming
65K05 Numerical mathematical programming methods
49N15 Duality theory (optimization)
Full Text: DOI


[1] DOI: 10.1088/0305-4470/15/2/033 · doi:10.1088/0305-4470/15/2/033
[2] Bazaraa M.S., Nonlinear programming-Theory and algorithms (1979) · Zbl 0476.90035
[3] Bernau, H. Upper bound techniques for quadratic programming. Proc. 9th Int. Math. Prog. Symp. pp.347–356. Budapest · Zbl 0428.90055
[4] Bubkard R.E., Math. Progr pp 53– (1984)
[5] DOI: 10.1016/0166-218X(84)90111-2 · Zbl 0524.90061 · doi:10.1016/0166-218X(84)90111-2
[6] Hammer P.L., Boolean methods in operations research (1968) · Zbl 0155.28001
[7] DOI: 10.1016/S0167-5060(08)70343-1 · Zbl 0426.90063 · doi:10.1016/S0167-5060(08)70343-1
[8] DOI: 10.1007/BF01459079 · Zbl 0493.90059 · doi:10.1007/BF01459079
[9] DOI: 10.1016/0377-2217(85)90181-X · Zbl 0553.90070 · doi:10.1016/0377-2217(85)90181-X
[10] DOI: 10.1007/BF01581047 · Zbl 0475.90065 · doi:10.1007/BF01581047
[11] DOI: 10.1287/mnsc.26.3.282 · Zbl 0443.90067 · doi:10.1287/mnsc.26.3.282
[12] DOI: 10.1002/zamm.19740540508 · Zbl 0281.90058 · doi:10.1002/zamm.19740540508
[13] Schwetlick H., Numerische Losung nichtlinearer Gleichungen (1979)
[14] Stoer J., Convexity and optimization in finite dimensions I (1970) · Zbl 0203.52203
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.