Misinterpreting QCP as MIQCP

[Anjula-Antonis]

Hi,
I have written a code to find the duals of a QCP problem. But DOcplex is misinterpreting QCP as MIQCP. What could be the reasons for this?

Model: Con_acopf2

• number of variables: 6895
  • binary=0, integer=0, continuous=6895
• number of constraints: 4234
  • linear=4099, quadratic=135
• parameters: defaults
• objective: minimize
• problem type is: MIQCP
  Version identifier: 22.1.0.0 | 2022-03-09 | 1a383f8ce
  CPXPARAM_Read_DataCheck 1
  MIP Presolve eliminated 2 redundant SOS constraints.
  Tried aggregator 2 times.
  MIQCP Presolve eliminated 3522 rows and 6143 columns.
  MIQCP Presolve modified 4 coefficients.
  Aggregator did 297 substitutions.
  Reduced MIQCP has 630 rows, 862 columns, and 2037 nonzeros.
  Reduced MIQCP has 0 binaries, 0 generals, 76 SOSs, and 0 indicators.
  Reduced MIQCP has 133 quadratic constraints.
  Presolve time = 0.00 sec. (6.58 ticks)
  MIP emphasis: balance optimality and feasibility.
  MIP search method: dynamic search.
  Parallel mode: deterministic, using up to 4 threads.
  Root relaxation solution time = 0.00 sec. (3.36 ticks)

[PhilippeCouronne]

Hello,

The problem type you see is directly queried from CPLEX, this is not DOcplex code.
In your case, I see the model contains SOS sets. These constraints are implemented internally by CPLEX with
internal (hidden) binary variables. I guess this explains the MIQCP type.

[Anjula-Antonis]

Hi
Thank you for your reply. In CPLEX I found code to find dual for QCP. But I couldn't find a response for duals in MIQCP.
Do you have any suggestion on how to identify the SOS constraints in my DOcplex code?

[PhilippeCouronne]

SOS set constraints are added to the model via the Model.add_sos, Model.add_sos1 or Model.add_sos2 methods . I suggest you comment out calls to this model and check that the resulting model indeed has type QCP. However, I don't see how to implement such constraints without binary or integer variables...

[Anjula-Antonis]

I didn't add any constraint using this method. I used the model.add_constraint method for everything. I have nearly 500 constraints and I'm unable to identify which is SOS. Is there a way to identify?

[vberaudi]

Do you have piecewise? In cplex, PWL functions in the problem are internally reformulated with SOS2.

[Anjula-Antonis]

No I dont. It is a second order cone program, so it is convex

[Anjula-Antonis]

I just realised the issue. I have absolute value constraints which is formulated as SOS. Do you have any suggestions how to reformulate this?

[PhilippeCouronne]

Good news. Yes, some docplex constructs also generate sos "under the hood". What are you using the abs value for? the sos is there to implement that a variable Z is exactly equal to the absolute value of some X. So I would have to ideas: 1. if possible, reformulate the model with positive variables, eliminating the need for abs. if Z can take negative or positive values, introduce two positive values Z1 and Z2 such that Z = Z1 - Z2, Then minimize the sum Z1+Z2 as a secondary objective. 2. if absolute values are used in <= and <= constraints only then you don't need an exact absolute value. For example, abs(X) <= Z can be rewritten as X <= Z and --X <= Z Sorry for the trouble, this should be emphasized in the documentation. Le mar. 18 oct. 2022 à 13:49, Anjula-Antonis ***@***.***> a écrit :

…

I just realised the issue. I have absolute value constraints which is formulated as SOS. Do you have any suggestions how to reformulate this? — Reply to this email directly, view it on GitHub <#80 (comment)>, or unsubscribe <https://github.com/notifications/unsubscribe-auth/AJLZWW2INRTMS7BKRPTZUQDWD2FGFANCNFSM6AAAAAAREIVP3M> . You are receiving this because you commented.Message ID: ***@***.***>

[Anjula-Antonis]

Thank you so much for the suggestions.
My constraint is of the form x-y=z
and in the objective min(abs(Z)), where Z can take positive and negative values
I think your first suggestion might work, let me try

[PhilippeCouronne]

If X and Y are positive (which I guess) , then minimizing X+Y should minimize the absolute value of Z=X-Y. At the end of the solve, at most one of X,Y should be nonzero. And no need for an exact abs value...

[Anjula-Antonis]

Hi Philippe
Your suggestion worked, thank you so much. I am facing two more issues

1. I tried to optimize a model with 500 binary variables and docplex shows that model is infeasible. I tried the same on cvx and I was getting the optimal value. Is cplex incapable of handle large number of binary variables?
2. For another model, My optimal solution seems to be violating a constraint. Why is this happening? If the model is feasible shouldnt all the constraints be satisfied? Is this an issue with cplex?

[PhilippeCouronne]

Hello,
Sorry for the late answer, this is vacation time in France...

1. Commercial issues of Cplex have no limitations. Academic versions are limited both in number of variables and
2. number of constraints, but solve of large models fails with an explicit exception, so I assume this is not your case
3. This is abnormal and may be related to numerical instabilities.

To investigate infeasible models , I suggest you have a look at the Relaxer class, this is described in details in the infeasible notebook in the jupyter directory.
Another suggestion is to export the model in LP or SAV format, load it into the cplex.exe interpreter and enable the modeling assistant using

