CPLEX error: CPLEX cannot handle QCP models with quadratic equality constraints.

[MatthiasW]

Hi everyone,

I'm having the following problem when I try to execute my MIQCP
problem: CPLEX always produces the following error:

CPLEX error: CPLEX cannot handle QCP models with quadratic equality
constraints.
Warning: Model status 13: Error no solution, Solver status 9: Error:
Setup failure.

However, by now, I removed all the potentially quadratic equality
constraints that I set up for my model. I did that by replacing the
equality constraints of the form

term_a = term_b

by two inequality constraints of the form

term_a <= term_b + epsilon
term_a >= term_b - epsilon

However, the error still pops up. Unfortunately, AIMMS does not tell
me which constraint in particular is causing the problem. So I'm
pretty clueless about what to do to resolve this...

Does anyone have experience with this kind of issues?


Thanks a lot in advance!
Best
Matthias

[MatthiasW]

I forgot to mention that my model is quadratic both in the constraints
and in the objective... maybe this is relevant for the problem with
CPLEX...

[MatthiasW]

I worked a little further on the problem.
One of my variables was obviously defined in a quadratic way. As
explained by Sergio in the following threat, this quadratioc
definition may cause problems for CPLEX:
http://groups.google.com/group/aimms/browse_thread/thread/5cfd8cfb67bbeba7/befaa58b823c95f0?lnk=gst&q=socp#befaa58b823c95f0

Thus, I removed the variable definition in my model and placed two
constraints of the upper bound / lower bound form (as presented above)
on this variable instead in order to force it into the desired values.
Now, a new error messages appears when I try to solve the model:

CPLEX: Q matrix is not positive semi-definite.

Warning: Model status 13: Error no solution, Solver status 9: Error:
Setup failure.

Does this make sense for anyone of you?
I would greatly appreciate your help.

Thanks a lot!
Matthias

[Marcel Hunting]

Hi,

CPLEX 12.2 and older can only handle models with quadratic constraints
if the model is convex (minimization) or concave (maximization).
Whether a quadratic constraint is convex or concave is equivalent to
whether the Q matrix is positive semi-definite or negative semi-
definite. A quadratic equality constraint can never be convex or
concave (also not if you split it up in a <= and >= constraint).

CPLEX 12.3 can handle some models with quadratic constraints that are
not convex or concave. You need to set the CPLEX option ‘Solution
Target’ to ‘Search for local optimum’. For non-convex/non-concave
models CPLEX 12.3 cannot guarantee to find a global optimum.

Marcel Hunting
AIMMS Software Developer

On Aug 29, 12:53 pm, MatthiasW <matz...@gmx.net> wrote:
> I worked a little further on the problem.
> One of my variables was obviously defined in a quadratic way. As
> explained by Sergio in the following threat, this quadratioc

> definition may cause problems for CPLEX:http://groups.google.com/group/aimms/browse_thread/thread/5cfd8cfb67b...

[MatthiasW]

Thanks for you help, Marcel!

Unfortunately, changing the option to ‘Search for local optimum’
didn't change a thing.
Do you have any suggestions as to how I could solve an non-convex/
concave model?

By the way, this is still the same model as the one you helped me with
last time. I managed to make the MINLP become a MIQCP, using a couple
of approximations. I thought this would make things easier... :/

Best
Matthias

[Marcel Hunting]

Hi,

For non-convex MIQCP you can use AOA, BARON or KNITRO. BARON returns a
global optimum while AOA and KNITRO only return a local optimum.

Marcel Hunting
AIMMS Software Developer

[Sergio Bruno]

Mathias,

Marcel is right. The kind of problem you could model with CPLEX 12.2
and before was only convex problems, with constraints that can be
represented by convex cones (it is always something like x^2 <= y1^2 +
y2^2 +... + yn^2). So, if you have this equality, either you have to
check if it is naturally obtained by the optimization procedure (I
mean, you model by one inequality and the model solution is the
equality), or if you are not lucky, the natural path would be to
migrate to one o the solvers he mentioned.

best,
Sergio

> --
> You received this message because you are subscribed to the Google Groups "AIMMS - The Modeling System" group.
> To post to this group, send email to ai...@googlegroups.com.
> To unsubscribe from this group, send email to aimms+un...@googlegroups.com.
> For more options, visit this group at http://groups.google.com/group/aimms?hl=en.
>
>

[MatthiasW]

Hi guys,

unfortunately, I still haven't resolved this problem.
The thing is, I changed my model in the meanwhile and now I definitely
haven't explicitly defined a single constraint that is non-linear. And
still AIMMS tells me that CPLEX can't handle QCP problems with
quadratic equality constraints. I just don't understand which
constraints this is referring to because as I said, I have removed my
quadratic constraints from the model.

