Application of the "descent with mutations" metaheuristic to a clique partitioning problem

I. Charon; O. Hudry

doi:10.1109/RIVF.2007.369132

Application of the "descent with mutations" metaheuristic to a clique partitioning problem

I. Charon, O. Hudry

CNRS LTCI

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

Abstract

We study here the application of a metaheuristic, issued from the noising methods and that we call "descent with mutations", to a problem arising in the field of the aggregation of symmetric relations: the clique partitioning of a weighted graph. This local search metaheuristic, of which the design is very simple, is compared with another very efficient metaheuristic, which is a simulated annealing improved by the addition of some ingredients coming from the noising methods. These experiments show that the descent with mutations is at least as efficient for the studied problem as this improved simulated annealing, usually a little better, while, above all, it is much easier to design and to apply.

Original language	English
Title of host publication	2007 IEEE International Conference on Research, Innovation and Vision for the Future, RIVF 2007
Pages	29-35
Number of pages	7
DOIs	https://doi.org/10.1109/RIVF.2007.369132
Publication status	Published - 26 Jun 2007
Externally published	Yes
Event	2007 IEEE International Conference on Research, Innovation and Vision for the Future, RIVF 2007 - Hanoi, Viet Nam Duration: 5 Mar 2007 → 9 Mar 2007

Publication series

Name	2007 IEEE International Conference on Research, Innovation and Vision for the Future, RIVF 2007

Conference

Conference	2007 IEEE International Conference on Research, Innovation and Vision for the Future, RIVF 2007
Country/Territory	Viet Nam
City	Hanoi
Period	5/03/07 → 9/03/07

Keywords

Aggregation of symmetric relations into equivalence relations
Clique partitioning of a graph
Combinatorial optimization
Metaheuristics
Noising methods
Simulated annealing

Access to Document

10.1109/RIVF.2007.369132

Cite this

Charon, I., & Hudry, O. (2007). Application of the "descent with mutations" metaheuristic to a clique partitioning problem. In 2007 IEEE International Conference on Research, Innovation and Vision for the Future, RIVF 2007 (pp. 29-35). Article 4223049 (2007 IEEE International Conference on Research, Innovation and Vision for the Future, RIVF 2007). https://doi.org/10.1109/RIVF.2007.369132

@inproceedings{873cec8d609f4cdea0beea5024749de3,

title = "Application of the {"}descent with mutations{"} metaheuristic to a clique partitioning problem",

abstract = "We study here the application of a metaheuristic, issued from the noising methods and that we call {"}descent with mutations{"}, to a problem arising in the field of the aggregation of symmetric relations: the clique partitioning of a weighted graph. This local search metaheuristic, of which the design is very simple, is compared with another very efficient metaheuristic, which is a simulated annealing improved by the addition of some ingredients coming from the noising methods. These experiments show that the descent with mutations is at least as efficient for the studied problem as this improved simulated annealing, usually a little better, while, above all, it is much easier to design and to apply.",

keywords = "Aggregation of symmetric relations into equivalence relations, Clique partitioning of a graph, Combinatorial optimization, Metaheuristics, Noising methods, Simulated annealing",

author = "I. Charon and O. Hudry",

year = "2007",

month = jun,

day = "26",

doi = "10.1109/RIVF.2007.369132",

language = "English",

isbn = "1424406943",

series = "2007 IEEE International Conference on Research, Innovation and Vision for the Future, RIVF 2007",

pages = "29--35",

booktitle = "2007 IEEE International Conference on Research, Innovation and Vision for the Future, RIVF 2007",

note = "2007 IEEE International Conference on Research, Innovation and Vision for the Future, RIVF 2007 ; Conference date: 05-03-2007 Through 09-03-2007",

}

Charon, I & Hudry, O 2007, Application of the "descent with mutations" metaheuristic to a clique partitioning problem. in 2007 IEEE International Conference on Research, Innovation and Vision for the Future, RIVF 2007., 4223049, 2007 IEEE International Conference on Research, Innovation and Vision for the Future, RIVF 2007, pp. 29-35, 2007 IEEE International Conference on Research, Innovation and Vision for the Future, RIVF 2007, Hanoi, Viet Nam, 5/03/07. https://doi.org/10.1109/RIVF.2007.369132

Application of the "descent with mutations" metaheuristic to a clique partitioning problem. / Charon, I.; Hudry, O.
2007 IEEE International Conference on Research, Innovation and Vision for the Future, RIVF 2007. 2007. p. 29-35 4223049 (2007 IEEE International Conference on Research, Innovation and Vision for the Future, RIVF 2007).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

TY - GEN

T1 - Application of the "descent with mutations" metaheuristic to a clique partitioning problem

AU - Charon, I.

AU - Hudry, O.

PY - 2007/6/26

Y1 - 2007/6/26

N2 - We study here the application of a metaheuristic, issued from the noising methods and that we call "descent with mutations", to a problem arising in the field of the aggregation of symmetric relations: the clique partitioning of a weighted graph. This local search metaheuristic, of which the design is very simple, is compared with another very efficient metaheuristic, which is a simulated annealing improved by the addition of some ingredients coming from the noising methods. These experiments show that the descent with mutations is at least as efficient for the studied problem as this improved simulated annealing, usually a little better, while, above all, it is much easier to design and to apply.

AB - We study here the application of a metaheuristic, issued from the noising methods and that we call "descent with mutations", to a problem arising in the field of the aggregation of symmetric relations: the clique partitioning of a weighted graph. This local search metaheuristic, of which the design is very simple, is compared with another very efficient metaheuristic, which is a simulated annealing improved by the addition of some ingredients coming from the noising methods. These experiments show that the descent with mutations is at least as efficient for the studied problem as this improved simulated annealing, usually a little better, while, above all, it is much easier to design and to apply.

KW - Aggregation of symmetric relations into equivalence relations

KW - Clique partitioning of a graph

KW - Combinatorial optimization

KW - Metaheuristics

KW - Noising methods

KW - Simulated annealing

U2 - 10.1109/RIVF.2007.369132

DO - 10.1109/RIVF.2007.369132

M3 - Conference contribution

AN - SCOPUS:34250747346

SN - 1424406943

SN - 9781424406944

T3 - 2007 IEEE International Conference on Research, Innovation and Vision for the Future, RIVF 2007

SP - 29

EP - 35

BT - 2007 IEEE International Conference on Research, Innovation and Vision for the Future, RIVF 2007

T2 - 2007 IEEE International Conference on Research, Innovation and Vision for the Future, RIVF 2007

Y2 - 5 March 2007 through 9 March 2007

ER -

Application of the "descent with mutations" metaheuristic to a clique partitioning problem

Abstract

Publication series

Conference

Keywords

Access to Document

Fingerprint

Cite this