Bipartite unconstrained 0-1 quadratic programming problem

Abraham Duarte, Manuel Laguna, Rafael Martí, Jesús Sánchez-Oro

Optimization procedures for the bipartite unconstrained 0-1 quadratic programming problem,Computers & Operations Research,Volume 51,2014,Pages 123-129,ISSN 0305-0548,https://doi.org/10.1016/j.cor.2014.05.019.

Abstract: The bipartite unconstrained 0-1 quadratic programming problem (BQP) is a difficult combinatorial problem defined on a complete graph that consists of selecting a subgraph that maximizes the sum of the weights associated with the chosen vertices and the edges that connect them. The problem has appeared under several different names in the literature, including maximum weight induced subgraph, maximum weight biclique, matrix factorization and maximum cut on bipartite graphs. There are only two unpublished works (technical reports) where heuristic approaches are tested on BQP instances. Our goal is to combine straightforward search elements to balance diversification and intensification in both exact (branch and bound) and heuristic (iterated local search) frameworks. We perform a number of experiments to test individual search components and also to create new benchmarks when comparing against the state of the art, which the proposed procedure outperforms.Keywords: Quadratic programming; Branch and bound; Heuristic search; Tabu search; Iterated local search

亚伯拉罕·杜阿尔特（Abraham Duarte）、曼努埃尔·拉古纳（Manuel Laguna）、拉斐尔·马蒂（Rafael Martí）、赫苏斯·桑切斯-奥罗（Jesús Sánchez-Oro）
《二分无约束0-1二次规划问题的优化方法》，发表于《Computers & Operations Research》（计算机与运筹学），2014年，第51卷，第123-129页，ISSN 0305-0548，DOI：10.1016/j.cor.2014.05.019。
摘要：二分无约束0-1二次规划问题（BQP）是一类定义于完全图上的复杂组合优化问题，其目标为选取一子图，使得所选顶点及其连接边的权重之和最大化。该问题在文献中曾以多个不同名称出现，包括最大权诱导子图、最大权二部团、矩阵分解以及二部图上的最大割问题。目前仅有两篇未发表的技术报告类文献针对BQP实例测试了启发式求解方法。本文旨在结合基础搜索策略元素，在精确求解（Branch and Bound，分支定界）与启发式求解（Iterated Local Search，迭代局部搜索）两种框架中平衡搜索的多样性与强化性。本文开展了多组实验，以测试各独立搜索模块的性能，并在与当前最优算法的对比中构建了全新的基准测试集，所提优化方法在该基准集上表现优于现有算法。
关键词：二次规划；分支定界（Branch and Bound）；启发式搜索；禁忌搜索（Tabu Search）；迭代局部搜索（Iterated Local Search）