Mathematical Programming Computation, Volume 6, Number 2, June 2014

Font Size:  Small  Medium  Large

A Newton’s method for the continuous quadratic knapsack problem

Roberto Cominetti, Walter F. Mascarenhas, Paulo J. S. Silva

Abstract


We introduce a new efficient method to solve the continuous quadratic knapsack problem. This is a highly structured quadratic program that appears in dif- ferent contexts. The method converges after O(n) iterations with overall arithmetic complexity O(n2). Numerical experiments show that in practice the method con- verges in a small number of iterations with overall linear complexity, and is faster than the state-of-the-art algorithms based on median finding, variable fixing, and secant techniques.


Full Text: pdf

mpc footer
© MPS 2008-2016