I'm using CPLEX in C++ to solve a hub location problem, a MIP, and I've recently found a very precise set of inputs that CPLEX thinks is infeasible (i.e. CPXMIP_INFEASIBLE) even though the problem is certainly feasible. The problem appears to diverge in CPLEX during MIP Presolve; normally at that point the problem is reduced to a null problem, but not in the infeasible input set.
I've found that making almost any slight adjustment in the input data can toggle CPLEX's ability to find a solution. For instance, changing 250.242566 to 250.242567, or even just rounding each input value to the nearest integer, will give me a perfectly valid solution.
Softening the two slack constraints I have will also allow a solution, but these constraints should not be broken given the input data. The value of these constraint variables after a solution is approximately 0 but slightly negative, e.g. -0.7e-10. (This is suspect since the values should be above 0.)
What is going on? I'm clueless. I've tried adjusting some of the CPLEX variables relating to precision (i.e. CPX_PARAM_NUMERICALEMPHASIS, CPX_PARAM_EPOPT, CPX_PARAM_EPMRK, CPX_PARAM_EPRHS) but nothing has helped. The input data itself does not require too much precision--the smallest value in the inputs is 1.412 and the largest is 1520.984907.
I'd appreciate any advice or suggestions!
UPDATE:
I've noticed that the infeasible problem is diverging from the feasible problem during MIP's Presolve.
Checking CPXgetprestat for both problems, one notable difference I can see between the two problems is in the pcstat vector one variable cannot be aggregated out in the infeasible set (i.e. the value is 0 in the infeasible problem vs. -4 in the feasible problem).
Also, CPXgetprestat's ocstat and orstat vectors have one non-zero value each in the infeasible problem (the feasible problem has none because it has been reduced to a null problem), but I am unsure what to do with these two values. If orstat[0] == 7 and ocstat[0] == 1, does that mean that something is notable in the 7th row and the 1st variable of the problem before Presolve? How would I check this?
I have compared the output of CPXwriteprob in both problems and nothing is different other than the input value that I changed by 0.0001 to make the problem infeasible.
