A Polyhedral Approach to the Multi-Layer Crossing Minimization Problem (Extended Abstract)

We study the multi-layer crossing minimization problem from a polyhedral point of view. After the introduction of an integer programming formulation of the multi-layer crossing minimization problem, we examine the 2-layer case and derive several classes of facets of the associated polytope. Preliminary computational results for 2- and 3-layer instances indicate, that the usage of the corresponding facet-defining inequalities in a branch-and-cut approach may only lead to a practically useful algorithm, if deeper polyhedral studies are conducted