[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: [Help-glpk] Patches to improve pseudocost initialisatiion speed
From: |
Chris Matrakidis |
Subject: |
Re: [Help-glpk] Patches to improve pseudocost initialisatiion speed |
Date: |
Sat, 14 Jan 2017 20:53:55 +0200 |
Hi Andrew,
Leaving aside the issue of the API for the time being, I did some
additional experiments in this area.
> To resolve this
> issue some time ago I implemented another factorization of the basis
> based on Schur complement (please see comments in src/bflib/scf.h),
> where B0 = L0 * U0 is not changed, so B = B0 can be easily restored as
> in case of "eta file".
I did try this, and it seems to work OK. The attached two patches
implement it on top of the three original patches I sent (pcost1.patch
to pcost3.patch). The first one just makes the pseudocost
initialisation use Schur complement updates, to use as a baseline
since the pseudocosts calculated may be different now. The second ones
introduces a bfd_reset() function that restores the original
factorisation and uses this instead of bfd_copy().
Unfortunately, it looks like that the speed gain from using bfd_reset
does not offset the overhead of Schur complement updates, so
Forrest-Tomlin update with bfd_copy seems to be the preferred option
here.
> This approach, however, limits
> the number of simplex iteration (say, to 100-200), since if
> refactorization is needed, to keep B0 = L0 * U0 we should stop.
I suppose this means that a new simplex flag may be needed, to stop
when re-factorisation is required.
Best Regards,
Chris Matrakidis
schur1.patch
Description: Text Data
schur2.patch
Description: Text Data
- Re: [Help-glpk] Patches to improve pseudocost initialisatiion speed, (continued)
- Re: [Help-glpk] Patches to improve pseudocost initialisatiion speed, Andrew Makhorin, 2017/01/09
- Re: [Help-glpk] Patches to improve pseudocost initialisatiion speed, Chris Matrakidis, 2017/01/09
- Re: [Help-glpk] Patches to improve pseudocost initialisatiion speed, Andrew Makhorin, 2017/01/11
- Re: [Help-glpk] Patches to improve pseudocost initialisatiion speed, Andrew Makhorin, 2017/01/11
- Re: [Help-glpk] Patches to improve pseudocost initialisatiion speed, Chris Matrakidis, 2017/01/12
- Re: [Help-glpk] Patches to improve pseudocost initialisatiion speed, Andrew Makhorin, 2017/01/12
- Re: [Help-glpk] Patches to improve pseudocost initialisatiion speed, Andrew Makhorin, 2017/01/12
- Re: [Help-glpk] Patches to improve pseudocost initialisatiion speed, Chris Matrakidis, 2017/01/12
- Re: [Help-glpk] Patches to improve pseudocost initialisatiion speed, Andrew Makhorin, 2017/01/12
- Re: [Help-glpk] Patches to improve pseudocost initialisatiion speed, Chris Matrakidis, 2017/01/12
- Re: [Help-glpk] Patches to improve pseudocost initialisatiion speed,
Chris Matrakidis <=
- Re: [Help-glpk] Patches to improve pseudocost initialisatiion speed, Andrew Makhorin, 2017/01/14
- Re: [Help-glpk] Patches to improve pseudocost initialisatiion speed, Chris Matrakidis, 2017/01/14