Quadratic constraints in CPLEX
Robert Fourer
CPLEX only accepts quadratic constraints Q(x) <= a for which either (1) Q(x) is positive semi-definite, or (2) the constraint can be identified by CPLEX as representing a convex second-order cone (an SOCP constraint). So it would seem that you are in situation (2), but to be sure you should post to this group an example of the constraints in question. Also it may be helpful to show the definitions of the variables.
A rarer situation is that some variables are being fixed by AMPL's or CPLEX's presolve phase, and that what then remains of Q(x) is PSD or SOCP. As a start you can set "option show_stats 1;" to check that there are not a lot of variables being eliminated by AMPL.
CPLEX *does* solve mixed-integer SOCPs.
Bob Fourer
From: Luis J. Novoa [mailto:luisjo...@gmail.com]
Sent: Thursday, August 16, 2012 5:39 PM
To: 4...@ampl.com
Subject: RE: [AMPL 6069] Consults
Dr. Fourer, thank you very much for your reply. I have one important question regarding this topic. I have a constraint which is not convex of the form xTC x + ATx <= P, where in this case C is not positive semi-definite. Nonetheless, when I submit the problem to CPLEX, it can solve it (reports a solution). My concrete question is, why is this happening?, Doesn’t CPLEX require for the C matrix to be positive semi-definite, or is it related to the SOCP form?
One last thing, can CPLEX solve mixed integer SOCP?
Thank you so much for all the help,
Robert Fourer
Quadratic constraints involving binary variables are a special case, as there exists a transformation from binary quadratic to binary linear constraints -- even when the functions are not positive semi-definite. CPLEX can apply this transformation automatically in many cases, and that is probably what you are seeing.
You can check whether this is the situation, by setting "option relax_integrality 1;" and then trying to solve using CPLEX. This option makes the variables continuous rather than binary, and so then you should get an error message about the constraint function not being PSD.
Bob Fourer
From: Luis J. Novoa [mailto:luisjo...@gmail.com]
Sent: Sunday, August 19, 2012 3:51 PM
To: 4...@ampl.com
Subject: RE: [AMPL 6078] Quadratic constraints in CPLEX
Dr. Fourer, again, thank you very much for your reply. The original constraint formulation is something like (xTB x) <= (P - ATx)^2, where B is a Positive-Semidefinite matrix, P is a constant and A is a vector of nonnegative components. In AMPL:
var x{I,J} binary;
subject to C1{j in J, s in S}:
(sum{i in I, k in K} B[i,k,s]*x[i,j]*x[k,j]) <= ((P - sum{i in I} a[i,s]*x[i,j])^2);
My original question was based on the restatement of this expression when squaring the right hand side expression, as the resulting matrix in the resulting quadratic expression could be non Positive semidefinite.
Thanks again,