[Clp] Solver seems to work forever after deciding the problem is infeasible

[Robin Whittle]

John,

Thanks very much for your response and updates to the source code.  I
just posted a message to the list describing how I found these changes.

Thanks too for the tip on writing MPS files.  I will write in a
subsequent message exactly how I did it.

You wrote, in part:

> Also setting setMoreSpecialOptions(1); makes code return immediately 
> if presolve says infeasible - I have just modified so that that works
> with bound tightening.
> 
> Obviously the problem is badly scaled.  If you send me an mps file I 
> can look at it.

Thanks for this offer.  For now I will do more work on how my program
formulates the LP.

There were three changes in your revision 2218 of 2016-05-01.  I found
that only the change to ClpSolve.cpp was what I needed, and that the two
changes to ClpSimplexDual.cpp were not required to fix my immediate
problem.

I am using CLP 1.16.9 and want to stick with this for some time,
changing only what whatever is required to avoid the interminable run
time problem.  At some stage in the future I will update everything to a
later version.

My model object iLP is of class ClpSimplex and I am using only Dual
Simplex.  I use presolve unless I am reading in a basis.

I create on object "psAndAlgorithm" of class ClpSolve, and then set it
to use Dual Simplex and to use Presolve or not:

    psAndAlgorithm.setSolveType(ClpSolve::useDual);
    psAndAlgorithm.setPresolveType(ClpSolve::presolveOn); OR:
    psAndAlgorithm.setPresolveType(ClpSolve::presolveOff);

Then I call the solver with:

    statusClp = iLP.initialSolve(psAndAlgorithm);


Your additional lines in ClpSolve.cpp:

  https://projects.coin-or.org/svn/Clp/trunk/Clp/src/ClpSolve.cpp

follow line 1763:

           // return if wanted
           if (options.infeasibleReturn() ||
           (moreSpecialOptions_ & 1) != 0)
             return -1;

and are part of a block of code which runs if the number of
infeasibilities is greater than 0, after a call of
tightenPrimalBounds(), under the conditions that presolve is not being
used and that the model's total number of rows and columns exceeds 5000.

Just adding this code did not alter the behaviour of the program since
neither of the two elements of the if statement were true.
options.infeasibleReturn() was not true, due to the default constructor
for ClpSolve() setting "independent_Options[0]" to 0.
moreSpecialOptions was set to 2.

There is a member function of ClpSolve() for setting
"independent_Options[0]": infeasibleReturn().  At first I thought I
couldn't use this, since I was looking only for a member function of
class ClpSimplex, but I now realise I could have used this on my
psAndAlgorithm object.

Searching the CLP Class List:

  http://www.coin-or.org/Doxygen/Clp/annotated.html

for the setMoreSpecialOptions() function you mentioned showed that this
is a member function of class ClpSimplex.  I could use this to set
moreSpecialOptions_ in my iLP object so its bit 0 is set, which would
cause your new lines of code to return, rather than the problem behavior
of trying to solve the LP.

Since CLP seems to be running fine without bit 0 of moreSpecialOptions_
being set, I decided to leave this as it is.  So the first change I made
to the 1.16.9 version of ClpSolve.cpp was to add just the line:

    return -1;

For the particular LP which caused the trouble (which has more than 5000
total columns and rows), this change was successful - the solver
returned with status indicating the the LP was not solved, which my
program regarded as being due to the LP being infeasible.

However I want to avoid a similar situation occurring if the total
number of columns and rows is 5000 or less.  So the second change I made
was to delete the if statement from line 1744:

    } else if (numberRows_ + numberColumns_ > 5000) {

I searched the 1.16.9 code for anything resembling this check for 5000
total rows and columns and found nothing.  So I assume that this was not
a crucial piece of logic which ties in with some other logic elsewhere.

With these two changes, CLP seems to be running fine.  I am doing a
series of tests which will take another day or so to complete, with
three different tolerance settings which I set before calling the solver
with one of these lines:

   iLP.setDualTolerance(1e-7);   The default value.
   iLP.setDualTolerance(3e-7);
   iLP.setDualTolerance(1e-6);

Thanks for CLP!

  Robin