[Top][All Lists]

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Re: [Help-glpk] Solve then add rows then presolve: Can I maintain basis?

From: Andrew Makhorin
Subject: Re: [Help-glpk] Solve then add rows then presolve: Can I maintain basis?
Date: Wed, 2 Jul 2008 23:18:48 +0400

> If I keep the presolver on, the basis information from the previous
> solve is lost and the 2-phase primal algorithm kicks off from scratch
> (instead of the dual simplex using the previous basis).  If I turn the
> presolver off, I know my problem is bigger than it needs to be, but
> the dual simplex does kick in starting with the previously optimal
> basis.  So I guess my question is:  is there a way to use the
> presolver AND supply an initial basic solution?

No, the lp presolver does not use the current basis information,
so you should disable it on performing re-optimization.

>   If not, is there a
> mathematical/algorithmic reason this isn't possible?

There is not much sense to do that, because re-optimization needs
much less iterations. Besides, in that case the lp presolver could not
remove redundant basic rows and redundant non-basic columns.

>    If so, I'd be
> interested in hearing it because it will probably change my approach
> (and understanding) of my problem.  My understanding from the glpk
> code is that the presolver uses a copy of the original problem to
> perform all of it transformations and then the solution to the
> presolved problem is translated back to the original problem when the
> simplex completes.


> This transformation must interfere with any basis
> that the original problem had, thus eliminating it I suppose?  Hope
> all of these questions make sense.

> I'll gladly supply more info if it's helpful.  Thanks in advance for
> any insights.

reply via email to

[Prev in Thread] Current Thread [Next in Thread]