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.