Originally posted by: James82

Hi

I have been comparing MIP root solution times between barrier only (startalg=4 via GAMS or rootalg=4) and concurrent (the default) for the problem I am working with (technically a smaller version of the full problem -> reduced along the time axis).

Barrier always seems to solve the model in the shortest time, particularly as I increase its size so I was experimenting with moving from concurrent to just barrier alone. However, as you will see in the attached logs (note for the concurrent solve I copied and pasted the presolve log together with the clone log), I find that the concurrent version of barrier solves much faster than barrier on its own -> 93 secs vs 297 secs. The logs show the number of nonzeros in the lower triangle are the same and the barrier only solve even has a lower FP ops to factor (by ~10%).

So:

1) Any idea why there is a factor of 3 difference in the solution time? I note that both have parallelmode=1.

2) Are there any CPLEX hidden parameters that allow concurrent to be used for the node solves?

Thanks!

While the number of non-zeros in the lower triangle of A*A' is the same in both cases, the statistics of the Cholesky factors are not. That may indicate that eventually the two barrier runs are solving different things (or at least in a different way). Would you be able to share the model? We then could figure out what exactly is going on here. If you don't want to share in public, please feel free to share with daniel(dot)junglas(at)de(dot)ibm(dot)com.

Originally posted by: James82

Hi Daniel

Thank you for getting back to me. I attach the model.

And yes indeed, the statistics are different - hope you can shed some light on what is going on here.

Thanks again.

Unfortunately, I cannot reproduce your problem here. In both parameter settings, solving the root relaxation with barrier takes a few hundreds of seconds here. I suspect that part of the problem/failure to reproduce is this:

CPLEX> display problem statistics

Problem name         : highres.lp
Objective sense      : Minimize
Variables            :  250329  [Nneg: 224082,  Fix: 291,  Box: 11,
                                 Free: 1,  General Integer: 25944]
Objective nonzeros   :   54046
Linear constraints   :  234422  [Less: 114131,  Greater: 46440,  Equal: 73851]
  Nonzeros           :  810607
  RHS nonzeros       :    7619

Variables            : Min LB: 0.000000         Max UB: 12700.00       
Objective nonzeros   : Min   : 0.001000000      Max   : 4000.000       
Linear constraints   :
  Nonzeros           : Min   : 4.420000e-08     Max   : 500.0000       
  RHS nonzeros       : Min   : 0.08000000       Max   : 463720.0

The non-zeros in your matrix range from 1e-8 through 1e2, i.e., 10 orders of magnitude. This is asking for numerical trouble. Any chance to narrow this range?

These tiny numbers may also mean that the LP file might not be an exact representation of your model, can you export to a SAV file instead?

What version of CPLEX do you use?

Originally posted by: James82

Hi Daniel

Thanks for getting back to me again.

1) So I've made a minor change to the model and now get much improved numerics (see bottom of this post).

2) I attach a SAV file of the revised model.

3) I also attach two new logs (both main log and clone log) straight from CPLEX 12.8 using the command line interface (I believe that is called the interactive optimiser?). Normally I run the model from GAMS (using CPLEX 12.8 as well) but I thought this route would be good to test and get one layer of possible issues out of the way. The new logs show the same thing as in my first post - basically concurrent barrier is 3 times faster than barrier only.

One critical point I want to mention is that here I'm using parallelmode=-1 so that the concurrent optimiser stops as soon as barrier has solved. Without that option the concurrent optimiser will run for longer even after barrier has solved the model according to the clone logs. Regardless of parallelmode, one should compare the clone log concurrent barrier run to the main log barrier only to see the different in solution time.

So I don't think its the numerics of the model that cause the issue. Also, I note that this is a very small version of the full problem (time axis is hourly for 2 weeks, full problem is hourly for 1 year) and, as far as I can tell, this factor of 3 scaling continues as I start running larger and larger versions of the problem (tested up to hourly for 6 months). As such, it can have a very big impact on solution times.

