Markov Chain methods for the Bipartite Boolean Quadratic Programming Problem
Markov Chain methods for the Bipartite Boolean Quadratic Programming Problem
复制标题
DOI：
10.1016/j.ejor.2017.01.001
复制
发表时间：
2016-05
期刊：
影响因子：
--
通讯作者：
Daniel Karapetyan;Abraham P. Punnen;A. Parkes
中科院分区：
文献类型：
--
作者：
Daniel Karapetyan;Abraham P. Punnen;A. Parkes
研究了二部布尔二次规划问题（BBQP），它是布尔二次规划问题（BQP）的扩展。BBQP的应用包括从二进制数据中挖掘离散模式，用秩一二进制矩阵逼近矩阵，计算矩阵的切范数，解决优化问题，如最大权值双方，二部最大权值切割，二部图的最大权值诱导子图等。对于BBQP，我们首先提出了几个算法组件，特别是爬山者和突变，然后展示了如何将它们组合在一个高性能的元启发式中。我们没有手动调整标准的元启发式来测试组件混合的效率，而是选择使用自动生成的多组件元启发式来节省人力时间，并提高分析和比较组件的客观性。为此，我们设计了一种新的元启发式模式，我们称之为条件马尔可夫链搜索（CMCS）。我们表明，CMCS足够灵活，可以模拟几种标准的元启发式；这种灵活性由多个数值参数控制，因此便于自动化生成。我们研究了我们的方法所揭示的配置，并表明其中最好的配置比以前最先进的BBQP算法要好几个数量级。在我们的实验中，我们使用了本文初稿中介绍的基准测试实例，这些实例在BBQP文献中已经成为事实上的标准。
We study the Bipartite Boolean Quadratic Programming Problem (BBQP) which is an extension of the well known Boolean Quadratic Programming Problem (BQP). Applications of the BBQP include mining discrete patterns from binary data, approximating matrices by rank-one binary matrices, computing the cut-norm of a matrix, and solving optimisation problems such as maximum weight biclique, bipartite maximum weight cut, maximum weight induced sub-graph of a bipartite graph, etc. For the BBQP, we first present several algorithmic components, specifically, hill climbers and mutations, and then show how to combine them in a high-performance metaheuristic. Instead of hand-tuning a standard metaheuristic to test the efficiency of the hybrid of the components, we chose to use an automated generation of a multi-component metaheuristic to save human time, and also improve objectivity in the analysis and comparisons of components. For this we designed a new metaheuristic schema which we call Conditional Markov Chain Search (CMCS). We show that CMCS is flexible enough to model several standard metaheuristics; this flexibility is controlled by multiple numeric parameters, and so is convenient for automated generation. We study the configurations revealed by our approach and show that the best of them outperforms the previous state-of-the-art BBQP algorithm by several orders of magnitude. In our experiments we use benchmark instances introduced in the preliminary version of this paper and described here, which have already become the de facto standard in the BBQP literature.