# Mixed-Integer Bilinear Program (MIBLP) with linear constraints

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?

## 1 Answer

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).
• Thanks for the response. I have some question. 1- Is there any paper that explains in details why that linearization is true? 2- After linearization, we can find the exact optimal solution using MIP, right? Or it is an approximation because the linearization is not exact? 3- To me, it seems both the first and the third method you suggested should work. What is the difference? – m0_as Sep 5 '16 at 17:42
• I checked the transformation. I think it is exact. – m0_as Sep 5 '16 at 18:10
• The linearization is exact. The main issue is to avoid very large bounds as they can lead to numerical trouble. – Erwin Kalvelagen Sep 5 '16 at 18:37
• I didn't get. You mean if the continuous variable belongs to for example [0,1], it is okay? – m0_as Sep 5 '16 at 18:39
• Big M's of the form 1000000000 are notorious for giving bad results in MIP models. – Erwin Kalvelagen Sep 5 '16 at 18:40