[Clp] Accumulating rounding errors cause solution to become infeasible

[John J Forrest]

Sebastian,

With finite accuracy, it is possible for Clp to think it is feasible when 
starting from one solution/basis and not from another.

Normally variables which are not in the basis should be at a bound. 
However it is possible with your program that you are introducing problems 
for yourself by adding and deleting constraints as you are doing.  If the 
initial basis is non-singular then adding constraints will keep it 
non-singular as the slack on each new constraint will be put in basis. 
However, when the constraints are deleted some of the constraints will 
probably be tight.  So you will have more variables in basis than there 
are rows.  On the next pass some variables will be thrown out of basis and 
the basis may be singular.  If a variable is -1.0e-8 when in basis and 
leaves basis it may still be set to -1.0e-8 which could lead to rounding 
errors.

If you do an initial solve, save the basis and column solution then you 
could set these back each time.  This may avoid the problem.

John Forrest





[Clp] Accumulating rounding errors cause solution to become     infeasible

Sebastian Theophil 
to:
clp
09/23/2009 01:19 PM


Sent by:
clp-bounces at list.coin-or.org







From:
"Sebastian Theophil" <stheophil at think-cell.com>




To:
<clp at list.coin-or.org>




Sent by:
clp-bounces at list.coin-or.org





Hi,

in our application we solve a linear constraint system many times with
little changes. Very roughly, it looks like this:

OsiClpSolverInterface solver;

AddConstraints(solver);

while( something ) {
                 AddMoreConstraints( solver );
                 solver.initialSolve() / resolve();
                 ...

                 RemoveConstraints( solver ); // undo all changes 
performed
_inside_ loop
}

Now I have a reproducible scenario in which the problem becomes
infeasible during the second run of the while loop but not in the first.
I've seen that some primal solution values have nudged below the lower
bound by just a little bit more than the tolerance (about 10e-7). 

The problem disappears if I save the problem to an mps file after
AddConstraints(solver) and if I reinitialize the solver at the beginning
of each while loop.

How can I debug the problem? The sequence of solver operations during
the first loop is very long, so it isn't practical to create a complete
driver for the problem. Is there some magic setting that forces the
solver to set variables to their precise lower bounds?

Of course, I hesitate to just increase the feasibility tolerance unless
someone recommends to do that for a reason :-) 

Thanks for the help
Sebastian

--
Sebastian Theophil . stheophil at think-cell.com
Software Engineer
 
think-cell Software GmbH . Invalidenstr. 34 . 10115 Berlin, Germany 
http://www.think-cell.com . phone +49-30-666473-10 . toll-free (US) 
+1-800-891-8091
Directors: Dr. Markus Hannebauer, Dr. Arno Schoedl . Amtsgericht 
Berlin-Charlottenburg, HRB 85229


_______________________________________________
Clp mailing list
Clp at list.coin-or.org
http://list.coin-or.org/mailman/listinfo/clp

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://list.coin-or.org/pipermail/clp/attachments/20090923/901adea6/attachment.html>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: not available
Type: image/gif
Size: 821 bytes
Desc: not available
URL: <http://list.coin-or.org/pipermail/clp/attachments/20090923/901adea6/attachment.gif>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: not available
Type: image/gif
Size: 821 bytes
Desc: not available
URL: <http://list.coin-or.org/pipermail/clp/attachments/20090923/901adea6/attachment-0001.gif>