13.5. VERTEX ORDERING 439
Exact Methods
Following from their work on the linear ordering and OLCM problems J¨unger et
al. derived an integer linear programming (ILP) formulation for MLCM [JLMO97]. As
in the one-layer case, quadratic terms analogous to those appearing in equation (13.7)
prevent formulation as a linear program. In this case, however, neither layer is fixed so
a different strategy is called for. The proposed solution is to introduce crossing variables,
c
ijkl
, denoting whether the edges (i, j) and (k, l) cross when i < j, k < l, i < k and j 6= l.
Using this notation along with boolean variables x
ij
to denote π
1
(i) < π
1
(j) and y
ij
to
denote π
2
(i) < π
2
(j) TLCM can be formulated as
minimize
X
(i,j),(k,l)∈E
c
ijkl
(13.14)
− c
ijkl
≤ y
jl
− x
ik
≤ c
ijkl
(i, ...