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

Körner, F.

Optimization 19, No. 5, 711-721 (1988).

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.

MSC:

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

Keywords:

duality; tight bounds; branch and bound; Boolean quadratic optimization; Superlinear convergence

References:

[1]	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
[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
[8]	DOI: 10.1007/BF01459079 · Zbl 0493.90059
[9]	DOI: 10.1016/0377-2217(85)90181-X · Zbl 0553.90070
[10]	DOI: 10.1007/BF01581047 · Zbl 0475.90065
[11]	DOI: 10.1287/mnsc.26.3.282 · Zbl 0443.90067
[12]	DOI: 10.1002/zamm.19740540508 · Zbl 0281.90058
[13]	Schwetlick H., Numerische Losung nichtlinearer Gleichungen (1979)
[14]	Stoer J., Convexity and optimization in finite dimensions I (1970) · Zbl 0203.52203