Dynamic Programming in R

classic Classic list List threaded Threaded
7 messages Options
Reply | Threaded
Open this post in threaded view
|

Dynamic Programming in R

Arnab mukherji
Hi R users,

I am looking to numerically solve a dynamic program in the R environment. I was wondering if there were people out there who had expereinced success at using R for such applications. I'd rather continue in R than learn Mathlab.

A concern that has been cited that may discourage R use for solving dynamic programs is its memory handling abilities.  A senior researcher had a lot of trouble with R becuase on any given run it would eat up all the computers memory and need to start using the hard disk. Yet, the memory needed was not substantial - saving the worksapce, exiting and recalling would noticebly start of tthe progam at a much lower memory use, level and a quick deteroration in a few thousand iterations.

Is this a problem other people have come across? Perhaps, its a problem already fixed, since the researcher was working on this in 2002 (he claimed he had tried it on windows, mac, and unix versions to check).

Thanks.

Arnab

______________________________________________
[hidden email] mailing list
https://stat.ethz.ch/mailman/listinfo/r-help
PLEASE do read the posting guide! http://www.R-project.org/posting-guide.html
Reply | Threaded
Open this post in threaded view
|

Re: Dynamic Programming in R

Bert Gunter
1. I have no experience in dynamic programming (so you may want to ignore
the rest of this message)

2. Your message is vague (to me) -- more specifics about what you want to do
might result in a better answer.

3. R has become **much** better at loop management since 2002

4. Nevertheless, there are undoubtedly still situations where R may require
an unacceptably large amount of memory overhead. Recursion is one, I
believe.

Usually the best advice is: try it and see.

-- Bert Gunter
Genentech Non-Clinical Statistics
South San Francisco, CA
 
 

> -----Original Message-----
> From: [hidden email]
> [mailto:[hidden email]] On Behalf Of Arnab mukherji
> Sent: Thursday, January 19, 2006 1:55 PM
> To: [hidden email]
> Subject: [R] Dynamic Programming in R
>
> Hi R users,
>
> I am looking to numerically solve a dynamic program in the R
> environment. I was wondering if there were people out there
> who had expereinced success at using R for such applications.
> I'd rather continue in R than learn Mathlab.
>
> A concern that has been cited that may discourage R use for
> solving dynamic programs is its memory handling abilities.  A
> senior researcher had a lot of trouble with R becuase on any
> given run it would eat up all the computers memory and need
> to start using the hard disk. Yet, the memory needed was not
> substantial - saving the worksapce, exiting and recalling
> would noticebly start of tthe progam at a much lower memory
> use, level and a quick deteroration in a few thousand iterations.
>
> Is this a problem other people have come across? Perhaps, its
> a problem already fixed, since the researcher was working on
> this in 2002 (he claimed he had tried it on windows, mac, and
> unix versions to check).
>
> Thanks.
>
> Arnab
>
> ______________________________________________
> [hidden email] mailing list
> https://stat.ethz.ch/mailman/listinfo/r-help
> PLEASE do read the posting guide!
> http://www.R-project.org/posting-guide.html
>

______________________________________________
[hidden email] mailing list
https://stat.ethz.ch/mailman/listinfo/r-help
PLEASE do read the posting guide! http://www.R-project.org/posting-guide.html
Reply | Threaded
Open this post in threaded view
|

Re: Dynamic Programming in R

François Pinard
In reply to this post by Arnab mukherji
[Arnab mukherji]

>A concern that has been cited that may discourage R use for solving
>dynamic programs is its memory handling abilities.

For a dynamic programming problem defined over N steps, one usually
needs a N*N matrix, so problems should be tractable for N being "not too
big".  In those I studied, CPU time usually was the scarse resource.
As extreme paths were known to be very unlikely, this (and memory as
well) could be alleviated somehow by limiting the solution search into
bands (more or less wide) following the diagonal of the solution matrix.  
I also had some success in splitting big problems into a sequence of
smaller subproblems, and recursively: such approximations are likely not
acceptable in the general case.

