[Coin-discuss] improving the performance of adding constraints via OSI

[Kish Shen]

Hi,

I have been having this performance issue with adding constraints to a problem, which I would
like to solve now.

My use of OSI is to provide an interface to the constraint logic programming language ECLiPSe.
The user can create and modify a problem in many ways, in particular, the user can add
constraints incrementally to a problem, and repeatedly solve a problem. Unfortunately,  I
am unable to make this incremental adding of constraints efficient via OSI -- the cost
increase quite rapidly with the number of constraints, while doing the same thing with CPLEX
is much more efficient. Here are the results of a simple test I did with adding the same 
constraint repeatedly to a problem, and here are the timings for doing this on CPLEX (10.1) 
and CLP/CBC on the same machine:

                 CPLEX          CLP/CBC
  1000            0.06                   0.23
 10000           0.30                   4.06
 20000           0.67                  14.61

In my code, I add constraints vua OSI as follows:

    CoinBuild build;

    for (int i=0; i<coladded; i++)
    {
	build.addColumn(matbeg[i+1]-matbeg[i],
			&(matind[matbeg[i]]),
			&(matval[matbeg[i]]),
			bdl[i], bdu[i], objx[i]);
    }

    static_cast<OsiSolverInterface* >(lp->Solver)->addCols(build);

This code should be reasonably efficient if many constraints are added at the same time, but in
my test case above, the constraints are added one by one (i.e. coladded = 1, and this code is 
called each time a constraint is added). Added the constraints one by one is often the most
convenient  for the user, so I would like to be able to make this efficient.

As I am providing an interface myself, I would like the code to be efficient for different cases:
the user can repeatedly modify and resolve the problem. Between each solve, the user can add
only a few, or many constraints to the problem -- it is important that all these cases are 
efficient. It will also be very important to retain any warm start information between the solves.

I had a brief discussion with John Forrest about this problem last week, and he suggested 
that I should retain the problem external to the solver (which I guess means in the CoinBuild
matrix in my case), and only pass the problem to the solver when the problem is to be solved.
Ideally I would like to be able to do this via OSI, because I would like my code to work with 
different solvers. It seems that the only way I can do this is to load the problem afresh (via
loadProblem() or assignProblem()), but is this efficient for the case when the problem is only
slightly modified, and how do I retain the warm start information in this case?

If it is not possible to do this effectively with OSI, I am willing to write special code to make it
efficient for CLP/CBC, which is the main linear solver I am interface to.

Thanks in advance for any information and help!

Yours sincerely,

Kish