[Coin-discuss] OsiCpxSolverInterface incompatible with CGL

[Tobias Achterberg]

Hi Jonathan,

> On my list of things to bring up from the ISMP conference: I learned 
> from Matt Saltzman that OsiCpxSolverInterface is incompatible with the 
> CGL.  Apparently the LP relaxation solution gets lost during the various 
> manipulations of the embedded cplex object, and the CGL cannot figure 
> out what point it is trying to cut.  I guess this could be fixed by 
> having OsiCpxSolverInterface cache the LP solution after each call to 
> the cplex solver.

We discussed this issue a lot on the coin-core mailing list. The problem is, 
that there are two different philosophies in the LP solvers. The core of the 
problem is the following:

If an LP was solved, the solution can be accessed with an appropriate call (of 
course). If afterwards, the problem was changed (e.g. adding a cut, adding a 
column, changing a bound, ...), what should be done at the next 
"getSolution"-call? There are two different positions -- and both are correct in 
some way.
1. The solver should return "current problem not yet solved" and refuse to give 
a solution. This is the CPLEX's (and more logic and consistent) point of view, 
and it seems very reasonable, that the "getSolution" call should always give the 
solution for the actual problem. Otherwise, the user may forget to resolve the 
problem and think the (actually old) solution is the solution of the current 
problem.
2. The solver should return the solution of the last solved problem. This is the 
CGL's (and the more algorithmic) point of view. This allows different cut 
generators, to access the current solution through OSI and add cutting planes 
directly to the LP. However, the user has to remember, that the solution 
obtained from the LP solver may have nothing to do with the current LP.

Of course, in COIN we need something following the second philosophie, but the 
question is how and where to implement the caching of the last LP solution. A 
"clean" way may be to collect all the changes to the LP in a separate storage 
(added/removed rows/columns, changed bounds/sides/objectives/coefficients) and 
apply them at the next "solve" call. In this way, all OSI information methods 
(like "getSolution", "getRows", ...) would work in a clearly specified manner: 
they always refer to the last solved problem. Such a mechanism should definitely 
not be implemented in each solver interface, but in an outer wrapper class for 
LP (or more generally subproblem) management.

> In my view, this is a fairly serious bug which undercuts COIN's 
> philosophy of solver independence (agnosticism? atheism? heresy?). 
> Anyway, I was just posting a reminder that this needs to be looked at. I 
> think it can be fixed without waiting for a full redesign of OSI, which 
> will take quite a while.  If it is not dealt with by next month, I could 
> try to fool around with it myself, although I suspect those closer to 
> the code could make the fix more quickly and reliably than I.

Because my time is very limited, I decided to wait for the OSI redesign and then 
implement a new CPLEX interface, instead of fixing the current version with many 
caching methods, only to throw them away when all the caching is (hopefully) 
done in a common base class of all OSI interfaces.

However, if you or anyone else is in the urgent need of getting CGL running with 
CPLEX, it would be nice if you could implement the caching to the CPLEX 
interface. But keep in mind, that caching the last solution is not enough -- you 
also have to cache the column's type (binary, integer, continous), because CPLEX 
discards the type information when the problem's type is switched from MIP to LP.

Regards,    Tobias


-- 
Tobias Achterberg          Konrad-Zuse-Zentrum fuer
                            Informationstechnik Berlin
Tel: +49 (0)30 84185-301   Takustr. 7
Email: achterberg at zib.de   D-14195 Berlin, Germany