Combining solutions of the optimum satisfiability problem using evolutionary tunneling
Abstract
The optimum satisfiability problem involves determining values for Boolean variables to satisfy a Boolean expression, while maximizing the sum of coefficients associated with the variables chosen to be true. Existing literature has identified a tabu search heuristic as the best method to deal with hard instances of the problem. This paper combines the tabu search with a simple evolutionary heuristic based on the idea of tunneling between local optima. When combining a set of solutions, variables with common values in all solutions are identified and fixed. The remaining free variables in the problem may be decomposed into several independent subproblems, so that parts of the solutions combined can be extracted and combined in an improved solution. This solution can be further improved by applying the tabu search in an improvement stage. The value of the new heuristic is demonstrated in extensive computational experiments on both existing and new test instances.
References
Bixby, R. Mixed integer programming: It works better than you may think. slide presentation, Gurobi Optimization, 2010.
Cook, S.The complexity of theorem-proving procedures. In Proceedings of the Third ACM Symposium on Theory of Computing (1971), pp. 151–158.
CPLEX, 2020. https://www.ibm.com/support/knowledgecenter/en/SSSA5P12.9.0/.
Davoine, T., Hammer, P., and Vizvari, B. A heuristic for boolean optimization problems. Journal of Heuristics 9(2003), 229–247.
Du, D., Gu, J., and Pardalos, P., Eds. Satisfiability Problem: Theory and Applications, vol. 35 of DIMACS Series in Discrete Mathematics and Theoretical Computer Science. 1997.
Glover, F. A template for scatter search and path relinking. In Artificial Evolution, J.-K. Hao, E. Lutton, E. Ronald, M. Schoenauer, and D. Snyers, Eds., vol. 1363 of Lecture Notes in Computer Science. Springer, 1997, pp. 13–54.
Glover, F. Adaptive Memory Projection Methods for Integer Programming. Springer US, Boston, MA, 2005, pp. 425–440.
Glover, F. Parametric tabu search for mixed integer programs.Computers and Operations Research 33(2006), 2449–2494.
Glover, F., and Laguna, M. Tabu Search. Kluwer Academic Publisher, Boston, Dordrecht, London, 1997.
Hutter, F., Hoos, H., and Leyton-Brown, K.Sequential model-based optimization for gen-eral algorithm configuration. In LION-5(2011),LNCS, pp. 507–523.
Hvattum, L., Løkketangen, A., and Glover, F. Adaptive memory search for booleanoptimization problems. Discrete Applied Mathematics 142(2004), 99–109.
Hvattum, L., Løkketangen, A., and Glover, F. New heuristics and adaptive memory procedures for boolean optimization problems. In Integer Programming: Theory and Practice, J. Karlof, Ed. CRC Press, Boca Raton, FL, 2006, pp. 1–18.
Hvattum, L., Løkketangen, A., and Glover, F. Comparisons of commercial MIP solvers and an adaptive memory (tabu search) procedure for a class of 0–1 integer programming problems. Algorithmic Operations Research7(2012), 13–21.
Koch, T., Achterberg, T., Andersen, E., Bastert, O., Berthold, T., Bixby, R., Danna, E., Gamrath, G., Gleixner, A., Heinz, S., Lodi, A., Mittelmann, H., Ralphs, T., Salvagnin, D., Steffy, D., and Wolter, K. MIPLIB 2010 - mixed integer pro-gramming library version 5. Mathematical Programming Computation 3(2011), 103–163.
Lodi, A. MIP computation and beyond. Technical Report ARRIVAL-TR-0229, 2008.
Løkketangen, A., and Glover, F. Surrogate constraint analysis — new heuristics and learning schemes for satisfiability problems. In Satisfiability Problem: Theory and Applications, D. Du,J. Gu, and P. Pardalos, Eds., vol. 35 of DIMAC SSeries in Discrete Mathematics and TheoreticalComputer Science. 1997.
Løkketangen, A., and Olsson, R. Generating metaheuristic optimization code using ADATE. Journal of Heuristics 16(2010), 911–930.
Selman, B., Mitchell, D., and Levesque, H.Generating hard satisfiability problems. Artificial Intelligence 81(1996), 17–29.
Whitley, D. Next generation genetic algorithms: a user’s guide and tutorial. In Handbook of Metaheuristics, M. Gendreau and J.-Y. Potvin, Eds., 3rd ed., vol. 272 of International Series in Operations Research & Management Science. Springer,Switzerland, 2019, pp. 245–274.
Copyright (c) 2020 MENDEL
This work is licensed under a Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International License.
MENDEL open access articles are normally published under a Creative Commons Attribution-NonCommercial-ShareAlike (CC BY-NC-SA 4.0) https://creativecommons.org/licenses/by-nc-sa/4.0/ . Under the CC BY-NC-SA 4.0 license permitted 3rd party reuse is only applicable for non-commercial purposes. Articles posted under the CC BY-NC-SA 4.0 license allow users to share, copy, and redistribute the material in any medium of format, and adapt, remix, transform, and build upon the material for any purpose. Reusing under the CC BY-NC-SA 4.0 license requires that appropriate attribution to the source of the material must be included along with a link to the license, with any changes made to the original material indicated.
