NAPHEAP
swMATH ID:  23701 
Software Authors:  Davis, Timothy A.; Hager, William W.; Hungerford, James T. 
Description:  An efficient hybrid algorithm for the separable convex quadratic knapsack problem. This article considers the problem of minimizing a convex, separable quadratic function subject to a knapsack constraint and a box constraint. An algorithm called NAPHEAP has been developed to solve this problem. The algorithm solves the KarushKuhnTucker system using a starting guess to the optimal Lagrange multiplier and updating the guess monotonically in the direction of the solution. The starting guess is computed using the variable fixing method or is supplied by the user. A key innovation in our algorithm is the implementation of a heap data structure for storing the break points of the dual function and computing the solution of the dual problem. Also, a new version of the variable fixing algorithm is developed that is convergent even when the objective Hessian is not strictly positive definite. The hybrid algorithm NAPHEAP that uses a Newtontype method (variable fixing method, secant method, or Newton’s method) to bracket a root, followed by a heapbased monotone break point search, can be faster than a Newtontype method by itself, as demonstrated in the numerical experiments. 
Homepage:  https://dl.acm.org/citation.cfm?doid=2935754.2828635 
Keywords:  continuous quadratic knapsack; convex programming; heap; nonlinear programming; quadratic programming; separable programming 
Related Software:  SPG; ALGENCAN; Knapsack; CSparse; symrcm; SparseMatrix; METIS; Mosek; Gurobi; PPROJ; Algorithm 656; Algorithm 679; NETLIB LP Test Set; UNLocBoX; PDCO; Ipopt; CHOLMOD; CPLEX; BLAS; GALAHAD 
Referenced in:  11 Publications 
Standard Articles
1 Publication describing the Software, including 1 Publication in zbMATH  Year 

An efficient hybrid algorithm for the separable convex quadratic knapsack problem. Zbl 1369.65072 Davis, Timothy A.; Hager, William W.; Hungerford, James T. 
2016

all
top 5
Referenced by 22 Authors
all
top 5
Referenced in 9 Serials
Referenced in 3 Fields
11  Operations research, mathematical programming (90XX) 
8  Numerical analysis (65XX) 
4  Game theory, economics, finance, and other social and behavioral sciences (91XX) 