set read datacheck 2

With this mode cplex will report modeling issues which might cause numerical instabilities.

[Anjula-Antonis]

Hi
Thank you for your response. I looked into the issues you mentioned.
It appears my model has some ill-conditioning. I have big-M constraints with binary variables that is causing the issue. When I remove these constraints my problem is solving. And these solutions satisfy the big-M constraints when I tried computing on paper, so I expected to get the same solution after adding the constraints
Do you have advice on how to handle ill-conditioning due to big-M?
I saw some resources online that told to reduce the size of M, I tried that but my model is still infeasible

[PhilippeCouronne]

Big-M constraints can usually be modeled using Cplex indicator or equivalence constraints. An indicator constraint acts as a logical implication (one-way) from the value of a binary variable and the satisfaction of a linear constraint, without introducing artificial big-Ms. See the add_indicator family of methods on a Model.
This might have an impact on solve time (in an unpredictable direction), but should remove ill-conditiing, as reported by the modeling assistant.

However, I hope this is not the original model which started this discussion, because indicators only work with binary variables (and add some extra under the hood), so that Cplex works with a MIP problem.

[Anjula-Antonis]

Hi Philippe
Thanks a lot for all your advice. Sorry for the delayed response
I tried implementing everything you suggested as well as advice given on the links you share.
Right now my situation is, I have eliminated all the binary variables, big-M and indicator constraints.
My model is a simple SOCP program with continuous variables. My optimal solution is violating some of the linear constraints.
I have set lower bound as -cplex.infinity, and when I vary this lower bound the optimal solution is varying or becomes infeasible.
Do you have any suggestion on what might be the issue?

[Anjula-Antonis]

just a correction to my previous text. I am getting a sub-optimal solution.
when i'm checking the status code, i got '6'. problem not solved due to numeric difficulties.
when I test my code with a small data set, I am getting an optimal solution but with larger data sets it is not optimal
how to handle this issue

[PhilippeCouronne]

Hi,
From what you say, it looks like numerical instabilities. The first thing is to save a model file (in SAV format to avoid any risk of introducing extra numerical errors), load it into cplex interactive ith modeling assistant turned on.
(use set read datacheck 2 under cplex interactive).
From experience, the two major causes of numerical instabilities are

• first, constraint coefficients have orders of magnitude too different. The ratio between nonzero max and min should ideally be no more than 1e+6 (1e+8 at most). larger ratios can cause troubles.
• second, mixing different objectives with coefficients may also lead to sub-optimality. In such cases, using lexicographic objectives has proven effective. I could go into more details if needed.

Side idea: set mdl.quality_metrics = True to store quality metrics into the solve_details record. This will indicate various quality metrics of the solution (e.g. kappa)

If none of this helps, you might attach a LP file here and I'll take a look. Note that I'm not with IBM anymore so this would not be IBM support, .

[Anjula-Antonis]

Hi,
Thank you for your support.
I followed the tips you gave. My constraints don't have the issue with magnitudes and datacheck is not showing any issues with my model.
And I'm not mixing objectives, it is a cost minimization problem
lp file opf.zip

I suspect my feasibility set is small, could this be a reason for sub-optimal value?
I have attached an LP file here, could you please help me.

[PhilippeCouronne]

Hi
I have investigated your model, and so far I have not found any iasue with your coefficients, either in objective or constraint. I don't think this has to do with precision or ill-conditioning. However, I found a number of issues, which I cannot relate together yet:

• disabling presolve yields a different result (with presolve I get 41704, without it I get 41897. This is definitely not good.

• I tried narrowing the bounds of free variables to -1000, 1000 and then I get optimality at 42033 (which is worse than the free variable solution!)

• while investigating I did a wrong try setting all bounds to -1000, 1000 for all non-fixed variable; this was wrong as some variables are [-1,3] so I solved a different problem but then I get an error:
  CPLEX Error 5002: 'qc1' is not convex.

The first quadratic constraint is:

qc1: [ x119^2 + x1640^2 - x118*x158 ] <= 0

which, to me, is non convex due to the non-separable product. As such, Cplex refuses to solve it as non-convex QCPs are not supported. The fact that this non-convexity is detected hen widening the bounds seems suspicious to me.
However, I am not a Qp/QCP expert and I cannot go much further on this.

To summarize, your model has sound data and formulation. It exhibits at least one issue with presolve and another issue with the detection of non-convex QCPs. In the meantime you can try narrowing the bounds of free variables, though I don't understand what happens with convexity here.

I used the code below to change bounds and trigger the convexity error:

for dv in m80.iter_variables():
    #if dv.has_free_lb() and dv.has_free_ub():
    if dv.lb < dv.ub:
        dv.lb = -1e2
        dv.ub = 1e+2
        nb_fixed += 1

I also found the following support note on non-convex qcps, I did not try them,

I understand all that is a bit negative and I am very sorry for that.

[Anjula-Antonis]

Hi Philippe,
Thank you so much for your time and efforts.
I found the same issues with presolve and variable bounds and I was assumed it was due to some ill-conditioning in the model. But thanks for clarifying that my model and data looks sound.
qc1 is a SOCP constraint and cplex defines it like this. Like you said, I think qc1 is causing the issue.
I will see try to reformulate my model.

Thanks again for all your help. I really appreciate it