QCQP model doomed infeasible in presolve, however it is not

Hi Jonas,

how did you create that .lp file, as I am struggling to reproduce the infeasibility? It seems like the .lp-file includes 362381 rows while your log shows 360816 rows. Also an mps file might be better to ensure that the column ordering is kept intact.

Otherwise the presolve seems to point to row AVVAVV2Mode6AFRRVerticalUpCondensing2_23, although of course we may have already made changes to the row at this point, but still it might point to issues with the variables in that row. Also it might be worth trying to adjust the feasibility and matrix tolerances and see if that can help, as the solutions I am getting with barrier tend to have some slight infeasibilities where there can be differences between presolve and the LP solvers themselves.

Best,

Tristan

Hi Tristan,

Thank you for a quick reply. Please, find the mps-fil attached.

Neither can I reproduce the infeasibility using the lp. We are using the .Net api, and original this problem is formulated as a MIP and solved, then the integer variables are fixed using upper bound = lower bound, the quadratic terms are added the objective functions and quadratic constraints added to the model and the model is solved using the XPRBprob.lpOptimise.

You are right, that there is a difference between the lp and the log, however I ensure they are from the same state of the model, the exportProb is called just before lpOptimise. Besides the number of rows, the MIP entities numbers are different. Maybe the state of the model in memory in the .Net differs is not as the lp dumped?

I cannot find anything wrong with AVVAVV2Mode6AFRRVerticalUpCondensing2_23, unless it just picks one row out of many.

Let me know if you need anything else.

Thanks!

Hi Jonas,

Could you please try adding the code below just before your call to lpOptimize? This should export the actual problem solved by the Optimizer. If you send us the resulting MPS file, hopefully we can then reproduce the infeasibility.

prob.loadMat();
prob.getXPRSprob().WriteProb("prob.mps");

Hi Jonas,

and if you want to try something on your side while waiting for us to look into the issue in presolve: We do have the refinops functionality https://www.fico.com/fico-xpress-optimization/docs/latest/solver/optimizer/HTML/REFINEOPS.html which is meant for this usecase of optimizing a mixed-integer problem, fixing integer variables, and then reoptimizing. Of course it cannot predict the quadratics that you would add for the second solve, but if the problem is caused by some of the linear constraints becoming slightly infeasible after performing your fixings (where there can be slight differences with regards to the tolerances used by the LP solver and in presolve), then this might help. You can either set the ninth bit (so set REFINEOPS to 17 + 2^9 = 531) if you want the initial branch-and-bound search to completely reject solutions that would become infeasible after fixing the integers and resolving the problem from scratch as an LP, or you can set the tenth bit (so set it to 1041) if you want it to attempt to clean up the solution, but not reject solutions outright due to this.

Hi Chris and Tristan,

The .mps-file is already attached (in reply), however I did not call loadMat before writing the prob - is that important?

I'll look into the refineops func.

Cheers,

Jonas

loadMat ensures that the latest changes from BCL have been loaded into Optimizer. Did you export the MPS file using prob.exportProb() or using prob.getXPRSprob().WriteProb()? If the second, then BCL may not have fully synchronised the problem with the Optimizer before writing the problem.

If you cannot reproduce the infeasibility with an MPS file produced by calling loadMat and then WriteProb, then another option is to send us a save file, which captures the entire Optimizer state:

prob.loadMat();
prob.getXPRSprob().SaveAs("prob.svf");

Hi Chris,

I'm using exportProb, however added the loadMat before calling exportProb just to be sure.

I have attached the .mps and .svf files. I've tried to do a IIS on the .mps file but it just stalls at "Applying the Deletion Filter".

Also, I have attached our code wrapping the XPRESS solver so you can see how we interact with XPRBprob and XPRSprob.

Just to add som context: The flow is not new and works in general, however we sometimes see this issue when solving the QCQP. We have an old version of Cplex also implemented for this flow, and it does not fail in the QCQP like the XPRESS Optimizer.

Could only attach one file at time. Here the .svf file.

The .mps is the same as already received so I will not attach again

Thanks Jonas,

from the save file I managed to reproduce the issue. The reason for the discrepancy between presolve on and off indeed seems to be tolerances. When I disable presolve, barrier is also struggling to find a feasible solution and the one that is returned in the end does have infeasibilities in the 10^-5 range, and if I weaken the feasibility tolerance to 10^-4 then also presolve no longer seems to declare the problem infeasible. I will see if I can spot the exact reason for infeasibility in this case. From what you explained, you also add quadratic constraints to the problem after fixing the integers. Is it guaranteed from an application point of view that the problem should remain feasible at this point, or could it be that these lead to a situation where the constraints can no longer be satisfied exactly from the previous fixings?

Hi Jonas,

first of all about the difference between exportProb and writeProb, by default exportProb will use a relatively low precision to make the file more readable (see https://www.fico.com/fico-xpress-optimization/docs/latest/bcl/bcl.net/HTML/html/4ccfa469-ec31-cf8f-8f0e-9ebe302a9c91.htm ), while writeProb will by default write with full precision to make things reproduceable, and in this case I can see that some of the coefficients in the problem created by exportprob have been cut off compared to the numbers I get after restoring the save-file, which for an infeasibility in the 10^-5 range can of course make a difference.

In fact looking at the infeasibility, I think it might have a similar reason. When I look at AVVAVV2Mode6FCRNGenericUpDownCondensing1_18, which on my side is the row we blame for infeasibility in the end, we start by fixing AVVAVV2Mode6Condensing_18 to -330.87860827049457, which is strikingly similar to the - 330.8786 coefficient in front of AVVAVV2Mode6FCRNGenericUpDownPPRPoint3Alpha_18, and after fixing two more variables, including the latter, that row ends up with a violation in the 10^-6 range, which very much matches the difference between those two numbers. And if I replace - 330.8786 by the full number in the original model, then this infeasibility seems to go away (even though the problem is still declared infeasible due to another row, but given that there are a number of rows with almost identical structure, that doesn't seem too surprising). Without knowing about your application, it looks to me very much like that - 330.8786 would be the result of a rounding operation, while other rows might still implicitly enforce the more accurate number?

If that is indeed the case, I would suggest either avoiding these roundings when preparing the problem, or otherwise to relax the feasibility tolerance to a value that doesn't require higher precision than the input data provides, as the 10^-4 with which the model still solves nicely even with presolve enabled seems to match the roundoff error in those numbers. Given these differences, I assume what happens is that the original model with integralities is still too complex for us to figure out these infeasibilities and then in the LP solver we leave a little bit more wiggle-room and end up with a solution that is not quite as accurate as we would want. But after fixing those integers, the problem simplifies and we can figure out these discrepancies in presolve and then apply the tolerances with a bit more force and therefore end up declaring the problem infeasible.