Exact Approaches for the 2-Layer Crossing Minimization Problem: Novel MILP Formulations

I. Espejo Miranda, J. Peiró, M. Landete

In general terms, the Two-Layer Straight Line Crossing Minimization problem consists of ordering the nodes of a bipartite graph to minimize edge intersections. This NP-hard problem has significant applications in VLSI design, computational biology, and data mining. Due to its complexity, the literature has mostly focused on heuristic approaches. Regarding exact methods, the only existing integer linear programming model is based on a four-index formulation. We propose a novel compact MILP formulation that requires significantly fewer variables and constraints. Furthermore, through a structural analysis of the graph crossings, we propose new families of valid inequalities and preprocessing techniques. By enriching the models with these problem-specific insights, we improve the performance of exact methods, successfully solving medium-sized instances to optimality.

Palabras clave: crossing minimization, bipartite graphs, mixed-integer linear programming

GT GELOCA II: Optimization Models for Network Analysis and Classification
4 de septiembre de 2026  09:00
Aula B

V. Blanco, R. Gázquez, J. F. Ocaña-Rivas

S. Anglada, C. Galé, J. J. Salazar-González

V. Blanco, M. Martínez Antón, J. Puerto

F. Temprano Garcia, J. Puerto, S. Benati