Wednesday, August 11, 2010

Simplex vs barrier

For some models the barrier algorithm is very fast compared to the Simplex method (for an example see http://yetanothermathprogrammingconsultant.blogspot.com/2009/01/cplex-barrier-results.html). Here is an example of a medium sized but quite dense problem (107543 rows, 81160 columns, 878481 nonzeroes), for which the opposite holds. The primal and dual simplex method of the leading solvers are all doing very good, and the interior point algorithms have some troubles. In addition the variability between interior point timings is much more pronounced than the variability between Simplex times.

image

Timings are in seconds. The fastest barrier is 306 secs.

2 comments:

  1. Hmmmmm. Not much info about why that is the case. If the logs where available it might be possible to say why interior-point optimizer is slow. It could be that the interior point does not find some dense columns. [Most likely the problem should dualized and hence some dense rows are not detected.]

    It could also be that simplex just is doing exceptionally well in this case.

    If you put an MPS file anywhere let me know.

    ReplyDelete
  2. Sorry, I am not allowed to share the MPS files. There are both dense rows and columns. All the runs were with default settings.

    ReplyDelete