7
$\begingroup$

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?

$\endgroup$
3
  • $\begingroup$ 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 ? $\endgroup$
    – Kuifje
    Aug 14 at 19:18
  • $\begingroup$ @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 $\endgroup$
    – TUI lover
    Aug 14 at 19:20
  • 1
    $\begingroup$ Ok got it ! I had not seen your last edit ! $\endgroup$
    – Kuifje
    Aug 14 at 19:48
8
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.