[Coin-discuss] adding constraints incrementally to OsiSolverInterface
John J Forrest
jjforre at us.ibm.com
Wed Jul 12 11:50:14 EDT 2006
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
More information about the Coin-discuss
mailing list