[Coin-discuss] Re: osi cplex implementation not MIP friendly

[Ted Ralphs]

Javan,

Yes, I discovered this problem a while back. I've attached my original 
e-mail to the development group in case you are interested in the ugly 
details. There has been a great deal of discussion about it since then 
among the core group of developers. The fix is not all that simple and 
raises a number of difficult issues about how the solver interface 
should behave when the model description changes in some way after the 
problem has already been solved. The approach CPLEX takes is that if the 
model has been changed in any way, then all solution information is 
invalidated. In addition if switching from a MIP to an LP, all integer 
variable information is deleted.

CPLEX's approach is correct in the sense that if you ask for solution 
information with regard to the current model and that model hasn't 
actually been solved, then no solution should be returned. However, it 
would be nice to be able to access the previous solution, even though it 
is no longer valid. This could be done by caching solution information 
in the Osi base class for later access. However, this should be 
accompanied by a notice to the user that the information is not valid 
with respect to the current model.

We are in the process of completely redesigning OSI and in the next 
version, there will be flags to track the validity of certain cached 
information. Because all of this will be fixed in the new version of 
OSI, we haven't gotten around to fixing the old version. It would 
require a little work, but it could be patched up. By the way, I have 
just fixed a few other bugs in OsiCpxSolverInterface, so be sure to do 
an update.

Ted

-------- Original Message --------
Subject: OSI Cplex Interface
Date: Wed, 21 May 2003 19:22:16 -0400
From: Ted Ralphs <tkr2 at lehigh.edu>
To: pfender at zib.de
CC: coin-core at www-124.southbury.usf.ibm.com,  Matthew Galati 
<magh at Lehigh.EDU>

Tobias et al.,

I recently tried to use the Osi CPLEX solver interface with the BCP 
BranchAndBound example and found that it does not work properly (for 
reasons I will explain below). I started to try to fix it, but I found 
that the fix is not so simple and raises some Osi design issues, so I 
figure I would post this to the list. I'm certain that some of these 
have been discussed before, so please forgive the repitition.

The issue stems from the fact that CPLEX requires the user to set a 
problem type (basically either LP or MILP) and only allows the user to 
call the problem modification and query routines that make sense for the 
problem type. For example, if the problem type is LP, then the user 
cannot set a variable to be integer. This means that in the 
implementation of the interface, if the user requests that a variable be 
set to integer, then the problem type must be changed to MILP before 
doing so. Once the problem type is set to MILP, however, the problem can 
no longer be solved as an LP and all problem information (such as the 
solution) cached by CPLEX is erased. In other words, if you solve an LP
relaxation, then set a variable to integer through the interface and 
then try to get the solution to the LP relaxation, this will fail. This 
means that you cannot the Osi CPLEX solver interface with the CGL to 
implement the processing of a node in branch and cut, because the CGL 
first requires variables to be set to integer through the interface and 
then tries to access the solution to the LP relaxation. But as soon as 
you set any variable to integer, the solution to the LP relaxation is 
erased. Furthermore, you cannot set any variable to integer before 
solving the LP relaxation either because as soon as the problem type is
set to LP, CPLEX wipes out all record of which variables are integer. 
Hence, it is impossible to mix LP and MILP functions in the way that you 
would want in order to implement branch and cut. One could argue that 
this is a poor design on the part of CPLEX, but we have to live with it 
nonetheless.

The most obvious solution is to leave the problem type set to LP except 
in the case that the user calls branchAndBound(), at which time the 
problem type must be changed to MILP. This means that all information 
relating to integer variables, etc, would have to cached locally by the 
interface and all queries handled directly by the interface.  This could 
be done within the CPLEX interface fairly easily, but it begs the 
question as to whether this should just be handled in the base class. 
The way the Osi is currently implemented is a mix of LP and MILP, which 
is definitely biased towards the implementation of branch and cut. 
CPLEX, on the other hand, has a completely different philosophy.

Currently, BCP's approach is to cache variable types locally and so the 
Osi CPLEX interface works fine, as long as the CGL is not invoked. 
However, once the CGL is invoked, things are not so nice. Using the 
current version of the interface with the BranchAndCut example results 
in a fatal error because some of the Osi routines do not set the problem 
type back to LP after changing it to MILP. I have fixed this problem and 
now the example runs, but the CGL is unable to access the solution to 
the LP relaxation, so no cuts are found.

There are also some other unrelated issues with the CPLEX interace, such 
as the fact that the return value is not checked after solving an LP, 
which means that any infeasibility found during presolve is not detected 
by the interface, but these are relatively easy to fix.

I'd be happy to help with fixing these problems, but I wanted to get 
some reaction before I forge ahead. Thoughts?

Cheers,

Ted
-- 
Dr. Ted Ralphs
Assistant Professor
Industrial and Systems Engineering
Lehigh University
(610)758-4784
tkralphs at lehigh.edu
www.lehigh.edu/~tkr2