3
$\begingroup$

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?

$\endgroup$
3
$\begingroup$

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).
$\endgroup$
9
  • $\begingroup$ 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? $\endgroup$ – m0_as Sep 5 '16 at 17:42
  • $\begingroup$ I checked the transformation. I think it is exact. $\endgroup$ – m0_as Sep 5 '16 at 18:10
  • $\begingroup$ The linearization is exact. The main issue is to avoid very large bounds as they can lead to numerical trouble. $\endgroup$ – Erwin Kalvelagen Sep 5 '16 at 18:37
  • $\begingroup$ I didn't get. You mean if the continuous variable belongs to for example [0,1], it is okay? $\endgroup$ – m0_as Sep 5 '16 at 18:39
  • $\begingroup$ Big M's of the form 1000000000 are notorious for giving bad results in MIP models. $\endgroup$ – Erwin Kalvelagen Sep 5 '16 at 18:40

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.