Originally posted by: RafaelMartinelli

Hello,

I have a MIQCP formulation, with only binary variables. Everything is linear, but one set of constraints like:

Σ_iΣ_j x_ix_j ≥ constant

These constraints are not convex. When running cplex, it seems the solver used is a Branch-and-Bound. I would like to know how does cplex deal with these constraints. Does it linearize them? Or does it try to convexify them? I need to know to argue about comparing with other methods.

Thank you,

Rafael

Hi

https://www.ibm.com/developerworks/community/forums/html/topic?id=d234cf8b-e13f-43ca-9a53-f9fb96b7709c&ps=25

could help you to turn your model into MIP

About MIQCP, some info at https://www.ibm.com/support/knowledgecenter/en/SSSA5P_12.7.0/ilog.odms.cplex.help/CPLEX/UsrMan/topics/discr_optim/mip_quadratic/03_introMIQCP.html

regards

Originally posted by: PierreBonami

Hello,

Short answer: we convexify them.

In the case where all variables in a quadratic form are binaries, we convexify it by perturbing the diagonal using the equality x*x = x (see for e.g.https://cedric.cnam.fr/fichiers/RC466.pdf ).

Best regards,

Pierre

Originally posted by: RafaelMartinelli

Hello Pierre,

Thanks for your reply. This is the information I was looking for. I read the paper and I know a bit about the methods, but still I have a couple of doubts:

1. Does cplex uses the simple convexification using \lambda.e or the SDP convexification?

2. Is there any difference whether it is doing the convexification of the objective function or a constraint? Or is the method used the same?

Best,

Rafael

Originally posted by: PierreBonami

Hi again Rafael,

1. We use the simple convexifictation.

2. The method we use is the same for constrains and the objective. But for MIQP there are more options. By default, we linearize if there are no quadratic constraints. As soon as there are quadratic constraints we only do convexification.

For MIQP, it can be controlled with the parameter qtolin:
https://www.ibm.com/support/knowledgecenter/en/SSSA5P_12.7.1/ilog.odms.cplex.help/CPLEX/Parameters/topics/QToLin.html

Best regards,

Pierre

Originally posted by: RafaelMartinelli

Pierre,

Thank you!

Best,

Rafael