Backbone guided tabu search for solving the UBQP problem
Tóm tắt
We propose a backbone-guided tabu search (BGTS) algorithm for the Unconstrained Binary Quadratic Programming (UBQP) problem that alternates between two phases: (1) a basic tabu search procedure to optimize the objective function as far as possible; (2) a strategy using the TS notion of strongly determined variables to alternately fix and free backbone components of the solutions which are estimated likely to share values in common with an optimal solution. Experimental results show that the proposed method is capable of finding the best-known solutions for 21 large random instances with 3000 to 7000 variables and boosts the performance of the basic TS in terms of both solution quality and computational efficiency.
Tài liệu tham khảo
Alidaee, B., Kochenberger, G.A., Ahmadian, A.: 0-1 quadratic programming approach for the optimal solution of two scheduling problems. Int. J. Syst. Sci. 25, 401–408 (1994)
Alidaee, B., Kochenberger, G.A., Lewis, K., Lewis, M., Wang, H.: A new approach for modeling and solving set packing problems. Eur. J. Oper. Res. 86(2), 504–512 (2008)
Amini, M., Alidaee, B., Kochenberger, G.A.: A Scatter Search Approach to Unconstrained Quadratic Binary Programs. New Methods in Optimization, pp. 317–330. McGraw–Hill, New York (1999)
Borgulya, I.: An evolutionary algorithm for the binary quadratic problems. Adv. Soft Comput. 2, 3–16 (2005)
Boros, E., Hammer, P.L., Tavares, G.: Local search heuristics for quadratic unconstrained binary optimization (qubo). J. Heuristics 13, 99–132 (2007)
Boros, E., Hammer, P.L., Sun, R., Tavares, G.: A max-flow approach to improved lower bounds for quadratic 0-1 minimization. Discrete Optim. 5(2), 501–529 (2008)
Chardaire, P., Sutter, A.: A decomposition method for quadratic zero-one programming. Manag. Sci. 41(4), 704–712 (1994)
Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-Completeness. Freeman, New York (1979)
Glover, F.: Heuristics for integer programming using surrogate constraints. Decis. Sci. 8(1), 156–166 (1977)
Glover, F.: Adaptive memory projection methods for integer programming. In: Rego, C., Alidaee, B. (eds.) Metaheuristic Optimization Via Memory and Evolution, pp. 425–440. Kluwer Academic, Dordrecht (2005)
Glover, F., Hao, J.K.: Efficient evaluations for solving large 0-1 unconstrained quadratic optimization problems. Int. J. Metaheuristics 1(1), 3–10 (2010)
Glover, F., Laguna, M.: Tabu Search. Kluwer Academic, Boston (1997)
Glover, F., Kochenberger, G.A., Alidaee, B.: Adaptive memory tabu search for binary quadratic programs. Manag. Sci. 44, 336–345 (1998)
Glover, F., Alidaee, B., Rego, C., Kochenberger, G.A.: One-pass heuristics for large-scale unconstrained binary quadratic problems. Eur. J. Oper. Res. 137, 272–287 (2002)
Glover, F., Lü, Z., Hao, J.K.: Diversification-driven tabu search for unconstrained binary quadratic problems. 4OR, Q. J. Oper. Res. 8(3), 239–253 (2010)
Harary, F.: On the notion of balance of a signed graph. Mich. Math. J. 2, 143–146 (1953)
Horst, R., Pardalos, P.M., Thoai, N.V.: Introduction to Global Optimization. Kluwer Academic, Boston (2000)
Katayama, K., Narihisa, H.: Performance of simulated annealing-based heuristic for the unconstrained binary quadratic programming problem. Eur. J. Oper. Res. 134, 103–119 (2001)
Kilby, P., Slaney, J.K., Thiebaux, S.T.: Backbones and backdoors in satisfiability. In: Proceedings of AAAI-2005, pp. 1368–1373 (2005)
Kochenberger, G.A., Glover, F., Alidaee, B., Rego, C.: A unified modeling and solution framework for combinatorial optimization problems. OR Spektrum 26, 237–250 (2004)
Kochenberger, G.A., Glover, F., Alidaee, B., Rego, C.: An unconstrained quadratic binary programming approach to the vertex coloring problem. Ann. Oper. Res. 139, 229–241 (2005)
Krarup, J., Pruzan, A.: Computer aided layout design. Math. Program. Stud. 9, 75–94 (1978)
Lewis, M., Kochenberger, G.A., Alidaee, B.: A new modeling and solution approach for the set-partitioning problem. Comput. Oper. Res. 35(3), 807–813 (2008)
Lewis, M., Alidaee, B., Glover, F., Kochenberger, G.A.: A note on xqx as a modelling and solution framework for the linear ordering problem. Int. J. Oper. Res. 5(2), 152–162 (2009)
Lü, Z., Glover, F., Hao, J.K.: A hybrid metaheuristic approach to solving the ubqp problem. Eur. J. Oper. Res. 207(3), 1254–1262 (2010)
McBride, R.D., Yormark, J.S.: An implicit enumeration algorithm for quadratic integer programming. Manag. Sci. 26, 282–296 (1980)
Merz, P., Katayama, K.: Memetic algorithms for the unconstrained binary quadratic programming problem. Biosystems 78, 99–118 (2004)
Monasson, R., Zecchina, R., Kirkpatrick, S., Selman, B., Troyansky, L.: Determining computational complexity for characteristic ‘phase transitions’. Nature 400, 133–137 (1998)
Palubeckis, G.: Multistart tabu search strategies for the unconstrained binary quadratic optimization problem. Ann. Oper. Res. 131, 259–282 (2004)
Palubeckis, G.: Iterated tabu search for the unconstrained binary quadratic optimization problem. Informatica 17(2), 279–296 (2006)
Wilbaut, C., Salhi, S., Hanafi, S.: An iterative variable-based fixation heuristic for 0-1 multidimensional knapsack problem. Eur. J. Oper. Res. 199, 339–348 (2009)
Zhang, W.: Configuration landscape analysis and backbone guided local search. Part 1: Satisfiability and maximum satisfiability. Artif. Intell. 158, 1–26 (2004)