I would guess that most dynamic programming problems have their own
specific artifacts and speed-up techniques, a universal solution might
be uneasy.  Who knows (I'm not sure): R might well offer a powerful
environment for building a dynamic programming framework.

--
François Pinard   http://pinard.progiciels-bpi.ca

______________________________________________
[hidden email] mailing list
https://stat.ethz.ch/mailman/listinfo/r-help
PLEASE do read the posting guide! http://www.R-project.org/posting-guide.html
Reply | Threaded
Open this post in threaded view
|

Re: Dynamic Programming in R

Gabor Grothendieck
In reply to this post by Arnab mukherji
The lpSolve package can handle integer programming problems.

Here is an example of using dynamic programming in R from
first principles in another setting:

http://tolstoy.newcastle.edu.au/R/help/06/01/18845.html

On 1/19/06, Arnab mukherji <[hidden email]> wrote:

> Hi R users,
>
> I am looking to numerically solve a dynamic program in the R environment. I was wondering if there were people out there who had expereinced success at using R for such applications. I'd rather continue in R than learn Mathlab.
>
> A concern that has been cited that may discourage R use for solving dynamic programs is its memory handling abilities.  A senior researcher had a lot of trouble with R becuase on any given run it would eat up all the computers memory and need to start using the hard disk. Yet, the memory needed was not substantial - saving the worksapce, exiting and recalling would noticebly start of tthe progam at a much lower memory use, level and a quick deteroration in a few thousand iterations.
>
> Is this a problem other people have come across? Perhaps, its a problem already fixed, since the researcher was working on this in 2002 (he claimed he had tried it on windows, mac, and unix versions to check).
>
> Thanks.
>
> Arnab
>
> ______________________________________________
> [hidden email] mailing list
> https://stat.ethz.ch/mailman/listinfo/r-help
> PLEASE do read the posting guide! http://www.R-project.org/posting-guide.html
>

______________________________________________
[hidden email] mailing list
https://stat.ethz.ch/mailman/listinfo/r-help
PLEASE do read the posting guide! http://www.R-project.org/posting-guide.html
Reply | Threaded
Open this post in threaded view
|

Re: Dynamic Programming in R

Jens Oehlschlägel
In reply to this post by Arnab mukherji
Gunter,

> there are undoubtedly still situations where R may require an unacceptably
large amount of memory overhead. Recursion is one, I
believe.

One can avoid unacceptably large amount of memory overhead when doing
recursion in R: either by passing parameters "by reference" using package
ref or by directly using environments.

Best regards


Jens Oehlschlägel

--

______________________________________________
[hidden email] mailing list
https://stat.ethz.ch/mailman/listinfo/r-help
PLEASE do read the posting guide! http://www.R-project.org/posting-guide.html
Reply | Threaded
Open this post in threaded view
|

Re: Dynamic Programming in R

Arne.Muller
In reply to this post by Arnab mukherji
Hello,

I've implemented dynamic programming for aligning spectral data (usually 100 to 200 peaks in one spectrum, but some spectra contain > 5k peaks) entirely in R. As François Pinard pointed out, the memory usage should be proportional to the n x n dynamic programming matrix, and I've not yet had any problems on my machine (R2.2.0 win2k, 1GB mem, 2GHz Intel PV), CPU seems to be the more problematic issue.

I guess it all depends on how much data you have. You could split the dynamic programming matrix into chunks and calculate them in parallel on different machines (but the implementatino of finding the optiomal trace will probably get a bit difficult).

        kind regards,

        Arne

-----Original Message-----
From: [hidden email]
[mailto:[hidden email]]On Behalf Of Arnab mukherji
Sent: Thursday, January 19, 2006 22:55
To: [hidden email]
Subject: [R] Dynamic Programming in R


Hi R users,

I am looking to numerically solve a dynamic program in the R environment. I was wondering if there were people out there who had expereinced success at using R for such applications. I'd rather continue in R than learn Mathlab.

A concern that has been cited that may discourage R use for solving dynamic programs is its memory handling abilities.  A senior researcher had a lot of trouble with R becuase on any given run it would eat up all the computers memory and need to start using the hard disk. Yet, the memory needed was not substantial - saving the worksapce, exiting and recalling would noticebly start of tthe progam at a much lower memory use, level and a quick deteroration in a few thousand iterations.

Is this a problem other people have come across? Perhaps, its a problem already fixed, since the researcher was working on this in 2002 (he claimed he had tried it on windows, mac, and unix versions to check).

Thanks.

Arnab

______________________________________________
[hidden email] mailing list
https://stat.ethz.ch/mailman/listinfo/r-help
PLEASE do read the posting guide! http://www.R-project.org/posting-guide.html

______________________________________________
[hidden email] mailing list
https://stat.ethz.ch/mailman/listinfo/r-help
PLEASE do read the posting guide! http://www.R-project.org/posting-guide.html
Reply | Threaded
Open this post in threaded view
|

Re: Dynamic Programming in R

hadley wickham
In reply to this post by Jens Oehlschlägel
> > there are undoubtedly still situations where R may require an unacceptably
> large amount of memory overhead. Recursion is one, I
> believe.
>
> One can avoid unacceptably large amount of memory overhead when doing
> recursion in R: either by passing parameters "by reference" using package
> ref or by directly using environments.

Or by unrolling tail recursion into a loop, of course.

Hadley

______________________________________________
[hidden email] mailing list
https://stat.ethz.ch/mailman/listinfo/r-help
PLEASE do read the posting guide! http://www.R-project.org/posting-guide.html