Originally posted by: XinZhang

Hi,

I'm new to CPLEX. Recently I'm using CPLEX to solve a 0-1 ILP problems (minimizing). However, the optimal value of the objective function according to its solution is 30% greater than the one produced by a feasible solution I know. I did not change any default setting. Moreover, CPLEX claims it finds the exact optimal solution (not some suboptimal solution falling into the tolerance or gap).

To validate the solution I have is a feasible one, I use the solution as a warm start for CPLEX. This time CPLEX claims the solution I feed into is the optimal one, and generate a smaller objective function value.

The model file is around 1GB, so it is impossible for me to post it here. But I've attached the log file of two runs: one with my solution as warm start and another without.

I'm really confused. The document of ILP leaves me the impression that CPLEX will always try to give global optimal solution unless it finds a solution that is closed enough to the the optimal one or it runs out of certain resources. But I don't think my problem falls into any of this category.

I really appreciate your help,

Xin

It's possible that your model is somewhat numerically unstable, but we cannot ascertain that from the logs. Assuming that you are using the interactive optimizer (rather than one of the APIs), try the following:

1. Turn on numerical emphasis ('set emp num y') before solving the model, then solve it without a warm start and see if CPLEX gets the correct solution. If not ...
2. Turn on the collection of kappa (basis condition number) statistics ('set mip str kap 2'), reload the problem, solve without a warm start, and see if the kappa statistics indicate any unstable bases. (You can post the log output here if you have trouble understanding it.) If that does not signal anything useful ...
3. Try turning presolve off ('set pre pre n'), reload the problem, and solve without a warm start. If that works, you can experiment with turning off just one presolve switch at a time (for instance, leave presolve on but turn off dual reductions) until you find the culprit.

Paul

Originally posted by: XinZhang

Hi Paul,

Thanks very much for the detailed suggestions! From the result of 1 and 2, it seems not to be an issue of numerical stability. ( I might be wrong so I attached the log file of 1,2,3 here). But after turning off presolve, it indeed seems to give the right answer. Now I'm turning on/off different switches to see which part is wrong.

Thanks gain!

-Xin

Xin,

You are correct. Based on your new logs, it does not look like numerical instability (unless poor conditioning is somehow leading the presolver astray).

If you are using an older version of CPLEX and can upgrade to the current one (12.6), it would be a good idea to do so. I seem to recall one or two presolve bugs being fixed in recent years. If 12.6 is producing this error, it suggests a bug, which the IBM engineers will want to hunt down.

Good luck,

Paul

Originally posted by: XinZhang

Sure. I'll do that!

Thanks very much.

-Xin