Originally posted by: satdene

Hello all, I attach a problem instance for which Cplex 11.0 generates an infeasible solution as optimal. For instance, when I try to learn the values of variables (by getValue() method) which are all supposed to be nonnegative, some of them are reported as negative. I asked this problem to many people including very experienced ones, and we could not reach a remedy or we could not find a simple bug in my code. This may be an interesting and challenging problem for Cplex experts as well. Any help would be very appreciated. Thanks in advance for your interest.
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

Before looking into the problem it would be interesting what negative the values are that you observe. Are these just small values (like -1e-9) that could be caused by bad numerics? Or are this really negative values like -1?
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: satdene

They are really negative values. For instance there is a -8162 value for one of the variables. Moreover, negative variables are not the only problem. Some of the constraints are also (seriously) violated. I also tried to run Cplex with numerical emphasis, end it ended up with a different but still infeasible solution. The solution it gave was around 32% better (which is impossible) than the objective value of the linear relaxation of the root node. Therefore, Cplex provides a really infeasible solution. Thx.
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

I confirmed that behavior here. Looks like a bug :-(
I will look into that and report back to you once I know what is going on. Thank you for reporting the problem.
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: satdene

Thank you very much. I am looking forward to for a solution. Good luck
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

I have not found the place in CPLEX were things go wrong but I observed two things. Maybe it is just bad numerics. Your coefficients range from 1e-5 to 8760 which may just be to wide a range for default settings.
When I set CPX_PARAM_EPRHS to 1e-9 ("set simplex tolerance feasibility" in the interactive) I do only get non-negative variables (apart from -0 which is just roundoff). Maybe this is already good enough for you? Note that I tested only with CPLEX 12.2 but it might be worth while to give that parameter setting a try with your version.
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

> dju358 wrote:
> Note that I tested only with CPLEX 12.2 but it might be worth while to give that parameter setting a try with your version.

I ran the model yesterday with 12.2 and default parameter settings (just to see if I could replicate the issue) and got a plausible looking solution (no negative variables, other than the occasional decimal dust). I also noticed the suspicious range of magnitudes. That said, you might need to test on 11.x to make sure scaling is really the culprit (as opposed to an, um, "feature" that got fixed in 12.x).

/Paul

Mathematicians are like Frenchmen: whenever you say something to them, they translate it into their own language, and at once it is something entirely different. (Goethe)
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

I was able to reproduce the problem with 12.2 here as well. Which is one more vote for "numerical trouble" as the same version gives very different results on different machines.
I will of course keep on investigating and post the final results here.
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: satdene

Daniel and Paul, thanks for your answers and interest. Unfortunately, setting CPX_PARAM_EPRHS to 1e-9 did not work in Cplex 11.0. Some negative variables became pozitive but some remained negative. Moreover, serious constraint violation persisted. My idea is that constraint violations are too high to be explained by some little feasibility tolerances. I will try to scale the parameter values in order to test whether the problem is due to bad scales. Thanks again, I will wait for your final results. Good luck.
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

Unfortunately, I don't have my CPLEX 11 docs handy. Does your version of CPLEX have the CPX_PARAM_NUMERICALEMPHASIS parameter? If so, try turning it on. (I'd still look for ways to improve the scaling, though.)

/Paul

Mathematicians are like Frenchmen: whenever you say something to them, they translate it into their own language, and at once it is something entirely different. (Goethe)
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: satdene

Unfortunately, I set numerical emphasis to "yes" but it didn't work. I also tried to set mip emhasis to feasibility and solved with a 3 hour time limitation. After 3 hours, it reports a feasible solution(all variables are nonnegative and constraints are not violated(at least the one which is seriously violated)). However, objective function value of the reported solution is almost equal to the objective value of linear relaxation of the problem(There is a 0.01% deviation between them). My problem is not totally unimodular, so I don't expect an integer solution from linear relaxation for such a big instance. Hence, I doubt about the solution after all these infeasibility issues. I will try with feasibility numerical emphasis on different instances as well and plan to share the difficulties and problems I face with you as well.
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: satdene

Hi again, the problem I attached before was solved accurately to optimality after setting mip emphasis to feasibility. However, for different instances of the same kind, the same problem arose again. I attach a new instance this time for which infeasible solution is reported as optimal by cplex although mip emphasis is set to feasibility.
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

I ran your problem with both numerical emphasis and integer feasibility emphasis set, but I only give it about five minutes, so CPLEX managed just the root node and a couple after that. It did find a feasible solution at the root, and the solution was indeed feasible (violations on the order of 10^-7).

It also told me that the worst basis condition number it encountered was about 1.8e10 (the LP relaxation's optimal solution has a condition number around 1e11, I think). CPLEX reported that, of the 80,000+ pivots it did, 83% produced "suspicious" bases and the other 17% produced "unstable" bases. There were no "stable" bases. So you've got a rather poorly conditioned problem, which may well have something to do with bad scaling (your constraint coefficients span eight orders of magnitude). I suggest you take a good look at whether you can reformulate your model to have better scaling.

/Paul

Mathematicians are like Frenchmen: whenever you say something to them, they translate it into their own language, and at once it is something entirely different. (Goethe)
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: satdene

Thanks Paul. Unfortunately, I have to deal with current parameter values. The problem is most probably due to bad scaling but it is still strange for Cplex to report such a ridicilous solution as optimal instead of providing a report about bad scaling or simply it can say that no feasible solution is found within the allowable time limit.
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

> satdene wrote:
> Thanks Paul. Unfortunately, I have to deal with current parameter values.

I don't know if this would help, but if you have constraint expressions that look like a'x + b'y where x and y are variable vectors, a and b are coefficient vectors, and the components of a are substantially bigger than the components of b (say, components of b are roughly unit magnitude), you could try rewriting the expression as z + b'y and adding a constraint z = a'x.

> The problem is most probably due to bad scaling but it is still strange for Cplex to report such a ridicilous solution as optimal instead of providing a report about bad scaling or simply it can say that no feasible solution is found within the allowable time limit.

Have you tried IloCplex.getStatus and IloCplex.getCplexStatus after solving the model? The CplexStatus value might at least tip you off that the solution is suspect.

/Paul

Mathematicians are like Frenchmen: whenever you say something to them, they translate it into their own language, and at once it is something entirely different. (Goethe)
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: satdene

Thanks again. I will try scaling method you wrote. Unfortunately, IloCplex.getStatus returns optimal although it is clearly infeasible.
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

What does getCplexStatus return? There's a value CPX_STAT_OPTIMAL_INFEAS for CPLEX status (slightly different but similar name in higher level APIs) that means the solution looks optimal to CPLEX in the scaled model but looks infeasible after unscaling. I would guess (hope) that's the CPLEX status when you get your infeasible solution.

/Paul

Mathematicians are like Frenchmen: whenever you say something to them, they translate it into their own language, and at once it is something entirely different. (Goethe)
#CPLEXOptimizers
#DecisionOptimization