Basis Factorization Packages
Basis Factorization Package (shortened as BFP) is a unique lp_solve feature. Considerable effort has been put in this new feature and we have big expectations for this. BFP is a generic interface model and users can develop their own implementations based on the provided templates. We are very interested in providing as many different BFPs as possible to the community.
Until version 4, lp_solve always used the product form of the inverse (etaPFI) to perform
its matrix pivot changes. However there are other methods
like LU decomposition. Each method has its advantages and disadvantages. Some
are faster/slower, other are numerical more/less stable. The speed and
stability of a solver depends considerably on the BFP. One model will be solved
better with one BFP and another with another BFP.
lp_solve version 5.1 has the etaPFI from lp_solve v3.2 built in as default engine. This BFP is versioned 1.0 to distinguish it from the newer external bfp_etaPFI version 2. In addition two other BFPs are included for both Windows and Linux: bfp_LUSOL.dll, bfp_etaPFI.dll for Windows and libbfp_LUSOL.so, libbfp_etaPFI.so for Linux. The standalone bfp_etaPFI is v2.0 and includes advanced column ordering using the COLAMD library, as well as better pivot management for stability. For complex models, however, the LU factorization approach is much better, and lp_solve now includes LUSOL as one of the most stable engines available anywhere. LUSOL was originally developed by Prof. Saunders at Stanford, and it has now been ported to C and enhanced by Kjell Eikland. It is expected that the LUSOL source will be made available.
These BFPs are not statically linked, but are dynamically loaded
when requested (except for the default etaPFI engine). It is even possible for people to write their own BFP.
Under Windows, a BFP is provided as DLL (bfp_*.dll), under UNIX/LINUX as a dynamic linked
Under Windows, the following search order is used:
Under Unix/Linux, following search order is used:
Under Unix/Linux it is standard that a library has the lib prefix and a .so postfix.
Under Windows there is no prefix and a .dll postfix.
lp_solve -bfp bfp_LUSOL input.lp
The latter makes sure that the BFP is searched in the current directory, especially for Unix/Linux.
Note that for the time being only bfp_etaPFI can be recompiled by you using the included source. A third BFP based on GLPK may be included later, but license issues must first be resolved. In the interim, you may experiment with the working sample BFP interface files for GLPK.
If you compile BFPs yourself, make sure that under Windows, you use __stdcall convention and use 8 byte alignments. This is needed for the BFPs to work correctly with the general distribution of lp_solve and also to make sharing BFPs as uncomplicated as possible.