×

Reactive local search techniques for the maximum \(k\)-conjunctive constraint satisfaction problem \((MAX-k-CCSP)\). (English) Zbl 0941.68149

Summary: The performance of the Hamming-based Reactive Tabu Search algorithm (H-RTS) previously proposed for the maximum satisfiability problem is studied for the different maximum \(k\)-conjunctive constraint satisfaction problem. In addition, the use of non-oblivious functions recently proposed in the framework approximation algorithms is investigated. In particular, two relevant special cases of the maximum \(k\)-conjunctive constraint satisfaction problem are considered: maximum directed cut and maximum independent set in cubic graphs. The preliminary diversification-bias analysis of the basic components shows a remarkable difference between the two problems, and the derived predictions are then validated by extensive experiments with the complete H-RTS algorithm. The performance of H-RTS is compared with that of simulated annealing and simple repeated local search.

MSC:

68W05 Nonnumerical algorithms
68P10 Searching and sorting

Software:

CCSP
PDFBibTeX XMLCite
Full Text: DOI

References:

[2] Alimonti, P., New local search approximation techniques for maximum generalized satisfiability problems, Inform. Process. Lett., 57, 151-158 (1996) · Zbl 1022.68560
[5] Ausiello, G.; Crescenzi, P.; Protasi, M., Approximate solution of NP optimization problems, Theoret. Comput. Sci., 150, 1-55 (1995) · Zbl 0874.68145
[6] Ausiello, G.; Protasi, M., Local search, reducibility and approximability of NP optimization problems, Inform. Proces. Lett., 54, 73-79 (1995) · Zbl 1022.68561
[10] Battiti, R.; Tecchiolli, G., The reactive tabu search, ORSA J. Comput., 6, 2, 126-140 (1994) · Zbl 0807.90094
[13] Erdos, P.; Renyi, A., On random graph I, Publ. Math. Debrecen, 6, 290-297 (1959) · Zbl 0092.15705
[15] Ferreira, A. G.; Zerovnik, J., Bounding the probability of success of stochastic methods for global optimization, Comput. Math. Appl., 25, 1-8 (1993) · Zbl 0806.90103
[16] Glover, F., Tabu search – part I, ORSA J. Comput., 1, 3, 190-260 (1989) · Zbl 0753.90054
[17] Goemans, M. X.; Williamson, D. P., New \(34\)-approximation algorithms for the maximum satisfiability problem, SIAM J. Discrete Math., 7, 4, 656-666 (1994) · Zbl 0812.90129
[18] Goemans, M. X.; Williamson, D. P., Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming, J. ACM, 42, 6, 1115-1145 (1995) · Zbl 0885.68088
[19] Greenlaw, R.; Petreschi, R., Cubic graphs, ACM Comput. Surveys, 27, 471-495 (1995)
[21] Hansen, P.; Jaumard, B., Algorithms for the maximum satisfiability problem, Computing, 44, 279-303 (1990) · Zbl 0716.68077
[23] Hopfield, J. J.; Tank, D. W., Neural computation of decisions in optimization problems, Biol. Cybernet., 52, 141-152 (1985) · Zbl 0572.68041
[27] Kirkpatrick, S.; Gelatt, C. D.; Vecchi, M. P., Optimization by simulated annealing, Science, 220, 671-680 (1983) · Zbl 1225.90162
[28] Papadimitriou, C. H.; Yannakakis, M., Optimization, approximation and complexity classes, J. Comput. System Sci., 43, 425-440 (1991) · Zbl 0765.68036
[31] Yannakakis, M., On the approximation of maximum satisfiability, J. Algorithms, 17, 475-502 (1994) · Zbl 0820.68056
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.