Originally posted by: JeffWhittle

Hi all,

I'm having trouble with a particular LP, which is one of many thousands of similar LPs generated by the same program.

The problem is that it returns status 3 (Infeasible), then when my program calls CPXrefineconflict it returns status 1719 (no conflict)!

I saved the LP to disk and then ran it with interactive CPLEX. The result was:

CPLEX> read Problem_3_032_02_00.sav
Warning:  File contains basis.  Basis is loaded.
Problem 'Problem_3_032_02_00.sav' read.
Read time =    0.00 sec.
CPLEX> opt

Iteration log . . .
Iteration:     1   Scaled dual infeas =   60850148309.012283
Iteration:  1150   Dual objective     =   39783103119.546188
Iteration:  1835   Dual objective     =   13972874171.763437
Iteration:  2184   Dual objective     =   13176141061.352478
Iteration:  2664   Dual objective     =   10179817905.323408
Iteration:  2783   Dual objective     =   10178917933.357168
Removing shift (1).

Dual simplex - Infeasible:  Objective = 1.0178887681e+010
Solution time =    0.51 sec.  Iterations = 2873 (1149)
Infeasible variable = x114943

CPLEX> conf
Using sensitivity filter.
Problem is feasible; no conflict available.
CPLEX>

I don't know what it means for an individual variable to be infeasible unless the lower and upper bounds are inconsistent, and I have verified that the bounds of x114943 are zero and one, as expected.

This LP has a starting basis. When I switch that off with "set adv 0", it again says it is infeasible, but then "conf" says it is feasible!

Does anyone know what is going on?

Thanks,

Jeff

Originally posted by: T_O

This might be due to numerical problems. You could try to set the numerical emphasis parameter (set em num y).

Best regards,
Thomas

Originally posted by: JeffWhittle

Thanks for replying Thomas.

I tried "set em num y", but it made no difference.

I have found that I can optimize this particular LP with barrier. However, that is not a suitable option for my application because I solve many thousands of very similar LPs, and using a starting basis from the previous LP causes a huge reduction in run time.

I'm no LP expert, just a serious user, but my understanding is that I can't use a starting basis with barrier.

Best regards,

Jeff

Originally posted by: T_O

What is the range of your coefficients?

Can you post your model?

Best regards,
Thomas

Originally posted by: JeffWhittle

I don't have a ready handle on the range of coefficients, but I can upload the model.

Here it is.

Jeff

Originally posted by: T_O

If i do dis prob stat, it says:

Variables            : Min LB: 0.0000000        Max UB: 1.000000
Objective nonzeros   : Min   : 0.003868787      Max   : 1.860161e+010
Linear constraints   :
  Nonzeros           : Min   : 5.518476e-008    Max   : 3.030411e+008
  RHS nonzeros       : Min   : 1.000000         Max   : 2.470683e+008

So there is a huge range of coefficients both in the objective and in the constraints. Maybe, you could reformulate your model so that your coefficients are in the same order of magnitude?

Best regards,
Thomas

Originally posted by: T_O

By the way, I now used an LP solver based on exact arithmetic to see whether your model is feasible or not. Using the CPLEX C API, I took the data obtained from your sav file and created GMP data out of it. So, I should not have done any rounding errors. The result: Your model is infeasible.

For the sake of completeness, I attached the exact farkas proof, but I guess, it won't help you.

Best regards,
Thomas

Originally posted by: JeffWhittle

Dear Thomas,

Thank you very much for your efforts and help.

I rarely use interactive CPLEX and was unaware of "dis prob stat". The min/max ratios are certainly very large and are likely the explanation for CPLEX getting confused between feasible and infeasible.

To fill you in, this LP was set up by a program that finds near-optimal long-term operating schedules for large mining complexes (www.whittleconsulting.com.au). Mathematically, the whole problem is at least non-convex quadratic MIP, and we get answers by a mixture of heuristics and many LPs.

Mining is very complicated and very varied, with all sorts of weird constraints. Runs can take anything from 10 minutes to a month, so that speed is important. I have worked on this application for about 12 years and there are now 43,000 lines of code in it even though it has no screens. It just reads a text file and writes two text files.

It would be difficult for me to trace the origin of particular very large or very small LP coefficients. All I can do is get the guys who set up the data for the application to try to avoid tiny quantities in the presence of large quantities. However, their job is already pretty difficult, so there are limits to what they can do when shovelling many megabytes of data.

In the long run we probably have to put up with this sort of thing happening occasionally.

Thank you again,

Jeff Whittle

