search

IBMDecisionOptimization / docplex-examples

These samples demonstrate how to use the DOcplex library to model and solve optimization problems.
https://ibmdecisionoptimization.github.io/
Apache License 2.0
396 stars 228 forks source link

No solution to convex QCP when an extra, irrelevant binary variable is added #82

Closed AndrasKiss closed 1 year ago

AndrasKiss commented 1 year ago

Hi, I've ran into a puzzling issue with cplex / docplex. I've built a convex QCP using docplex, which CPLEX can solve. But when I rebuild the problem from scratch and add a single, mathematically inconsequential binary variable, the CPLEX solver responds with "integer infeasible". (The same issue happens also if the binary variable plays a meaningful role in the problem.) Furthermore, when I linearize all the quadratic constraints with a fairly tight polyhedral relaxation technique (thus turning the MIQCP into an MILP), CPLEX can again solve the problem.

As a check, I've tried all of the above with Gurobi, too. It has solved the exact same problems without any glitches.

You can reproduce the issue from the two MPS model files at this gist. (It also shows up when using the cplex API only.)

Any ideas?

PhilippeCouronne commented 1 year ago

Hello,

I reproduce the issue under cplex interactive optimizer (20.1, windows) only, so it is clearly not a docplex issue but a cplex one. The xtra binary issue causes infeasi ility as soon as it appears in the objective, whether its coefficient is zero or not. If I remove it from the objective it solves fine. This is indeed very strange.

vberaudi commented 1 year ago

The model is feasible if the presolve is off. But interestingly, if you write the model to its presolve version, and solve this presolved version, then presolved model is feasible.

AndrasKiss commented 1 year ago

The MIQCP presolve does some strange things, indeed. E.g.: it leaves 3 fewer quadratic constraints in the problem than the QCP presolve.

When I turn off presolve (for a problem with meaningful binary variables), the solver gives back "integer optimal, tolerances", which is not as ideal as "integer optimal", but still much better than no solution at all. And the result is identical to what Gurobi calculates. Good enough.

Thanks for the quick help, guys!