A global continuation algorithm for solving binary quadratic programming problems

A global continuation algorithm for solving binary quadratic programming problems

0.00 Avg rating0 Votes
Article ID: iaor200911689
Country: United States
Volume: 41
Issue: 3
Start Page Number: 349
End Page Number: 362
Publication Date: Dec 2008
Journal: Computational Optimization and Applications
Authors: , ,
Abstract:

In this paper, we propose a new continuous approach for the unconstrained binary quadratic programming (BQP) problems based on the Fischer–Burmeister NCP function. Unlike existing relaxation methods, the approach reformulates a BQP problem as an equivalent continuous optimization problem, and then seeks its global minimizer via a global continuation algorithm which is developed by a sequence of unconstrained minimization for a global smoothing function. This smoothing function is shown to be strictly convex in the whole domain or in a subset of its domain if the involved barrier or penalty parameter is set to be sufficiently large, and consequently a global optimal solution can be expected. Numerical results are reported.

Reviews

Required fields are marked *. Your email address will not be published.