I would like to formulate the graph crossing minimization problem as a MI(N)LP (it's ok if it is non linear) : given a graph $G(V,E)$, what is the minimum number of edge crossings in any drawing of $G$?
A natural way of starting is to define $(x_v,y_v) \in \mathbb{R}^2$ variables for coordinates of each vertex $v$, and a binary variable $\delta_{e,f} \in \{0,1\}$ which takes value $1$ if edges $e$ and $f$ cross one another. With such variables, the problem is to minimize $\sum_{(e,f)\in E}\delta_{e,f}$ subject to "crossing constraints", where crossing constraints enforce $$ e,f \quad \text{cross} \implies \delta_{e,f}=1 $$
How can I formulate this logical constraint ? (Other formulations with different variables are accepted).
