Mixed-Integer Bilinear Program (MIBLP) with linear constraints

Question

Consider the problem of

\begin{align} \min_{x,y} \quad &a^Tx + b^Ty + x^TQy \\ &Ax \leq d \\ &Cy \leq e \\ &x_i \in \mathbb{R} \quad i \in \{1,2,\ldots,N\} \\ &y_i \in {\{0,1\}} \quad i \in \{1,2,\ldots,M\} \end{align} where $x = [x_1,x_2,\ldots,x_N]^T$ and $y = [y_1,y_2,\ldots,y_N]^T$. Is it possible to find optimum (local/global) solution to this Mixed-Integer Bilinear Program (MIBLP). Is there any solver for this type of problem?

Answer 1

Here are some hints:

1. Linearize $z_{i,j}=x_i y_j$ and you can solve this as a standard MIP (Mixed Integer Programming) problem.
2. If the problem is convex use a standard MIQP (Mixed Integer Quadratic Programming) solver (e.g. Cplex, Gurobi)
3. If the problem is non-convex use a global solver (Cplex has a global MIQP solver, some other global MINLP solvers are Baron, Couenne, Antigone).