Discrete Applied Mathematics

Discrete Applied Mathematics

0.00 Avg rating0 Votes
Article ID: iaor20002312
Country: Netherlands
Volume: 96/97
Start Page Number: 3
End Page Number: 27
Publication Date: Oct 1999
Journal: Discrete Applied Mathematics
Authors: ,
Keywords: constraint handling languages
Abstract:

In this paper the performance of the Hamming-based Reactive Tabu Search (H-RTS) algorithm 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 of 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.

Reviews

Required fields are marked *. Your email address will not be published.