Fortran subroutines for computing approximate solutions of weighted MAX-SAT problems using GRASP

This paper describes Fortran subroutines for computing approximate solution s to the weighted MAX-SAT problem using a greedy randomized adaptive search procedure (GRASP). The algorithm (Resende, Pitsoulis, and Pardalos, in: D. Z. Du et al. (Ed.), Satisfiability problem: Theory and Applications, Vol. 3 5 DIMACS Series on Discrete Mathametics and Theoretical Computer Science, A merican Mathematical Society, Providence, RI, 1997, pp. 393-405) is briefly outlined and its implementation is discussed. Usage of the subroutines is considered in detail. The subroutines are tested on a set of test problems, illustrating the tradeoff between running lime and solution quality. (C) 2 000 Elsevier Science B.V. All rights reserved.