Originally posted by: James82

Hi all

So firstly I should say I'm quite new to linear/mixed integer optimization so please bear with me.

My question is this, I have a curious situation where the root relaxation of a MIP (where the integers are binaries) that I'm working with solves fine as an RMIP with barrier and then primal simplex crossover but generally has more problems when solving as the actual root of the MIP. It seems to be due to the MIP presolve which reduces the number of binaries from 7 to 6 before barrier begins whereas the LP presolve does not. Barrier then seems unable to converge, i.e. the primal and dual objectives do not converge (typically there is a sizable difference, e.g. primal = 5.2E4, dual = 6.2E4, when barrier terminates and it gets worse because the crossover solution is usually drawn from many iterations previous), and the crossover step then typically has much larger solve times (relative to the RMIP). This does not appear to be a problem with the RMIP - barrier is able to converge normally.

Evidently the MIP presolve is determining that one of the binaries can be assigned straight away but I wonder why this then goes on to cause barrier a problem? I imagine it may be specific to this model but thought I'd ask just in case anyone had an idea or two.

Also, I'm a bit confused why barrier opts to iterate as close to convergence as it can and then, if it fails to meet the tolerance, terminates and selects primal/dual objectives from many iterations ago for crossover. Why does this happen?

As a side note, I've tried the same cplex options with a smaller version of the model (same formulation just run over fewer model time steps) and barrier is able to converge in the root relaxation. Oh and I'm using CPLEX 12.5.1 called by GAMS.

Many Thanks

James

Welcome to MIP models, where the dominant axiom is that some days you get the bear and some days the bear gets you.

I'm just guessing, but it's possible that fixing one of the integer variables, coupled with the information that the model is a MIP, may result in different cuts being added at the root than in the RMIP case, and perhaps one or more of the cuts in the MIP version create some sort of numerical misadventure take the barrier solver in a new and funkier direction.

Have you tried setting parameter CPX_PARAM_NUMERICALEMPHASIS? Or tightening some tolerances? Can you load your problem into the CPLEX interactive optimizer, issue 'display problem stats' there and show us the output? That could give a hint about whether your model looks like it has bad numerics. Or could you even attach your two models here?

Originally posted by: James82

Hi Paul and Daniel

Thank you for your replies. I've moved on to a related issue at the moment. From my knowledge of the data going into the problem and the conditioning numbers I have seen over my time working with this model (minimum ~ 10^10 but usual 10^12 and sometimes more), I'm pretty sure the issue lies with the numerics (many orders of magnitude between the smallest and largest coefficients). I guess this means that fairly subtle alterations to the model (e.g. differences between MIP and LP presolve) can result in significantly different outcomes (i.e. barrier solving or not).

Regarding the CPLEX interactive optimizer, I don't have it at the moment but will probably look to obtain it through the Academic Initiative since I'm a researcher at a University.

As a final, vaguely related question, does anyone know if there is a way to make CPLEX use all available (i.e. idle) threads when solving a MIP subproblem using barrier. Specifically, at the moment I have threads=6 but looking in the clone logs I see that at the start of the tree some threads are sitting idle waiting for others to finish. It would be nice to enable some form of dynamic allocation such that if CPLEX wanted to (and idle threads were available) it could use more than 1 thread for a particular subproblem.

Thanks

For technical reasons, CPLEX cannot use those idle threads in the beginning of the tree search to run multi-threaded barrier. However, with not too much coding effort one can implement a very similar behavior. This involves using an undocumented parameter, so I won't post that here. If you are interested please drop a message to daniel(dot)junglas(at)de(dot)ibm(dot)com.