Local search heuristics for Quadratic Unconstrained Binary Optimization (QUBO)

被引：89

作者：

Boros, Endre ^{[1
]}

Hammer, Peter L. ^{[1
]}

Tavares, Gabriel ^{[1
]}

机构：

[1] Rutgers State Univ, RUTCOR, Piscataway, NJ 08854 USA

来源：

JOURNAL OF HEURISTICS | 2007年 / 13卷 / 02期

基金：

美国国家科学基金会;

关键词：

integer programming; local optimization; Quadratic Unconstrained Binary Optimization; quadratic pseudo-Boolean functions; heuristics;

D O I：

10.1007/s10732-007-9009-3

中图分类号：

TP18 [人工智能理论];

学科分类号：

081104 ; 0812 ; 0835 ; 1405 ;

摘要：

We present a family of local-search-based heuristics for Quadratic Unconstrained Binary Optimization (QUBO), all of which start with a (possibly fractional) initial point, sequentially improving its quality by rounding or switching the value of one variable, until arriving to a local optimum. The effects of various parameters on the efficiency of these methods are analyzed through computational experiments carried out on thousands of randomly generated problems having 20 to 2500 variables. Tested on numerous benchmark problems, the performance of the most competitive variant (ACSIOM) was shown to compare favorably with that of other published procedures.

引用

页码：99 / 132

页数：34

共 72 条

[1] 0-1 QUADRATIC-PROGRAMMING APPROACH FOR OPTIMUM SOLUTIONS OF 2 SCHEDULING PROBLEMS [J].