# zbMATH — the first resource for mathematics

Merging variables: one technique of search in pseudo-Boolean optimization. (English) Zbl 1429.90100
Bykadorov, Igor (ed.) et al., Mathematical optimization theory and operations research. 18th international conference, MOTOR 2019, Ekaterinburg, Russia, July 8–12, 2019. Revised selected papers. Cham: Springer. Commun. Comput. Inf. Sci. 1090, 86-102 (2019).
Summary: In the present paper, we describe new heuristic technique, which can be applied to the optimization of pseudo-Boolean functions including Black-Box functions. This technique is based on a simple procedure which consists in transition from the optimization problem over Boolean hypercube to the optimization problem of auxiliary function in a specially constructed metric space. It is shown that there is a natural connection between the points of the original Boolean hypercube and points from new metric space. For a Boolean hypercube with fixed dimension it is possible to construct a number of such metric spaces. The proposed technique can be considered as a special case of Variable Neighborhood Search, which is focused on pseudo-Boolean optimization. Preliminary computational results show high efficiency of the proposed technique on some reasonably hard problems. Also it is shown that the described technique in combination with the well-known $$(1+1)$$-Evolutionary Algorithm allows to decrease the upper bound on the runtime of this algorithm for arbitrary pseudo-Boolean functions.
For the entire collection see [Zbl 1428.90004].
##### MSC:
 90C59 Approximation methods and heuristics in mathematical programming
##### Software:
CaDiCaL; Lingeling; Plingeling; Tabu search; Transalg; Treengeling; YalSAT
Full Text:
##### References:
 [1] Boros, E., Hammer, P.L.: Pseudo-boolean optimization. Discrete Appl. Math. 123(1-3), 155-225 (2002) · Zbl 1076.90032 [2] Biere, A., Heule, M., van Maaren, H., Walsh, T. (eds.): Handbook of Satisfiability, vol. 185. IOS Press, Amsterdam (2009) · Zbl 1183.68568 [3] Burke, E., Kendall, G. (eds.): Search Methodologies, 2nd edn. Springer, New York (2014). https://doi.org/10.1007/978-1-4614-6940-7 [4] McWilliams, F., Sloan, N.: The Theory of Error-Correcting Codes. North Holland, Amsterdam (1983) [5] Luke, S.: Essentials of Metaheuristics, 2nd edn. George Mason University, Fairfax (2015) [6] Rudolph, G.: Convergence properties of evolutionary algorithms. Ph.D. thesis, Hamburg (1997) · Zbl 0891.93089 [7] Droste, S., Jansen, T., Wegener, I.: On the analysis of the (1+1) evolutionary algorithm. Theor. Comput. Sci. 276(1-2), 51-81 (2002) · Zbl 1002.68037 [8] Stanley, R.: Enumerative Combinatorics. Cambridge University Press, Cambridge (2011) · Zbl 1247.05003 [9] Feller, W.: An Introduction to Probability Theory and its Applications, 3rd edn. Wiley, Hoboken (1970) · Zbl 0158.34902 [10] Mladenović, N., Hansen, P.: Variable neighborhood search. Comput. Oper. Res. 24(11), 1097-1100 (1997) · Zbl 0889.90119 [11] Hansen, P., Mladenović, N.: Variable neighborhood search: principles and applications. Eur. J. Oper. Res. 130(3), 449-467 (2001) · Zbl 0981.90063 [12] Hansen, P., Mladenović, N., Todosijević, R., Hanafi, S.: Variable neighborhood search: basics and variants. EURO J. Comput. Optim. 5(3), 423-454 (2016) · Zbl 1390.90586 [13] Glover, F., Laguna, M.: Tabu Search. Kluwer Academic Publishers, Dordrecht (1997) · Zbl 0930.90083 [14] Eén, N., Sörensson, N.: Translating pseudo-boolean constraints into SAT. JSAT 2(1-4), 1-26 (2006) · Zbl 1116.68083 [15] Rivest, R.L.: The MD4 message digest algorithm. In: Menezes, A.J., Vanstone, S.A. (eds.) CRYPTO 1990. LNCS, vol. 537, pp. 303-311. Springer, Heidelberg (1991). https://doi.org/10.1007/3-540-38424-3_22 · Zbl 0800.68418 [16] Otpuschennikov, I., Semenov, A., Gribanova, I., Zaikin, O., Kochemazov, S.: Encoding cryptographic functions to SAT using TRANSALG system. In: The 22nd European Conference on Artificial Intelligence (ECAI 2016). Frontiers in Artificial Intelligence and Applications, vol. 285, pp. 1594-1595. IOS Press (2016) [17] Marques-Silva, J.P., Lynce, I., Malik, S.: Conflict-driven clause learning SAT solvers. In: Biere et al. [2], pp. 131-153 [18] Williams, R., Gomes, C.P., Selman, B.: Backdoors to typical case complexity. In: The 18th International Joint Conference on Artificial Intelligence (IJCAI 2003), pp. 1173-1178 (2003) [19] Soos, M., Nohl, K., Castelluccia, C.: Extending SAT solvers to cryptographic problems. In: Kullmann, O. (ed.) SAT 2009. LNCS, vol. 5584, pp. 244-257. Springer, Heidelberg (2009). https://doi.org/10.1007/978-3-642-02777-2_24 [20] Biere, A.: CaDiCaL, Lingeling, Plingeling, Treengeling, YalSAT entering the SAT competition 2017. In: Balyo, T., Heule, M.J.H., Järvisalo, M. (eds.) SAT Competition 2017, vol. B-2017-1, pp. 14-15 (2017) [21] Ahuja, R.K., Ergun, O., Orlin, J.B., Punnen, A.P.: A survey of very large-scale neighborhood search techniques. Discrete Appl. Math. 123(1-3), 75-102 (2002) · Zbl 1014.68052 [22] Avella, P., D’Auria, B., Salerno, S., Vasil’ev, I.: A computational study of local search algorithms for italian high-school timetabling. J. Heuristics 13(6), 543-556 (2007) · Zbl 1144.90451 [23] Doerr, B.: Analyzing randomized search heuristics via stochastic domination. Theor. Comput. Sci. 773, 115-137 (2019) · Zbl 07057289 [24] Li, C., Manya, F.: MaxSAT. In: Biere et al. [2], pp. 613-632 [25] Ansótegui, C., Heymann, B., Pon, J., Sellmann, M., Tierney, K.: Hyper-reactive tabu search for MaxSAT. In: Battiti, R., Brunato, M., Kotsireas, I., Pardalos, P.M. (eds.) LION 12 2018. LNCS, vol. 11353, pp. 309-325. Springer, Cham (2019). https://doi.org/10.1007/978-3-030-05348-2_27 [26] Bouhmala, N., Øvergård, K.I.: Combining genetic algorithm with variable neighborhood search for MAX-SAT. In: Zelinka, I., Vasant, P., Duy, V.H., Dao, T.T. (eds.) Innovative Computing, Optimization and Its Applications. SCI, vol. 741, pp. 73-92. Springer, Cham (2018). https://doi.org/10.1007/978-3-319-66984-7_5
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.