3
$\begingroup$

Do CPLEX or Gurobi handle MIQPs with indefinite coefficient matrices?

The problem I am dealing with has quadratic terms in which one variable is binary and the other variable is continuous. The coefficient matrix of the quadratic form is far from positive semi-definite. Its entries are data-dependent. Thus, I have no control over the positive semi-definiteness.

Can CPLEX or Gurobi handle such models at all? Note that it's a MIQP with binary variables and continuous variables, not a QP.

Is there other software for such problems?

What is the state of the art, algorithmically?

$\endgroup$
6
$\begingroup$

A typical way to deal with this is to replace products $xy$ where $x$ is binary and $y$ continuous with a new variable $w$, and then add a constraint to ensure $w=0$ when $x=0$ and $w=y$ when $x=1$. This can be accomplished with $-M(1-x) \leq w-y \leq M(1-x)$, $-Mx \leq w \leq Mx$ where $M$ is a sufficiently large (but as small as possible) constant to ensure the feasible set does not change, i.e., an upper bound on the absolute value of any optimal $y$.

$\endgroup$
  • $\begingroup$ I don't have the reputation to vote this answer up. Someone should! $\endgroup$ – Bjoern Apr 2 '13 at 18:50
  • 1
    $\begingroup$ If you want to search for this construction in the literature, it is called a "big-M reformulation" (for obvious reasons). Johan has a nice discussion of this type of reformulation here with examples in his software package, YALMIP. $\endgroup$ – Geoff Oxberry Apr 2 '13 at 21:20
3
$\begingroup$

Note that CPLEX 12.6 and later includes functionality to solve general nonconvex QPs and MIQPs. However, for the special case of the product of a binary and continuous variables, the reformulation in the previous answer is likely to run faster. But, for nonconvex QPs with products of continuous variables in the objective, this type of reformulation no longer applies.

$\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.