Combining solutions of the optimum satisfiability problem using evolutionary tunneling

  • Rodrigo Ferreira da Silva Universidade Federal de Minas Gerais
  • Lars Magnus Hvattum Molde University College
  • Fred Glover OptTek System Inc.
Keywords: zero-one integer programming, boolean optimization, metaheuristic, tabu search, adaptive memory programming, recombination operator

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.

Published
2020-08-24
How to Cite
[1]
da Silva, R., Hvattum, L.M. and Glover, F. 2020. Combining solutions of the optimum satisfiability problem using evolutionary tunneling. MENDEL. 26, 1 (Aug. 2020), 23-29. DOI:https://doi.org/10.13164/mendel.2020.1.023.
Section
Research articles