An SDP relaxation for the cutwidth minimization problem

The Cutwidth Minimization Problem is a linear ordering problem on graphs, whose applications include natural language processing, information retrieval, graph drawing, and network migration scheduling. Finding the minimum cutwidth of a graph is an NP-hard problem, for which several heuristics and metaheuristics have been designed in order to compute upper bounds. Regarding lower bounds, integer linear programming models have been proposed, some with very good results on sparse graphs. However, even the best approaches see their performances decrease with the density and the size of the instances. In this talk, we introduce a new semidefinite relaxation for the Cutwidth Minimization Problem and investigate ways to efficiently strengthen it, using different sets of valid inequalities. We develop a cutting-plane algorithm based on these improved semidefinite relaxations, allowing us to significantly improve lower bounds for dense graphs. These methods can then be used for other challenging problems related to finding linear orderings minimizing other graph parameters, such as the pathwidth or the bandwidth.