[CoinUtils-tickets] [COIN-OR Common Utilities] #67: postsolve in CoinPresolve does not correctly handle slack variables at bounds

[COIN-OR Common Utilities]

#67: postsolve in CoinPresolve does not correctly handle slack variables at
bounds
-----------------------+----------------------------------------------------
  Reporter:  stefan    |      Owner:       
      Type:  defect    |     Status:  new  
  Priority:  critical  |    Version:  trunk
Resolution:            |   Keywords:       
-----------------------+----------------------------------------------------

Old description:

> Activating asserts in OsiPresolve::postsolve and running the Osi unittest
> shows issues with the postsolve routines of !CoinPresolve.
> It seems that slack variables may be set to status atLowerBound for rows
> with infinite right hand side or set to atUpperBound for rows with
> infinite left hand side.
>
> Lou had a look into it and reports:
> {{{
>     For reference, the notion of logical variable and row status enforced
> by the OSI unit test is:
>
>   <=    0 < s < infty    logical atLowerBound when constraint tight
>   >=    -infty < s < 0    logical atUpperBound when constraint tight
>
> Which is nicely compatible with upper-bounded logicals for range
> constraints.
>
>     I repaired CoinPresolvePsdebug (minor collateral damage from the
> config.h stuff) and added code to presolve_check_sol to check the row
> status. Turns out that forcing_constraint_action::postsolve and
> subst_constraint_action::postsolve were directly setting incorrect row
> status, and slack_doubleton_action::postsolve was indirectly getting it
> wrong via CoinPrePostsolveMatrix::setRowStatusUsingValue. All of these
> had the atLowerBound/atUpperBound convention reversed. Falls into the
> category of `why did anything work at all' because the relevant bits of
> code date back to 2004, probably earlier. Apparently none of the previous
> implementors using CoinPresolve were actually using the row status
> information? Or were using it and changes will break lots of code? I'm
> not looking forward to committing this.
>
>     Which leads to the obvious question `So what's really wrong?' I don't
> have the solution yet, but right now the answer appears to be that row
> bounds are not properly restored. The instances I'm seeing are uniformly
> a value of 0 but should be ± infty. There is, of course, the possibility
> that I introduced this bug while fixing the row status.
> }}}

New description:

 Activating asserts in OsiPresolve::postsolve and running the Osi unittest
 shows issues with the postsolve routines of !CoinPresolve.
 It seems that slack variables may be set to status atLowerBound for rows
 with infinite right hand side or set to atUpperBound for rows with
 infinite left hand side.

 Lou had a look into it and reports:[[br]]
   For reference, the notion of logical variable and row status enforced by
 the OSI unit test is:
 {{{
   <=    0 < s < infty    logical atLowerBound when constraint tight
   >=    -infty < s < 0    logical atUpperBound when constraint tight
 }}}
   Which is nicely compatible with upper-bounded logicals for range
 constraints.

   I repaired !CoinPresolvePsdebug (minor collateral damage from the
 config.h stuff) and added code to presolve_check_sol to check the row
 status. Turns out that forcing_constraint_action::postsolve and
 subst_constraint_action::postsolve were directly setting incorrect row
 status, and slack_doubleton_action::postsolve was indirectly getting it
 wrong via CoinPrePostsolveMatrix::setRowStatusUsingValue. All of these had
 the atLowerBound/atUpperBound convention reversed. Falls into the category
 of `why did anything work at all' because the relevant bits of code date
 back to 2004, probably earlier. Apparently none of the previous
 implementors using !CoinPresolve were actually using the row status
 information? Or were using it and changes will break lots of code? I'm not
 looking forward to committing this.

   Which leads to the obvious question `So what's really wrong?' I don't
 have the solution yet, but right now the answer appears to be that row
 bounds are not properly restored. The instances I'm seeing are uniformly a
 value of 0 but should be ± infty. There is, of course, the possibility
 that I introduced this bug while fixing the row status.

--

Comment (by lou):

 A quick update: I can say that I didn't introduce the bug that causes the
 failure to restore the row bounds, based on a test with a previous trunk
 version. And I've found the same incorrect row status code in several
 other postsolve methods. Looks like there was a change of convention at
 some point that wasn't reflected back into !CoinPresolve code. So far it's
 been a typical venture into !CoinPresolve. One thing leads to three more.

-- 
Ticket URL: <https://projects.coin-or.org/CoinUtils/ticket/67#comment:1>
COIN-OR Common Utilities <http://projects.coin-or.org/CoinUtils>
Common data structures and linear algebra functions for COIN-OR projects