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

Resumen

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

Estudiante de Doctorado en Inteligencia Artificial

Marcos Robles se graduó en Ingeniería del Software por la Universidad Rey Juan Carlos en 2022. Trabaja aquí como investigador predoctoral centrado en problemas de embebido de grafos.

Sergio Cavero

Doctor en Inteligencia Artificial

Sergio Cavero nació en Madrid (España) el 24 de septiembre de 1997. Se graduó en Ingeniería del Software por la Universidad Politécnica de Madrid en 2019. Durante sus estudios de grado realizó una estancia en la Universidad de Bradford (Reino Unido). Además, fue galardonado en dos ocasiones con la Beca de Excelencia de la Comunidad de Madrid, así como con el premio al Mejor Proyecto Fin de Carrera. Posteriormente, realizó un Máster en Inteligencia Artificial en la misma universidad (UPM) obteniendo los premios al Mejor Expediente Académico (‘Premio José Cuena’) y al Mejor Trabajo Fin de Máster. Sus resultados académicos le permitieron ser beneficiario de una de las ‘Ayudas para la Formación de Profesorado Universitario (FPU)’, financiadas por el Gobierno español. Actualmente realiza su tesis doctoral en la Universidad Rey Juan Carlos, dirigida por los profesores Abraham Duarte y Eduardo G. Pardo. Sus principales intereses de investigación se centran en la interfaz entre las Ciencias de la Computación, la Inteligencia Artificial y la Investigación Operativa. La mayoría de sus publicaciones tratan sobre el desarrollo de procedimientos metaheurísticos para problemas de optimización modelados por grafos.