skip to main content
article

GRASP with path relinking for the weighted MAXSAT problem

Published: 09 February 2007 Publication History

Abstract

A GRASP with path relinking for finding good-quality solutions of the weighted maximum satisfiability problem (MAX-SAT) is described in this paper. GRASP, or Greedy Randomized Adaptive Search Procedure, is a randomized multistart metaheuristic, where, at each iteration, locally optimal solutions are constructed, each independent of the others. Previous experimental results indicate its effectiveness for solving weighted MAX-SAT instances. Path relinking is a procedure used to intensify the search around good-quality isolated solutions that have been produced by the GRASP heuristic. Experimental comparison of the pure GRASP (without path relinking) and the GRASP with path relinking illustrates the effectiveness of path relinking in decreasing the average time needed to find a good-quality solution for the weighted maximum satisfiability problem.

References

[1]
Aiex, R. M., Binato, S., and Resende, M. 2003. Parallel GRASP with path-relinking for job shop scheduling. Parallel Computing 29, 393--430.
[2]
Aiex, R. M., Resende, M. G. C., Pardalos, P. M., and Toraldo, G. 2005. GRASP with path relinking for three-index assignment. INFORMS J. on Computing 17, 2, 224--247.
[3]
Asano, T. 1997. Approximation algorithms for MAX-SAT: Yannakakis vs. Goemans-Williamson. In 5th IEEE Israel Symposium on the Theory of Computing and Systems. 24--37.
[4]
Battiti, R. and Protasi, M. 1997. Reactive search, a history-sensitive heuristic for MAX-SAT. ACM Journal of Experimental Algorithms 2, 2.
[5]
Battiti, R. and Protasi, M. 1998. Approximate algorithms and heuristics for the MAX-SAT. In Handbook of Combinatorial Optimization, D. Z. Du and P. M. Pardalos, Eds. vol. 1. Kluwer Academic Publ., Boston, MA. 77--148.
[6]
Canuto, S. A., Resende, M. G. C., and Ribeiro, C. C. 2001. Local search with perturbations for the prize-collecting Steiner tree problem in graphs. Networks 38, 50--58.
[7]
Chen, J., Friesen, D., and Zheng, H. 1997. Tight bound on johnson's algorithm for MAX-SAT. In Proceedings of the 12th Annual IEEE Conference on Computational Complexity. 274--281.
[8]
Cook S. A. 1971. The complexity of theorem-proving procedures. In Proceedings of the Third Annual ACM Symposium on Theory of Computing. 151--158.
[9]
Feige, U. and Goemans, M. X. 1995. Approximating the value of two proper proof systems, with applications to MAX-2SAT and MAX-DICUT. In Proceedings of the Third Israel Symposium on Theory of Computing and Systems. 182--189.
[10]
Feo, T. A. Resende, M. G. C., and Smith, S. H. 1994. A greedy randomized adaptive search procedure for maximum independent set. Operations Research 42, 860--878.
[11]
Garey, M. R. and Johnson, D. S. 1979. Computers and intractability: A guide to the theory of NP-completeness. Freeman, San Francisco, CA.
[12]
Gent, I. P. and Walsh, T. 1993. Towards an understanding of hill-climbing procedures for SAT. In Proceedings of the 11th National Conference on Artificial Intelligence. 28--33.
[13]
Glover, F. 1996. Tabu search and adaptive memory programming: Advances, applications and challenges. In Interfaces in Computer Science and Operations Research, R. S. Barr, R. V. Helgason, and J. L. Kennington, Eds. Kluwer Academic Publ. Boston, MA. 1--75.
[14]
Goemans, M. X. and Williamson, D. P. 1994. A new 3/4 approximation algorithm for the maximum satisfiability problem. SIAM Journal on Discrete Mathematics 7, 656--666.
[15]
Goemans, M. X. and Williamson, D. P. 1995. Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming. Journal of Association for Computing Machinery 42, 6, 1115--1145.
[16]
Hansen, P. and Jaumard, B. 1990. Algorithms for the maximum satisfiability problem. Computing 44, 279--303.
[17]
Hart, J. P. and Shogan, A. W. 1987. Semi greedy heuristics: An empirical study. Operations Research Letters 6, 107--114.
[18]
Hastad, J. 2001. Some optimal inapproximability results. Journal of the ACM 48, 798--859.
[19]
Johnson, D. S. 1974. Approximation algorithms for combinatorial problems. Journal of Computer and System Sciences 9, 256--278.
[20]
Johnson, D. S., Papadimitriou, C. H., and Yannakakis, M. 1988. How easy is local search? Journal of Computer and System Sciences 37, 79--100.
[21]
Johnson, D. S. and Trick, M. A., Eds. 1996. Cliques, coloring, and Satisfiability: Second DIMACS Implementation Challenge. DIMACS Series in Discrete Mathematics and Theoretical Computer Science. American Mathematical Society.
[22]
Karloff, H. and Zwick, U. 1997. A 7/8-approximation algorithm for MAX-3SAT. In Proceedings of the 38th Annual IEEE Symposium on Foundations of Computer Science. 406--415.
[23]
Krentel, M. W. 1988. The complexity of optimization problems. Journal of Computer and System Sciences 36.
[24]
Laguna, M. and Martí, R. 1999. GRASP and path relinking for 2-layer straight line crossing minimization. INFORMS Journal on Computing 11, 44--52.
[25]
Resende, M. G. C. and Feo, T. A. 1996. A GRASP for Satisfiability. In Cliques, Coloring, and Satisfiability: Second DIMACS Implementation Challenge, D. S. Johnson and M. A. Trick, Eds. Number 26 in DIMACS Series in Discrete Mathematics and Theoretical Computer Science. American Mathematical Society. New Providence, Rhode Island. 499--520.
[26]
Resende, M. G. C. and Pitsoulis, L. S. 2002. Greedy randomized adaptive search procedures. In Handbook of Applied Optimization, P. M. Pardalos and M. Resende, Eds. Oxford University Press, Oxford. 168--183.
[27]
Resende, M. G. C., Pitsoulis, L. S., and Pardalos, P. M. 1997. Approximate solutions of weighted MAX-SAT problems using GRASP. In Satisfiability Problem: Theory and Applications, D.-Z. Du, J. Gu, and P. M. Pardalos, Eds. DIMACS Series in Discrete Mathematics and Theoretical Computer Science, American Mathematical Society. 393--405.
[28]
Resende, M. G. C., Pitsoulis, L. S., and Pardalos, P. M. 2000. Fortran subroutines for computing approximate solutions of weighted MAX-SAT problems using GRASP. Discrete Applied Mathematics 100, 95--113.
[29]
Resende, M. G. C. and Ribeiro, C. C. 2003. A GRASP with path-relinking for private virtual circuit routing. Networks 41, 104--114.
[30]
Resende, M. G. C. and Ribeiro, C. C. 2005. GRASP and path-relinking: Recent advances and applications. In Metaheuristics: Progress as Real Problem Solvers, T. Ibaraki, K. Nonobe, and M. Yagiura, Eds. Springer, New York. 29--63.
[31]
Ribeiro, C. C., Uchoa, E., and Werneck, R. F. 2002. A hybrid GRASP with perturbations for the Steiner problem in graphs. INFORMS Journal on Computing 14, 228--246.
[32]
Selman, B., Levesque, H., and Mitchell, D. 1992. A new method for solving hard satisfiability instances. In Proceedings of the 10th National Conference on Artificial Intelligence. 440--446.
[33]
Spears, W. M. 1996. Simulated annealing for hard satisfiability problems. In Cliques, Coloring, and Satisfiability: Second DIMACS Implementation Challenge, D. S. Johnson and M. A. Trick, Eds. Number 26 in DIMACS Series in Discrete Mathematics and Theoretical Computer Science. American Mathematical Society. New Providence, Rhode Island. 533--555.
[34]
Trevisan, L. 2000. Approximating satisfiable satisfiability problems. Algorithmica 28, 1, 145--172.
[35]
Yannakakis, M. 1992. On the approximation of maximum Satisfiability. In Proceedings of the Third ACM-SIAM Symposium on Discrete Algorithms. 1--9.

