[Cbc] Back to the future - yet another factorization

[John J Forrest]

When I first put the Coin Factorization code into CoinUtils for use in
Gomory cuts,  I knew it was not totally suitable as it had been written for
some research on parallel simplex.  I am now adding another factorization
which may be of some interest.  Basically what I have done is tear out the
factorization from OSL and modify it to work with Coin.  That was not as
simple as it sounds and there may still be bugs in it.  It is mainly
designed for use in Cbc where problems tend to be smaller.

The code is not aesthetically pleasing.  It was originally written in
Fortran in the 1980's and then converted to C by f2c in the 1990's.  It is
full of goto's and other horrible things.

On larger problems it is outperformed by the current factorization e.g.
solving ken-18 using the current factorization took 8.7 seconds, while
CoinOslFactorization took 20.7 seconds.  This is mainly due to the better
handling of hypersparsity by current code.  However for netlib it is
marginally slower 42.1 seconds as against 41.7 seconds.  However for
running the standard subset of 44 miplib problems (i.e. cbc -miplib) using
OslFactorization gives a time of 140.3 seconds as against 181.8 .

Unluckily when I tried on a different computer, it was slower so some of
this was luck.  Running on most of the Mittelman problems the Osl
factorization won more than it lost.  However doing some more tests I found
that the CXXDEFS -DCOIN_FAST_CODE makes a big difference as without it osl
version took 20 seconds longer (on 44 miplib problems) and I had not got
that set on the other computer.  -DCOIN_FAST_CODE assumes user is not
stupid and is not going to give cuts with duplicates, is not going
to ..... . But of course the code may fail unit tests so I am not sure it
can be default.

So I am putting it in Coin and I may be able to improve the code further.
See if it helps on your problems or if you find any bugs.

Also some non standard options seem to help (with and without osl) - you
may wish to try them -
a) allowing some cuts produced at root node to be kept and used anywhere if
they do anything.
just -gomory onglobal and -knapsack onglobal seem to work
b) fewer iterations in strong branching - hot(StartMaxIts) 10

John Forrest

To use from the standalone solver use -factorization osl while the function
call is ClpSimplex::solver->factorization()->forceOtherFactorization(3);

I will be interested in people's experience.

John Forrest
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://list.coin-or.org/pipermail/cbc/attachments/20090721/553f4041/attachment.html