Best network flow bounds for the quadratic knapsack problem. (English) Zbl 0678.90061

Chaillou, Paul; Hansen, Pierre; Mahieu, Yvon

Combinatorial optimization, Proc. 3rd Sess., Como/Italy 1986, Lect. Notes Math. 1403, 225-235 (1989).

Summary: [For the entire collection see Zbl 0676.00023.]
A Lagrangean relaxation of the quadratic knapsack problem is studied. It is shown, among other properties, that the best value of the Lagrangean multiplier, and hence the best bound for the original problem, can be determined in at most n-1 applications of a maximum flow algorithm to a network with \(n+2\) vertices and \(n+m\) arcs, where n and m denote the numbers of variables and of quadratic terms. A branch-and-bound algorithm using this result is presented and computational experience is reported on.

MSC:

90C09	Boolean programming
90B10	Deterministic network models in operations research
65K05	Numerical mathematical programming methods
90C35	Programming involving graphs or networks
90C20	Quadratic programming
68Q25	Analysis of algorithms and problem complexity

Keywords:

Lagrangean relaxation; quadratic knapsack problem; Lagrangean multiplier; best bound; maximum flow; branch-and-bound; computational experience

Citations:

Zbl 0676.00023