Bilinear programming vs Mixed integer linear programming performance comparison

Question

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?

Answer 1

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

This is often mentioned in non-convex QCQP articles to present non-convex QCQP is a somehow more general problem class.

$$ \{\mbox{MILP}\}\subset\{\mbox{non-convex QCQP}\} $$

There are some off-the-shelf non-convex QCQP (global) solvers, like gurobi. But their performance are generally poor. (I guess the reason might be that the problem class is TOO general, making it hard to solve, and less applied, making solver companies paying less attention to it.)

So in theory every MILP could be reformulated as a QCQP (maybe in different ways), and solved with a QCQP solver, but due to the different ways the solvers utilize the problem structure, and the efficiency difference, there is no benefit to do that. So just stick to MILP.

PS. Your example model could be relaxed to continuous, and the solution should automatically be integer.