Optimization Online


A new branch-and-bound algorithm for standard quadratic programming problems

Giampaolo Liuzzi (giampaolo.liuzzi***at***iasi.cnr.it)
Marco Locatelli (marco.locatelli***at***unipr.it)
Veronica Piccialli (veronica.piccialli***at***uniroma2.it)

Abstract: In this paper we propose convex and LP bounds for Standard Quadratic Programming (StQP) problems and employ them within a branch-and-bound approach. We first compare different bounding strategies for StQPs in terms both of the quality of the bound and of the computation times. It turns out that the polyhedral bounding strategy is the best one to be used within a branch-and-bound scheme. Indeed, it guarantees a good quality of the bound at the expense of a very limited computation time. The proposed branch-and-bound algorithm performs an implicit enumeration of all the KKT (stationary) points of the problem. We compare different branching strategies exploiting the structure of the problem. Numerical results on randomly generated problems (with varying density of the underlying convexity graph) are reported which show the effectiveness of the proposed approach, in particular in limiting the growth of the number of nodes in the branch-and-bound tree as the density of the underlying graph increases.

Keywords: Standard Quadratic Programming; branch-and-bound; polyhedral bound

Category 1: Nonlinear Optimization (Quadratic Programming )

Category 2: Global Optimization


Download: [PDF]

Entry Submitted: 08/04/2016
Entry Accepted: 08/04/2016
Entry Last Modified: 08/04/2016

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society