Originally posted by: T_O

If I understand you correctly, the purpose of your LP is to help you solving your non-convex problem? So, which information do you want to obtain from the LP? The answer to the question whether it is infeasible or not? Or didn't you expect your model to become infeasible? Do you need Farkas infeasibility proofs? Do you need the optimal solution (if there is any)?

I'm asking this because I do not really know how to help you. If your model is only slightly infeasible, then this might also be due to inappropriate data. Do you need exact solutions (including the question whether the model is feasible or not)? Or only approximations?

Best regards,
Thomas

Originally posted by: JeffWhittle

Dear Thomas,

If we forget the quadratic part for the moment, the whole problem can in theory be formulated as an MIP. However, it would be so large as to defy solution in any reasonable time (perhaps with quantum computing?!). A lot of work is done in this field with MIP, but it is very limited in the size of problem that can be handled. We handle very big problems involving large mining complexes with many pits, processing plants and products.

My program finds good solutions by finding a large number of local maxima by hill climbing from random start points. The hill climbing is done by using LP to traverse a succession small regions where the constraints can be treated as linear rather than MIP.

The quadratic part is handled by an iterative layer below this, with a heuristic to encourage convergence.

This approach of finding local maxima only works because the distribution of peak values that occurs in mining is almost always flat near the top. That is, there are a lot of similar long-term schedules with NPVs that are very near the best. When the top ten NPVs in a run are within, say, 0.1%, we figure that that is good enough.

Coming back to individual LPs, There are some circumstances were infeasibilities are mathematically possible, and the program copes with these by backing off and trying a different approach.

There are other circumstances were we do not expect infeasibilities. Then I try to output details of the conflict for further investigation, which is what happened in this case. This particular LP is unimportant in itself. It only occurs for one mining project for about 10% of the random start points. We can crash on without it. I raised the query because I had never before seen CPLEX get confused between between feasibility and infeasibility.

"I'm asking this because I do not really know how to help you."

You have helped a lot. I don't have personal contact with LP experts.

Best regards,

Jeff

Originally posted by: T_O

Dear Jeff,

thank you for detailed information.

Due to the use of floating point arithmetic, such strange things can unfortunately happen. Infact, solvers can claim an LP to be both feasible and infeasible. There are many tolerances / parameters one can play with, but in general the only way to rule out such problems completely is to use exact arithmetic, whose runtime is by far inferior to floating point arithmetic.

In your case, I would try to change the feasibility tolerance (set sim tol feas). If I set it to 1e-4, your problem becomes feasible. With your coefficients being in the order of 1e-8, this might be inappropriate, but maybe, it is ok for you.

Best regards,
Thomas

Originally posted by: JeffWhittle

Dear Thomas,

"set sim tol feas" is interesting.

Because of the extraordinary variety of mining enterprises, I think that, in general, I'm safer sticking with CPLEX defaults. However, it will be quite easy for me to allow our people to change the tolerance if they are having unexpected infeasibility problems with a particular project.

I'll set that up.

Thanks,

Jeff

Originally posted by: T_O

Dear Jeff,

you should still keep in mind that even the CPLEX defaults might be inappropriate. A coefficient of about 1e-8 and a (default) tolerance of 1e-6 might be completely meaningless (depending on the bounds of the corresponding variable).

Another thing I forgot to mention is the command dis sol qual. In your case, you see that your basis has a condition number of about 1e11 and even worse sizes of dual values / reduced costs.

Best regards,
Thomas

Originally posted by: JeffWhittle

Dear Thomas,

There are three problems.

The fact that there is a coefficient of 1e-8 may be peculiar to this particular run on this particular mining enterprise. There is no indication that such extreme values are normal. If we tune CPLEX to suit this run, it probably won't suit other runs.

The second problem is that I know very little about the inner workings of LP. I'm a user, not an OR professional. For example, I don't know what the figures produced when I do "dis sol qual" mean. In a sense I don't want to know because I have enough on my plate looking after by far the most complex program I have written in my 51 years of technical programming.

The third problem is that the guys in the office know even less about LP than I do. They are users of the program, "ProberC", and don't want to know any more about how it works than they need to to run it. They have an unbelievablly complex data manipulation job which keeps them fully occupied. You wouldn't believe how messy mining data can be. It's no use complaining, that's all the miner has.

It's all a bit like objective programming. They run ProberC without bothering about its inner workings. ProberC does the same with CPLEX.

Of course neither can be entirely oblivious of inner workings, but we try to keep it to a minimum.

Best regards,

Jeff