Of course, AIMMS adds its own constraints for each variable, called
"variablename_definition". Each of these constraints just repeats the
variable definition. Of course, if I have a quadratic variable, then
this constraint will be quadratic, too. But you would experience this
with every quadratic problem and CPLEX is generally able to deal with
quadratic issues, so I don't see why these automatically generated
constraints should be the problem...
But maybe I'm wrong?


Does anybody have an idea on this?

Thanks a lot, best
Matthias

[Marcel Hunting]

Hi,

If you have a variable x with definition y^2 then this definition is
generated as a quadratic equality constraint (namely, x = y^2) which
CPLEX cannot handle.

Marcel Hunting
AIMMS Software Developer

[MatthiasW]

Hi Marcel,

yes, I know that such a constraint is generated by AIMMS, but if CPLEX
cannot handle such constraints, wouldn't this imply that CPLEX cannot
handle quadratic problems in general? As far as I know, this is not
the case. In AIMMS; CPLEX is even configured as the standard solver
for all kinds of quadratic problems.

When I speak of quadratic, I mean problems of the form
x'Ax = b
i.e. I mean problems where two decision variables can be linked
multiplicatively in one or more terms of the model formulation.

Now, when you say thaat CPLEX cannot handle constraints of the form x
= y^2, do you mean, that CPLEX only does not work if the problem
contains terms in which a decision variable y is multiplied with
itself?
That is, do you mean that CPLEX could handle a term of the form x =
y*z, but cannot handle a term of the form x = y*y?

Thanks for your help, best
Matthias

> > Matthias- Zitierten Text ausblenden -
>
> - Zitierten Text anzeigen -

[Marcel Hunting]

Hi Matthias,

CPLEX requires that all quadratic constraints each define a convex
region. To make sure of convexity, CPLEX requires that each Q matrix
must be positive semi-definite (PSD) or that the constraint must be in
the form of a second order cone. That is, each quadratic constraint
must have one of the following forms:

x'Qx <= a'u + b
x'Qx <= y*y
x'Qx <= y*z

where x and u are vectors of variables, and y and z are scalar
variables. The quadratic matrix Q has to be PSD. (In case of a >=
constraint the Q matrix has to be negative semi-definite.)

Quadratic equality constraints are never convex and therefore cannot
be handled by CPLEX. So both x = y*y and x = y*z cannot be handled.

See also: http://www.ieor.berkeley.edu/Labs/ilog_docs/html/usrcplex/solveQCP2.html
.

AIMMS itself does not check whether the quadratic problem is convex or
not before sending it to the solver. If the quadratic problem is non-
convex then AIMMS will send it to CPLEX (if it is the default solver)
and CPLEX might return with an error because it cannot handle it.

Best regards,

Marcel Hunting
AIMMS Software Developer

> > - Zitierten Text anzeigen -- Hide quoted text -
>
> - Show quoted text -

[MatthiasW]

Dear Marcel,

thanks a lot for your reply.
Your explanation makes perfect sense for me. The only thing I don't
get is the following:

If I define a simple quadratic problem with say linear constraints,
then my objective function is:

y = f(x) = x'Qx

and my linear constraints are of the form

Ax <= b
Ex = d


Now, actually CPLEX should be able to handle this, because the
constraints are completely linear. It is a simple QP, and CPLEX is
even configured as the standard solver for simple QPs in AIMMS.
However, given that AIMMS always generates an additional constraint
repeating the definition of the objective variable y, we get in
trouble because this "artificial" constraint necessarily is a
quadratic equality constraint:

y = x'Qx

This would imply that CPLEX is unable to solve ANY quadratic problem
just because the quadratic objective function (which is necessarily a
quadratic equality) is forced into an additional constraint.
So, given this, if CPLEX is able to solve simple QPs, how do you model
them so that CPLEX accepts them?


Sorry for still not getting it, best
Matthias

> > - Show quoted text -- Zitierten Text ausblenden -

[Marcel Hunting]

Hi Matthias,

The constraint or variable definition defining the objective is
treated in a different way than the “real” quadratic constraints.
Probably not clear but in my previous reply I assumed that the
objective constraint is not part of the quadratic constraints.

For the objective the constraint can be an equality. So if you have an
objective defining constraint

y = x'Qx

where y is the objective variable then this can be handled by CPLEX if
Q is PSD and the objective direction is minimizing or if Q is NSD and
the objective direction is maximizing.

(In such case AIMMS will only pass x’Qx as the objective to CPLEX and
not pass the variable y.)

Best regards,

Marcel Hunting
AIMMS Software Developer