[Coin-discuss] adding constraints incrementally to OsiSolverInterface
Kish Shen
kish.shen at crosscoreop.com
Wed Jul 12 12:32:20 EDT 2006
John,
Thanks for your reply. I fully understand that you may not have time at the
moment to look at this. I will try and look at using a derived class.
One thing about the CoinPackedMatrix: the documentation states that `extra'
spaces can be added to the matrix to allow for faster insertion of new data.
Perhaps this can be exposed to the user in both Clp's and
Osi(Clp)SolverInterface's loadProblem() methods?
Cheers,
Kish
On Wednesday 12 July 2006 16:50, John J Forrest wrote:
> Kish,
>
> I will have to postpone looking further into this until I have more time.
> Clp by default works with a CoinPackedMatrix which imposes certain
> limitations, but I think some of your difficulties lie in trying to be
> totally solver agnostic. One approach I might try if I was using OsiClp
> would be to derive a new class from OsiClpSolverInterface which would
> implement a more cached version of addRow or use a row copy and then flip
> it on a call to solve.
>
> John Forrest
>
>
>
> Kish Shen
> <kish.shen at crossc
> oreop.com> To
> Sent by: coin-discuss at list.coin-or.org
> coin-discuss-boun cc
> ces at list.coin-or.
> org Subject
> Re: [Coin-discuss] adding
> constraints incrementally to
> 07/12/06 10:55 AM OsiSolverInterface
>
>
> Please respond to
> Discussions about
> open source
> software for
> Operations
> Research
> <coin-discuss at lis
> t.coin-or.org>
>
>
>
>
>
>
> John,
>
> Thanks for your reply. I think I had looked at the addRows.cpp code before,
>
> which is why I use CoinBuild to build each row.
>
> As I understand that code, you add all the rows to add incrementally to the
>
> CoinBuild/CoinModel object, and then when all the rows are added, put them
> into the OsiSolverInterface object in one go. Am I correct? The problem is
> that I can't do that, because the conceptual model we have is that each row
>
> is added immediately to the problem matrix. The user can inspect the matrix
>
> (such as asking for the constraints, or checking its size) as well as
> trigger
> a solve on the matrix.
>
> I have thought of keeping a CoinModel representation of the problem around
> all
> the time, and to make changes to this, rather than to the
> OsiSolverInterface
> object. However this would mean copying (and persumably packing) of the
> CoinModel each time I want to solve the problem, and in addition, it was
> not
> clear that adding incrementally to the CoinModel will be cheap [and the
> addRows.cpp example does indeed show it is significantly more expensive].
>
> One of the reasons we allow this incremental adding of rows is that it is
> not
> too expensive in CPLEX and XPRESS. I am not sure how they make the
> incremental add efficient, but I assume they do reduce the amount of
> copying
> by reserving space in the problem matrix to allow the problem to be
> expanded
> without copying. Does the resize() method for ClpModel (used in
> addRows.cpp)
> do something like this? Can a problem be solved after a resize, but before
> the specified number of rows and columns in the resize are added?
>
> Thanks and cheers,
>
> Kish
>
> On Wednesday 12 July 2006 14:25, John J Forrest wrote:
> > Kish,
> >
> > Yes. Use a CoinModel object (or faster but less flexible a CoinBuild
> > object) to do addRow and then use that to add to OsiSolverInterface
>
> object.
>
> > There is an example in ../Clp/examples/addRows.cpp which is for Clp but
>
> the
>
> > same functionality is available in OsiSolverInterface
> >
> > John Forrest
> >
> >
> >
> > Kish Shen
> > <kish.shen at crossc
> > oreop.com>
>
> To
>
> > Sent by: coin-discuss at list.coin-or.org
> > coin-discuss-boun
>
> cc
>
> > ces at list.coin-or.
> > org
>
> Subject
>
> > [Coin-discuss] adding constraints
> > incrementally to
> > 07/12/06 12:04 AM OsiSolverInterface
> >
> >
> > Please respond to
> > Discussions about
> > open source
> > software for
> > Operations
> > Research
> > <coin-discuss at lis
> > t.coin-or.org>
> >
> >
> >
> >
> >
> >
> > Hi,
> >
> > Is there any way to improve the speed of adding constraints incrementally
> > to a
> > program in a OsiSolverInterface?
> >
> > In our interface to COIN/Osi, we allow users to add constraints one by
>
> one
>
> > to
> > modify the problem. I use a CoinBuild to create the row representing the
> > constraint, and then use OsiSOlverInterface's addCols() to add the row to
> > the
> > problem.
> >
> > We also allow the user to specify constraints before they create the
> > COIN/Osi
> > problem. In this case, the constraints are loaded into the
> > OsiSolverInterface
> > with loadProblem() [with essentially the column-wise representation used
>
> by
>
> > CPLEX and Xpress, the initial targets of our interface].
> >
> > Our interface has to allow the user to add constraints incrementally,
> > because
> > this provides the most flexibility for our users.
> >
> > I compared the loading times of adding all the constraints at the start
> > when
> > setting up the OsiSolverInterface with that of setting up the
> > OsiSolverInterface, and then adding the constraints one by one. For two
> > examples, one much larger than the other, here are the load times in
> > seconds:
> >
> > Load at start Incremental
> > small (780 rows) 0.03 0.11
> > big (40215 rows) 1.49 299
> >
> > the cost for loading many rows incrementally is thus very expensive. I
> > assume
> > this is because the problem has to be repeatedly copied and expanded?
> > [I am using OsiClpSolverInterface for this test]
> >
> > For Xpress and CPLEX, the cost for loading the whole problem at the start
> > is
> > similar to for COIN/Osi, but the incremental is much better. For the big
> > problem, the load times are 1.6s (load at start) and 3.8 (incremental).
> >
> > Is there anyway I can make the incremental adding of rows more efficient
> > for
> > OsiSolverInterface?
> >
> > Thanks in advance for any help/information!
> >
> > Cheers,
> >
> > Kish Shen
> >
> > _______________________________________________
> > Coin-discuss mailing list
> > Coin-discuss at list.coin-or.org
> > http://list.coin-or.org/mailman/listinfo/coin-discuss
> >
> >
> > _______________________________________________
> > Coin-discuss mailing list
> > Coin-discuss at list.coin-or.org
> > http://list.coin-or.org/mailman/listinfo/coin-discuss
>
> _______________________________________________
> Coin-discuss mailing list
> Coin-discuss at list.coin-or.org
> http://list.coin-or.org/mailman/listinfo/coin-discuss
>
>
> _______________________________________________
> Coin-discuss mailing list
> Coin-discuss at list.coin-or.org
> http://list.coin-or.org/mailman/listinfo/coin-discuss
More information about the Coin-discuss
mailing list