Mathematical formulation and heuristic methods for the Min--Max Sitting Arrangement Problem in the Cycle

Abstract

The Cyclic Min–Max Sitting Arrangement (CMMSA) is an NP-hard problem which seeks to embed the vertices of a signed input graph, in which edges are labeled as either positive or negative, into the vertices of an unsigned cycle graph, so that the maximum number of conflicts experienced by any single vertex is minimized. A conflict occurs when a negatively connected vertex lies on the shortest path in the cycle between two positively connected ones. We address this problem by proposing two mathematical models designed for commercial solvers and with a tailored Basic Variable Neighborhood Search metaheuristic that combines a greedy constructive start, informed shaking strategies, fast solution evaluation, and a tie-breaking rule. Our evaluation covers instances drawn from synthetic families, real social networks, and engineered graphs adapted from the Harwell–Boeing collection. Under standard time budgets, the proposed method consistently outperforms commercial solvers and a state-of-the-art baseline adapted to this objective, delivering the best results in 266 out of 269 benchmarks and reaching optimal solutions in 153 instances.

Marcos Robles

Artificial Intelligence Phd Student

Marcos Robles graduated in Software Engineering from the Rey Juan Carlos University in 2022. He is working here as a predoctoral researcher focusing in Graph Layout Problems.

Sergio Cavero

Phd in Artificial Intelligence

Sergio Cavero was born Madrid (Spain) on September 24, 1997. He graduated in Software Engineering from Universidad Politécnica de Madrid in 2019. During his undergraduate studies he made a stay at the University of Bradford (UK). In addition, he was awarded twice with the ‘Beca de Excelencia of the Comunidad de Madrid, and also awarded for the Best Final Degree Project. Later, he completed a Master’s Degree in Artificial Intelligence at the same university (UPM) obtaining awards for Best Academic Record (‘Premio José Cuena’) and Best Master’s Thesis. He academic results lend him be beneficiary of one of the ‘Ayudas Para la Formación de Profesorado Universitario (FPU)’, funded by the Spanish Government. He is currently carrying out his doctoral thesis at the Universidad Rey Juan Carlos, supervised by Professors Abraham Duarte and Eduardo G. Pardo. His main research interests focus on the interface among Computer Science, Artificial Intelligence and Operations Research. Most of his publications deal with the development of metaheuristics procedures for optimization problems modeled by graphs.