Cited By

View all
  • (2022)Mathematical formulations and solution methods for the uncapacitated r-allocation p-hub maximal covering problemDiscrete Optimization10.1016/j.disopt.2021.10067243:COnline publication date: 1-Feb-2022
  • (2019)The Multi-Parent Biased Random-Key Genetic Algorithm with Implicit Path-Relinking and its real-world applicationsEuropean Journal of Operational Research10.1016/j.ejor.2019.11.037Online publication date: Nov-2019
  • (2018)Extending time‐to‐target plots to multiple instancesInternational Transactions in Operational Research10.1111/itor.1250725:5(1515-1536)Online publication date: 12-Feb-2018
  • Show More Cited By

Index Terms

  1. GRASP with path relinking for the weighted MAXSAT problem

    Recommendations

    Comments

    Information & Contributors

    Information

    Published In

    cover image ACM Journal of Experimental Algorithmics
    ACM Journal of Experimental Algorithmics  Volume 11, Issue
    2006
    355 pages
    ISSN:1084-6654
    EISSN:1084-6654
    DOI:10.1145/1187436
    Issue’s Table of Contents

    Publisher

    Association for Computing Machinery

    New York, NY, United States

    Publication History

    Published: 09 February 2007
    Published in JEA Volume 11

    Author Tags

    1. Algorithms
    2. GRASP
    3. experimentation
    4. heuristics
    5. path relinking
    6. performance
    7. time-to-target plots

    Qualifiers

    • Article

    Contributors

    Other Metrics

    Bibliometrics & Citations

    Bibliometrics

    Article Metrics

    • Downloads (Last 12 months)5
    • Downloads (Last 6 weeks)0
    Reflects downloads up to 14 Feb 2025

    Other Metrics

    Citations

    Cited By

    View all
    • (2022)Mathematical formulations and solution methods for the uncapacitated r-allocation p-hub maximal covering problemDiscrete Optimization10.1016/j.disopt.2021.10067243:COnline publication date: 1-Feb-2022
    • (2019)The Multi-Parent Biased Random-Key Genetic Algorithm with Implicit Path-Relinking and its real-world applicationsEuropean Journal of Operational Research10.1016/j.ejor.2019.11.037Online publication date: Nov-2019
    • (2018)Extending time‐to‐target plots to multiple instancesInternational Transactions in Operational Research10.1111/itor.1250725:5(1515-1536)Online publication date: 12-Feb-2018
    • (2018)A Novel Greedy Randomized Dynamic Ensemble Selection AlgorithmNeural Processing Letters10.1007/s11063-017-9670-y47:2(565-599)Online publication date: 1-Apr-2018
    • (2015)Satisfiability by Maxwell-Boltzmann and Bose-Einstein Statistical DistributionsACM Journal of Experimental Algorithmics10.1145/262949819(1.1-1.15)Online publication date: 7-Jan-2015
    • (2015)An effective variable selection heuristic in SLS for weighted Max-2-SATJournal of Heuristics10.1007/s10732-015-9284-321:3(433-456)Online publication date: 1-Jun-2015
    • (2013)Hybridizations of GRASP with Path-RelinkingHybrid Metaheuristics10.1007/978-3-642-30671-6_5(135-155)Online publication date: 2013
    • (2012)Path-relinking intensification methods for stochastic local search algorithmsJournal of Heuristics10.1007/s10732-011-9167-118:2(193-214)Online publication date: 1-Apr-2012
    • (2012)Global equilibrium search algorithms for combinatorial optimization problemsProceedings of the 12th international conference on Parallel Problem Solving from Nature - Volume Part II10.1007/978-3-642-32964-7_28(277-286)Online publication date: 1-Sep-2012
    • (2011)The analysis of expected fitness and success ratio of two heuristic optimizations on two bimodal MaxSAT problemsJournal of Global Optimization10.1007/s10898-011-9790-254:4(745-764)Online publication date: 25-Sep-2011

    View Options

    Login options

    Full Access

    View options

    PDF

    View or Download as a PDF file.

    PDF

    eReader

    View online with eReader.

    eReader

    Figures

    Tables

    Media

    Share

    Share

    Share this Publication link

    Share on social media