×

zbMATH — the first resource for mathematics

Advanced tabu search algorithms for bipartite Boolean quadratic programs guided by strategic oscillation and path relinking. (English) Zbl 07284454
Summary: 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.
The online supplement is available at https://doi.org/10.1287/ijoc.2018.0871.
MSC:
90C Mathematical programming
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Ahuja RK, Ergun O, Orlin JB, Punnen AP (2002) A survey of very large-scale neighborhood search techniques. Discrete Appl. Math. 123(1-3):75-102.Crossref, Google Scholar · Zbl 1014.68052
[2] Alon N, Naor A (2006) Approximating the cut-norm via Grothendieck’s inequality. SIAM J. Comput. 35(4):787-803.Crossref, Google Scholar · Zbl 1096.68163
[3] Ambühl C, Mastrolilli M, Svensson O (2011) Inapproximability results for maximum edge biclique, minimum linear arrangement, and sparsest cut. SIAM J. Comput. 40(2):567-596.Crossref, Google Scholar · Zbl 1223.68043
[4] Aringhieri R, Cordone R (2011) Comparing local search metaheuristics for the maximum diversity problem. J. Oper. Res. Soc. 62(2):266-280.Crossref, Google Scholar
[5] Benlic U, Hao J (2011) An effective multilevel tabu search approach for balanced graph partitioning. Comput. Oper. Res. 38(7):123-137.Crossref, Google Scholar · Zbl 1205.90286
[6] Carlton WB, Barnes JW (1996) A note on hashing functions and tabu search algorithms. Eur. J. Oper. Res. 95(1):237-239.Crossref, Google Scholar · Zbl 0953.90528
[7] Chang WC, Vakati S, Krause R, Eulenstein O (2012) Exploring biological interaction networks with tailored weighted quasi-bicliques. BMC Bioinformatics 13(Suppl 10):S16.Crossref, Google Scholar
[8] Chen Y, Hao JK, Glover F (2015) An evolutionary path relinking approach for the quadratic multiple knapsack problem. Knowledge-Based Systems 92:23-34.Crossref, Google Scholar
[9] Duarte A, Laguna M, Martí R, Sánchez-Oro J (2014) Optimization procedures for the bipartite unconstrained 0-1 quadratic programming problem. Comput. Oper. Res. 51:123-129.Crossref, Google Scholar · Zbl 1348.90514
[10] Gallego M, Laguna M, Martí R, Duarte A (2013) Tabu search with strategic oscillation for the maximally diverse grouping problem. J. Oper. Res. Soc. 64(5):724-734.Crossref, Google Scholar
[11] Gillis N, Glineur F (2011) Low-rank matrix approximation with weights or missing data is np-hard. SIAM J. Matrix Anal. Appl. 32(4):1149-1165.Crossref, Google Scholar · Zbl 1242.65077
[12] Glover F (1977) Heuristics for integer programming using surrogate constraints. Decision Sci. 8(1):156-166.Crossref, Google Scholar
[13] Glover F (1997) A template for scatter search and path relinking. Hao JK, Lutton E, Ronald E, Schoenauer M, Snyers D, eds. Artificial Evolution, Lecture Notes in Computer Science, vol. 1363 (Springer, Berlin, Heidelberg), 1-51.Google Scholar
[14] Glover F (2000) Multi-start and strategic oscillation methods—Principles to exploit adaptive memory. Comput. Tools Model. Optim. Simulation 12:1-23.Crossref, Google Scholar
[15] Glover F, Hao J (2010) Efficient evaluations for solving large 0-1 unconstrained quadratic optimization problems. Internat. J. Metaheuristics 1(1):3-10.Crossref, Google Scholar · Zbl 1219.90104
[16] Glover F, Laguna M (1997) Tabu Search (Kluwer, Alphen aan den Rign, Netherlands).Crossref, Google Scholar
[17] Glover F, Kochenberger G, Alidaee B (1998) Adaptive memory tabu search for binary quadratic programs. Management Sci. 44(3):336-345.Link, Google Scholar · Zbl 0989.90072
[18] Glover F, Laguna M, Martí R (2004) Scatter search and path relinking: Foundations and advanced designs. Onwubolu GC, Babu BV, eds. New Optimization Techniques in Engineering, Studies in Fuzziness and Soft Computing, vol. 141, (Springer, Berlin, Heidelberg), 87-99.Crossref, Google Scholar · Zbl 1165.90480
[19] Glover F, Ye T, Punnen AP, Kochenberger G (2015) Integrating tabu search and vlsn search to develop enhanced algorithms: A case study using bipartite boolean quadratic programs. Eur. J. Oper. Res. 241(3):697-707.Crossref, Google Scholar · Zbl 1339.90233
[20] Karapetyan D, Punnen AP (2013) Heuristic algorithms for the bipartite unconstrained 0-1 quadratic programming problem. Working paper, University of Essex, Colchester, UK.Google Scholar
[21] Karapetyan D, Punnen AP, Parkes AJ (2017) Markov chain methods for the bipartite boolean quadratic programming problem. Eur. J. Oper. Res. 260(2):494-506.Crossref, Google Scholar · Zbl 1403.90515
[22] Koyutürk M, Grama A, Ramakrishnan N (2006) Nonorthogonal decomposition of binary matrices for bounded-error data compression and analysis. ACM Trans. Math. Software 32(1):33-69.Crossref, Google Scholar · Zbl 1346.15028
[23] Laguna M, Martí R (1999) Grasp and path relinking for 2-layer straight line crossing minimization. INFORMS J. Comput. 11(1):44-52.Link, Google Scholar · Zbl 1092.90544
[24] López-Ibánez M, Dubois-Lacoste J, Stützle T, Birattari M (2011) The irace package: Iterated racing for automatic algorithm configuration. Technical Report, TR/IRIDIA/2011-004, Université Libre de Bruxelles, IRIDIA, Bruxelles, Belgium.Google Scholar
[25] Lü Z, Glover F, Hao JK (2010) A hybrid metaheuristic approach to solving the ubqp problem. Eur. J. Oper. Res. 207(3):1254-1262.Crossref, Google Scholar · Zbl 1206.90113
[26] Martí R, Duarte A, Laguna M (2009) Advanced scatter search for the max-cut problem. INFORMS J. Comput. 21(1):26-38.Link, Google Scholar · Zbl 1243.90227
[27] Peng B, Lü Z, Cheng T (2015) A tabu search/path pelinking algorithm to solve the job shop scheduling problem. Comput. Oper. Res. 53:154-164.Crossref, Google Scholar · Zbl 1348.90298
[28] Punnen AP, Sripratak P, Karapetyan D (2015a) Average value of solutions for the bipartite boolean quadratic programs and rounding algorithms. Theoret. Comput. Sci. 565:77-89.Crossref, Google Scholar · Zbl 1315.90027
[29] Punnen AP, Sripratak P, Karapetyan D (2015b) The bipartite unconstrained 0-1 quadratic programming problem: Polynomially solvable cases. Discrete Appl. Math. 193:1-10.Crossref, Google Scholar · Zbl 1333.90077
[30] Resende MGC, Ribeiro CC, Glover F, Martí R (2010) Scatter search and path relinking: Fundamentals, advances and applications. Internat. Ser. Oper. Res. Management Sci. 146:87-107.Google Scholar
[31] Shen BH, Ji S, Ye J (2009) Mining discrete patterns via binary matrix factorization. Proc. 15th ACM SIGKDD Internat. Conf. Knowledge Discovery Data Mining (ACM, New York), 757-766.Crossref, Google Scholar
[32] Tanay A, Sharan R, Shamir R (2002) Discovering statistically significant biclusters in gene expression data. Bioinformatics 18(Suppl 1):S136-S144.Crossref, Google Scholar
[33] Wang Y, Lü Z, Glover F, Hao JK (2012) Path relinking for unconstrained binary quadratic programming. Eur. J. Oper. Res. 223(3):595-604.Crossref, Google Scholar · Zbl 1292.90225
[34] Woodruff D, Zemel E (1993) Hashing vectors for tabu search. Ann. Oper. Res. 41(2):123-137.Crossref, Google Scholar · Zbl 0775.90294
[35] Yagiura M, · Zbl 1079.90119
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.