Markov Chain methods for the Bipartite Boolean Quadratic Programming Problem
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-n...
| Main Authors: | , , |
|---|---|
| Format: | Article |
| Published: |
Elsevier
2017
|
| Subjects: | |
| Online Access: | https://eprints.nottingham.ac.uk/41040/ |
| _version_ | 1848796183009427456 |
|---|---|
| author | Karapetyan, Daniel Punnen, Abraham Parkes, Andrew J. |
| author_facet | Karapetyan, Daniel Punnen, Abraham Parkes, Andrew J. |
| author_sort | Karapetyan, Daniel |
| building | Nottingham Research Data Repository |
| collection | Online Access |
| description | 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 com- bine 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 compar- isons 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 genera- tion. 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. |
| first_indexed | 2025-11-14T19:43:55Z |
| format | Article |
| id | nottingham-41040 |
| institution | University of Nottingham Malaysia Campus |
| institution_category | Local University |
| last_indexed | 2025-11-14T19:43:55Z |
| publishDate | 2017 |
| publisher | Elsevier |
| recordtype | eprints |
| repository_type | Digital Repository |
| spelling | nottingham-410402020-05-04T18:52:47Z https://eprints.nottingham.ac.uk/41040/ Markov Chain methods for the Bipartite Boolean Quadratic Programming Problem Karapetyan, Daniel Punnen, Abraham Parkes, Andrew J. 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 com- bine 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 compar- isons 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 genera- tion. 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. Elsevier 2017-07-01 Article PeerReviewed Karapetyan, Daniel, Punnen, Abraham and Parkes, Andrew J. (2017) Markov Chain methods for the Bipartite Boolean Quadratic Programming Problem. European Journal of Operational Research, 260 (2). pp. 494-506. ISSN 0377-2217 Artificial intelligence ; Bipartite Boolean quadratic programming ; Automated heuristic configuration ; Benchmark http://www.sciencedirect.com/science/article/pii/S0377221717300061 doi:10.1016/j.ejor.2017.01.001 doi:10.1016/j.ejor.2017.01.001 |
| spellingShingle | Artificial intelligence ; Bipartite Boolean quadratic programming ; Automated heuristic configuration ; Benchmark Karapetyan, Daniel Punnen, Abraham Parkes, Andrew J. Markov Chain methods for the Bipartite Boolean Quadratic Programming Problem |
| title | Markov Chain methods for the Bipartite Boolean Quadratic Programming Problem |
| title_full | Markov Chain methods for the Bipartite Boolean Quadratic Programming Problem |
| title_fullStr | Markov Chain methods for the Bipartite Boolean Quadratic Programming Problem |
| title_full_unstemmed | Markov Chain methods for the Bipartite Boolean Quadratic Programming Problem |
| title_short | Markov Chain methods for the Bipartite Boolean Quadratic Programming Problem |
| title_sort | markov chain methods for the bipartite boolean quadratic programming problem |
| topic | Artificial intelligence ; Bipartite Boolean quadratic programming ; Automated heuristic configuration ; Benchmark |
| url | https://eprints.nottingham.ac.uk/41040/ https://eprints.nottingham.ac.uk/41040/ https://eprints.nottingham.ac.uk/41040/ |