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

[Laszlo Ladanyi]

The real solution would be to write a generic caching mechanism for OSI. One 
that would implement storing the changes in a CoinBuild object and when there 
is a call to something where the actual solver must be invoked then all the 
changes would be applied at once and then the call to the solver would be 
made. This is relatively simple to write, but it's lots of coding...

--Laci

On Tue, 27 May 2008, Kish Shen wrote:

> 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
>
>
> _______________________________________________
> Coin-discuss mailing list
> Coin-discuss at list.coin-or.org
> http://list.coin-or.org/mailman/listinfo/coin-discuss
>