Advanced Tabu Search Algorithms for Bipartite Boolean Quadratic Programs Guided by Strategic Oscillation and Path Relinking

Qinghua Wu (), Yang Wang () and Fred Glover ()
Additional contact information
Qinghua Wu: School of Management, Huazhong University of Science and Technology, 430074 Wuhan, China;
Yang Wang: School of Management, Northwestern Polytechnical University, 710072 Xi’an, China;
Fred Glover: Electrical, Computer, and Energy Engineering, School of Engineering and Science, University of Colorado Boulder, Boulder, Colorado 80309

INFORMS Journal on Computing, 2020, vol. 32, issue 1, 74-89

Abstract: The bipartite Boolean quadratic programming problem (BBQP) is a generalization of the well-studied NP-hard Boolean quadratic programming problem and can be regarded as a unified model for many graph theoretic optimization problems, including maximum weight-induced subgraph problems, maximum weight biclique problems, matrix factorization problems, and maximum cut problems on bipartite graphs. This paper introduces three main algorithms for solving the BBQP, based on three variants of tabu search, the first two consisting of strategic oscillation–tabu search (SO-TS) algorithms, which use destructive and constructive procedures to guide the search into unexplored and promising areas. The third algorithm, whichDoes also incorporates the SO-TS algorithms as solution improvement methods, uses a path relinking (PR) algorithm that is capable of further enhancing search performance. Experimental results demonstrate that all three algorithms perform very effectively compared with the best methods in the literature, and the PR algorithm joined with tabu search is able to discover new best solutions for two-thirds of the large problem instances and match the previous best known solutions for the other instances. Additional analysis discloses the contributions of the key ingredients of each of the proposed algorithms.

Keywords: bipartite Boolean quadratic programs; tabu search; strategic oscillation; path relinking (search for similar items in EconPapers)
Date: 2020
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (2)

Downloads: (external link)
https://doi.org/10.1287/ijoc.2018.0871 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:orijoc:v:32:y:2020:i:1:p:74-89

Access Statistics for this article

More articles in INFORMS Journal on Computing from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().