A Smoothing Function for Solving Binary Quadratic Programming

摘要：

In this paper, a novel smoothing function method for solving Binary Quadratic Programming (BQP) problems is investigated. Unlike existing relaxation methods, the approach reformulates the BQP problems as an equivalent non-differentiable optimization model, and then each constrained condition is reduced to an equation by means of smooth technique. The smoothing function is shown to be strictly convex and differentiable in the whole domain. As such, the BQP can be solved by the mature optimization technique while this algorithm is fast and insensitive to initial point. Theory analysis and primary numerical results illustrate that smoothing function method for binary quadratic programming is feasible and effective.

关键词： Operations Research Binary quadratic programming Continuous approach Global continuous algorithm

作者: Ruopeng Wang

作者单位: Dept. of Math, and Physics, Beijing Institute of Petrochemical Technology. Beijing 102617, P.R. China

会议类型: 国际会议

会议名称: The First World Congress on Global Optimization in Engineering & Science(第一届工程与科学全局优化国际会议 WCGO2009)

会议地点: 长沙

会议语种:英文

页码: 489-495

在线出版日期: 2009-06-01（万方平台首次上网日期，不代表论文的发表时间）