Many thanks!

New stats:

Display which problem characteristic: stats
Problem name         : highres.sav
Objective sense      : Minimize
Variables            :  250329  [Nneg: 224082,  Fix: 291,  Box: 11,
                                 Free: 1,  General Integer: 25944]
Objective nonzeros   :   54046
Linear constraints   :  234422  [Less: 114131,  Greater: 46440,  Equal: 73851]
  Nonzeros           :  810607
  RHS nonzeros       :    7619

Variables            : Min LB: 0.0000000        Max UB: 12700.00
Objective nonzeros   : Min   : 0.001000000      Max   : 4000.000
Linear constraints   :
  Nonzeros           : Min   : 0.001000000      Max   : 500.0000
  RHS nonzeros       : Min   : 26.70000         Max   : 463720.0

Originally posted by: James82

Hi Daniel

I imagine you are very busy but I wondered if there was any update on this?

I continue to see this issue appearing with different sizes of my problem. To me it almost seems like a bug in CPLEX that concurrent barrier solves so much faster than barrier on its own.

Thanks!

I finally got to the bottom of that.

The problem is that CPLEX treats dense columns differently, depending on whether barrier is invoked from concurrentopt or invoked directly. That is why the number of non-zeros in the lower triangle are the same but the Cholesky factors are very different.

This different is not intended and I would even call it a (performance) bug. I have filed a bug report with respect to this.

Unfortunately, there is nothing you can do about this, no workaround. So you probably have to waste a few threads on simplex for concurrentopt although you already know that barrier will win there.

Originally posted by: James82

Hi Daniel

Thank you for getting back to me on this. Really good to hear you got to the bottom of this issue.

Regarding a work around, it is of course fine to run concurrent on the root node, as you suggest it just wastes a few threads on simplex which isn't a problem. Where it is a problem is that my solution "strategy" for solving this model involves using barrier to solve the other nodes (subalg=4, for some reason this also applies to root node resolves). I do this because my problem is degenerate/has numerical challenges that mean primal/dual simplex struggle as I scale up the model size despite having a barrier + crossover solution to warm start with from the root solve.

The solutions proceed like (log attached):

1) Use concurrent to solve the root node, barrier always wins.

2) Turn heuristics up (heurfreq=5).

3) Use barrier as the node algorithm (subalg=4). CPLEX then resolves the root node (using barrier) and the node heuristic always (as far as I have seen) finds a good solution (within my MIP gap of 1%) within just one more resolve.

I suspect the barrier run in 3) is suffering from the same problem you have identified because it is much much slower (almost an order of magnitude) than the root node solve - is there a way (e.g. a hidden parameter) to get concurrent to solve the nodes (including the root node resolves)?

That would be great.

Thanks!

I am really sorry. I looked hard through the source code to find a way to use concurrent for the nodes or to avoid this issue but did not find any. The best option I see at the moment is to wait for the next CPLEX release that fixes this problem

Originally posted by: James82

Hi Daniel

Thanks for looking into it and getting back to me. While it is disappointing it is good to know why the performance differs so much and that it isn't something I am doing.

The slightly bizarre thing here is that if I solve the relaxed MIP (using RMIP in GAMS) and compare barrier only with concurrent I get much closer solve times (in fact barrier only does a bit better with 100 secs vs 125 secs for a small version of my problem). So I presume this indicates the problem I'm seeing is something to do with how concurrent barrier and the MIP solving code in CPLEX interact.

Just out of interest, any idea when the next CPLEX release will be? It is worth noting that most large energy/power systems models (of which highRES is one of the latter) are primal/dual simplex degenerate and so barrier is often used. Therefore, for MIP models this would be an important fix.

Thanks again.

I confirm that this issue relates only to MIP.

Version 12.9 is out, see here. The issue should be fixed in this version.

Thanks for your feedback.

The next release is planned for the first quarter of 2019.