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

References

• 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
• Alon N, Naor A (2006) Approximating the cut-norm via Grothendieck’s inequality. SIAM J. Comput. 35(4):787–803.Crossref, Google Scholar
• 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
• 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
• 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
• 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
• 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
• 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
• 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
• 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
• 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
• Glover F (1977) Heuristics for integer programming using surrogate constraints. Decision Sci. 8(1):156–166.Crossref, Google Scholar
• 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
• 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
• 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
• Glover F, Laguna M (1997) Tabu Search (Kluwer, Alphen aan den Rign, Netherlands).Crossref, Google Scholar
• Glover F, Kochenberger G, Alidaee B (1998) Adaptive memory tabu search for binary quadratic programs. Management Sci. 44(3):336–345.Link, Google Scholar
• 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
• 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
• 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
• 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
• 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
• 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
• 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
• 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
• 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
• 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
• 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
• 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
• 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
• 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
• Tanay A, Sharan R, Shamir R (2002) Discovering statistically significant biclusters in gene expression data. Bioinformatics 18(Suppl 1):S136–S144.Crossref, Google Scholar
• 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
• Woodruff D, Zemel E (1993) Hashing vectors for tabu search. Ann. Oper. Res. 41(2):123–137.Crossref, Google Scholar
• Yagiura M, Toshihide I, Glover F (2006) A path relinking approach with ejection chains for the generalized assignment problem. Eur. J. Oper. Res. 169(2):548–569.Crossref, Google Scholar