[Coin-lpsolver] Re: Fw: [Coin-core] paper/notes for Coin Presolve?

[Vernon Austel]

Hello,

I must confess to my eternal shame to being the original author of this 
code and hence responsible for its errors.

The paper I refer to in my comments is:

        Presolving in linear programming
        erling D. Andersen, Knud D. Andersen
        Mathematical Programming 71 (1995) 221-245

I have no formal training in optimization.  I learned about optimization 
mostly by reading the source code for OSL.  When I wrote this code, I had 
difficulty understanding how the OSL presolve worked, so John Forrest 
recommended this paper to me, after which I was able to understand most, 
but not all, of the OSL code.  The result is in a sense the OSL algorithms 
recast in this framework.  The simpler transformations generally follow 
the paper, but the more complex ones follow OSL, if for no other reason 
than the paper didn't treat them.  The code even uses old-style OSL 
identifiers like mcstrt (lingering remnants of Fortran).  I never 
developed my own transformations, but hoped that the framework would allow 
other people to do so without too much pain.  I didn't adapt my code for 
COIN; John Forrest did that because I was too embarrassed about the state 
of the code to bring myself to do it.

remove_fixed_action concerns the case where (possibly as the result of 
prior transformations) a variable's bounds become equal (or close enough), 
so one can fix its value.  make_fixed_action concerns the case where a 
variable is to be forced to one of the bounds; the presolver only calls 
this when it determines that this must be the case, but a programmer could 
also use this as a heuristic when solving IPs.  Since the concepts seemed 
so similar, I tried to share code by using removed_fixed_action to 
implement make_fixed_action.  make_fixed_action simply saves the old bound 
and changes it before calling remove_fixed_action::presolve.  I remember 
being not entirely happy about the way it worked out.

The one unusual case is when the presolver starts.  The first 
transformation is to eliminate trivially fixed variables (ones whose 
bounds are already fixed at the start).  I initially had special-purpose 
code to do this, but after a while thought it would be clever to use 
removed_fixed_action to do it instead.  That is what make_fixed is used 
for; it is called in Osi/OsiPresolve.cpp once before anything else (it 
took me a while to find it).  I suspect that it shouldn't be used 
otherwise.

As for remove_fixed, I'm stumped.  That may have been have been an 
experiment that I failed to remove.  I see that I never call it.

I hope this helps.  Keep in mind that it has been about three years since 
I've dealt with this code.  I was pretty depressed about the whole thing 
by the end, so comments like this never got added to the code.

As for the difficulties you mention, I think John Forrest added that code, 
so I will leave that to him.  If it were my code I would not hesistate to 
call them bugs, but since it is his, I would rather not. 

Vernon Austel




Lou Hafer <lou at cs.sfu.ca> 
Sent by: coin-core-admin at www-124.southbury.usf.ibm.com
03/11/2004 01:21 PM
Please respond to
coin-core


To
coin-core at www-124.southbury.usf.ibm.com
cc

Subject
[Coin-core] paper/notes for Coin Presolve?






Folks,

                 I've located the bug I was stalking in CoinPresolve, plus 
what I
think are a few others. I can see a quick patch, but it's not clear to me
that this is the right solution.

                 In the code, there are occasional references to `the 
paper', and also
numbered references (e.g., `(22)') attached to comments. Can anyone point 
me
to this paper, and the source of the numbered references?

                 What I'm having trouble getting my head around is the 
larger picture
of how make_fixed_action (fix a variable) and remove_fixed_action 
(substitute
the value & remove the column) fit together.  Make_fixed_action always
invokes remove_fixed_action. It looks like remove_fixed_action is supposed 
to
be available as an independent action.  (There is at least one example, in
CoinPresolveForcing.cpp.) But is make_fixed_action ever to be used
independently of remove_fixed_action? There is definite information loss 
at
the interface between make_fixed_action and remove_fixed_action in the
present arrangement. There are a number of other questions (free space
management, use of next[Row,Col]ToDo) that I'd like to answer without 
having
to read the whole piece of code.

                 For those interested, a quick description of the bugs. 
For reference,
make_fixed_action::presolve invokes remove_fixed_action::presolve, with 
the
residual effect that a make_fixed_action::postsolve object contains
remove_fixed_action::postsolve objects:

  * r_f_a::postsolve restores the variable as fixed, with equal bounds, 
and
    arbitrarily chooses atUpperBound as the status. It hangs off a
    m_f_a::postsolve object which knows the correct original bound to 
restore
    (unfixing the variable), but doesn't twiddle status.  If the original
    upper bound is infinity, the result is a variable with an upper bound 
of
    infinity and status atUpperBound.

  * m_f_a::presolve adjusts row activity when fixing a variable. It then
    calls r_f_a::presolve, which adjusts the row upper and lower bounds, 
and
    row activity.  Row activity is thus tweaked twice.  This may be the 
cause
    of a lot of the `inacc RSOL' warnings. The adjustment also fails to 
guard
    against tweaking finite infinity, but this may not be important here.

                 Any leads much appreciated.
                 Lou

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://list.coin-or.org/pipermail/clp/attachments/20040311/90147aa8/attachment.html>