# Bilinear programming vs Mixed integer linear programming performance comparison

I know that both bilinear programming and mixed integer linear programming are NP-hard. But is there a preference to have when choosing an approach to solve a problem that can be represented in both, especially when all variables must have binary values? For example:

Bilinear version: \begin{align} \max&\quad\sum_{\forall i} v_i\cdot x_i\\ \text{s.t.}&\quad\forall i,v,\ i\neq v,\ x_i\cdot x_v = 0\\ &\quad\forall i,\ x_i \leq 1\\ &\quad\forall i,\ x_i \geq 0. \end{align} Note that the problem forces the values to be binary without explicitly stating it.

MILP version: \begin{align} \max&\quad\sum_{\forall i} v_i\cdot x_i\\ \text{s.t.}&\quad\sum_{\forall i} x_i \leq 1\\ &\quad\forall i,\ x_i \in\{0,1\}. \end{align}

These two problems will lead to the same result, but which one is more appropriate and efficiently designed?

• Your question is interesting but your formulations are misleading. For all pair of nodes $i,v$, one variable must take value $0$? What problem are you trying to model ? Aug 14, 2021 at 19:18
• @Kuifje this simple problem is to choose one and one only element of the vector v, that is the maximum. This is a trivial example, to illustrate the general problem, not a real one Aug 14, 2021 at 19:20
• Ok got it ! I had not seen your last edit ! Aug 14, 2021 at 19:48

Constraining a variable to be binary could be expressed as a quadratic constraint: $$x\in\{0,1\} \iff x(1-x)=0$$
$$\{\mbox{MILP}\}\subset\{\mbox{non-convex QCQP}\}$$