<br><font size=2 face="sans-serif">Hello,</font>
<br>
<br><font size=2 face="sans-serif">I must confess to my eternal shame to
being the original author of this code and hence responsible for its errors.</font>
<br>
<br><font size=2 face="sans-serif">The paper I refer to in my comments
is:</font>
<br>
<br><font size=2 face="sans-serif"> Presolving
in linear programming</font>
<br><font size=2 face="sans-serif"> erling
D. Andersen, Knud D. Andersen</font>
<br><font size=2 face="sans-serif"> Mathematical
Programming 71 (1995) 221-245</font>
<br>
<br><font size=2 face="sans-serif">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.</font>
<br>
<br><font size=2 face="sans-serif">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.</font>
<br>
<br><font size=2 face="sans-serif">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.</font>
<br>
<br><font size=2 face="sans-serif">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.</font>
<br>
<br><font size=2 face="sans-serif">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.</font>
<br>
<br><font size=2 face="sans-serif">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. </font>
<br>
<br><font size=2 face="sans-serif">Vernon Austel</font>
<br>
<br>
<br>
<br>
<table width=100%>
<tr valign=top>
<td width=40%><font size=1 face="sans-serif"><b>Lou Hafer <lou@cs.sfu.ca></b>
</font>
<br><font size=1 face="sans-serif">Sent by: coin-core-admin@www-124.southbury.usf.ibm.com</font>
<p><font size=1 face="sans-serif">03/11/2004 01:21 PM</font>
<table border>
<tr valign=top>
<td bgcolor=white>
<div align=center><font size=1 face="sans-serif">Please respond to<br>
coin-core</font></div></table>
<br>
<td width=59%>
<table width=100%>
<tr>
<td>
<div align=right><font size=1 face="sans-serif">To</font></div>
<td valign=top><font size=1 face="sans-serif">coin-core@www-124.southbury.usf.ibm.com</font>
<tr>
<td>
<div align=right><font size=1 face="sans-serif">cc</font></div>
<td valign=top>
<tr>
<td>
<div align=right><font size=1 face="sans-serif">Subject</font></div>
<td valign=top><font size=1 face="sans-serif">[Coin-core] paper/notes for
Coin Presolve?</font></table>
<br>
<table>
<tr valign=top>
<td>
<td></table>
<br></table>
<br>
<br>
<br><font size=2><tt>Folks,<br>
<br>
I've located the bug I was stalking in CoinPresolve, plus what I<br>
think are a few others. I can see a quick patch, but it's not clear to
me<br>
that this is the right solution.<br>
<br>
In the code, there are occasional references to `the paper', and also<br>
numbered references (e.g., `(22)') attached to comments. Can anyone point
me<br>
to this paper, and the source of the numbered references?<br>
<br>
What I'm having trouble getting my head around is the larger picture<br>
of how make_fixed_action (fix a variable) and remove_fixed_action (substitute<br>
the value & remove the column) fit together. Make_fixed_action
always<br>
invokes remove_fixed_action. It looks like remove_fixed_action is supposed
to<br>
be available as an independent action. (There is at least one example,
in<br>
CoinPresolveForcing.cpp.) But is make_fixed_action ever to be used<br>
independently of remove_fixed_action? There is definite information loss
at<br>
the interface between make_fixed_action and remove_fixed_action in the<br>
present arrangement. There are a number of other questions (free space<br>
management, use of next[Row,Col]ToDo) that I'd like to answer without having<br>
to read the whole piece of code.<br>
<br>
For those interested, a quick description of the bugs. For reference,<br>
make_fixed_action::presolve invokes remove_fixed_action::presolve, with
the<br>
residual effect that a make_fixed_action::postsolve object contains<br>
remove_fixed_action::postsolve objects:<br>
<br>
* r_f_a::postsolve restores the variable as fixed, with equal bounds,
and<br>
arbitrarily chooses atUpperBound as the status. It hangs
off a<br>
m_f_a::postsolve object which knows the correct original
bound to restore<br>
(unfixing the variable), but doesn't twiddle status. If
the original<br>
upper bound is infinity, the result is a variable with an
upper bound of<br>
infinity and status atUpperBound.<br>
<br>
* m_f_a::presolve adjusts row activity when fixing a variable. It
then<br>
calls r_f_a::presolve, which adjusts the row upper and lower
bounds, and<br>
row activity. Row activity is thus tweaked twice. This
may be the cause<br>
of a lot of the `inacc RSOL' warnings. The adjustment also
fails to guard<br>
against tweaking finite infinity, but this may not be important
here.<br>
<br>
Any leads much appreciated.<br>
Lou</tt></font>
<br>
<br>