A simulated annealing algorithm with the random compound move for the sequential partitioning problem of directed acyclic graphs

A simulated annealing algorithm with the random compound move for the sequential partitioning problem of directed acyclic graphs

0.00 Avg rating0 Votes
Article ID: iaor20001018
Country: Netherlands
Volume: 112
Issue: 1
Start Page Number: 147
End Page Number: 157
Publication Date: Jan 1999
Journal: European Journal of Operational Research
Authors: ,
Keywords: optimization: simulated annealing
Abstract:

In this paper, we present an approach for finding a minimum cost partition of the nodes of a directed acyclic graph into subsets of a given size, subject to the constraint that the precedence relationships along the elements are satisfied, based on the concept of simulated annealing. Simulated annealing is generally applicable, and can be used to obtain solutions arbitrarily close to an optimum. However, the standard simulated annealing approach with a conventional neighbourhood structure does not yield good solutions for this problem, since this is a multiple partitioning problem and the number of subsets is not fixed. For this problem, we develop an effective neighbourhood structure and a new acceptance criterion. We also assess the effectiveness of the developed algorithm. The results show that this proposed algorithm outperforms, in terms of solution quality, any other algorithm using tabu search. The computational time of the procedure is proportional to the number of nodes in the graph.

Reviews

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