Chris.Wilcox at csiro.au
2009-Jun-26 07:23 UTC
[R] Optimization and Linear Programming in R
Dear List, My student and I are looking for an optimizer for a nonlinear optimization problem we are working on. The problem we are working on is to try to pick a set of islands on which to eradicate rats for seabird conservation. We have about 50 islands, each of which has some subset of 17 seabird species. Rats are present on all islands, and will cause the seabirds to go extinct unless they are removed. Removing rats on islands costs different amounts depending on which island is chosen. The decision problem is to pick the set of islands which will save the "most" seabird species within a given budget. Here we use a nonlinear function to calculate the objective. The function is the proportion of individuals of each species saved divided by the total number of birds, times the log of the same number, summed up across all of the islands that are chosen to be in the set that is saved. We have a single constraint, which is a budget in our case. The contribution to this constraint is the product of the cost of each island times the decision vector. Our decision variable is a binary vector (1 for removing rats from an island, 0 for not removing them). The objective function is as I have explained above. We are looking for a solver that can deal with this nonlinear integer programming problem. We looked at a number of packages on the CRAN Task View: Optimization and Mathematical Programming, however, we have not been able to locate one that will suit our purposes. The essential features are we need to be able to write a nonlinear function for the objective (hopefully a self contained one as we need to include some data in it), we need to be able to use a binary decision (or parameter) vector, and we need to be able to use a constraint. Any suggestions as to packages or other software that will work for our problem would be much appreciated. Thanks, Chris Wilcox and Greg Thonier
Hello, On 6/26/09, Chris.Wilcox at csiro.au <Chris.Wilcox at csiro.au> wrote:> We are looking for a solver that can deal with this nonlinear integer programming problem. We looked at a number of packages on the CRAN Task View: Optimization and Mathematical Programming, however, we have not been able to locate one that will suit our purposes. The essential features are we need to be able to write a nonlinear function for the objective (hopefully a self contained one as we need to include some data in it), we need to be able to use a binary decision (or parameter) vector, and we need to be able to use a constraint. Any suggestions as to packages or other software that will work for our problem would be much appreciated. >There is `solnp', part of the "Integer and Nonlinear Optimization in R (RINO)" project [1]. It is still in early beta, though. [1] http://r-forge.r-project.org/projects/rino/
<Chris.Wilcox <at> csiro.au> writes:> Dear List, > > [...] > > We are looking for a solver that can deal with this nonlinear integer > programming problem. We looked at a number of packages on the CRAN Task > View: Optimization and Mathematical Programming, however, we have not > been able to locate one that will suit our purposes. The essential > features are we need to be able to write a nonlinear function for the > objective (hopefully a self contained one as we need to include some > data in it), we need to be able to use a binary decision (or parameter) > vector, and we need to be able to use a constraint. Any suggestions as > to packages or other software that will work for our problem would be > much appreciated.What you desribe appears to be a 'Mixed Integer NonLinear Programming' (MINLP) problem. R may not be the right place to look for such kind of solvers. You can have a look into the NEOS "Optimization Software Guide" or into the Projects page of the "COmputational INfrastructure for Operations Research" (COIN-OR). The 'Bonmin' COIN-OR project could perhaps provide an appropriate solver for this problem. The RINO project on 'R-forge' plans to provide Rbonmin and Rlago packages, but this may take some time. Perhaps by reconsidering your problem approach you can (at least partly) linearize your target function or see if it can be made convex, etc.; it did not sound to be too complex. --Hans Werner P.S.: As far as I know, 'solnp' does not solve mixed integer problems.> Thanks, > > Chris Wilcox and Greg Thonier >
One option is to use optim with method='SANN' which is simulate annealing. The parameter vector is your vector of 0's and 1's, the fn argument is the function that you are trying to maximize with respect to the par vector (sounds like you have that pretty much worked out), then the gr argument is a function that will randomly change the par vector, here is where you put in the budget constraint, only do changes that meet the budget. There are a couple of control parameters that you need to set, see the last set of examples to optim. Hope this helps, -- Gregory (Greg) L. Snow Ph.D. Statistical Data Center Intermountain Healthcare greg.snow at imail.org 801.408.8111> -----Original Message----- > From: r-help-bounces at r-project.org [mailto:r-help-bounces at r- > project.org] On Behalf Of Chris.Wilcox at csiro.au > Sent: Friday, June 26, 2009 1:24 AM > To: r-help at r-project.org > Subject: [R] Optimization and Linear Programming in R > > Dear List, > > My student and I are looking for an optimizer for a nonlinear > optimization problem we are working on. The problem we are working on > is to try to pick a set of islands on which to eradicate rats for > seabird conservation. We have about 50 islands, each of which has some > subset of 17 seabird species. Rats are present on all islands, and > will cause the seabirds to go extinct unless they are removed. > Removing rats on islands costs different amounts depending on which > island is chosen. The decision problem is to pick the set of islands > which will save the "most" seabird species within a given budget. Here > we use a nonlinear function to calculate the objective. The function > is the proportion of individuals of each species saved divided by the > total number of birds, times the log of the same number, summed up > across all of the islands that are chosen to be in the set that is > saved. > > We have a single constraint, which is a budget in our case. The > contribution to this constraint is the product of the cost of each > island times the decision vector. Our decision variable is a binary > vector (1 for removing rats from an island, 0 for not removing them). > The objective function is as I have explained above. > > We are looking for a solver that can deal with this nonlinear integer > programming problem. We looked at a number of packages on the CRAN > Task View: Optimization and Mathematical Programming, however, we have > not been able to locate one that will suit our purposes. The essential > features are we need to be able to write a nonlinear function for the > objective (hopefully a self contained one as we need to include some > data in it), we need to be able to use a binary decision (or parameter) > vector, and we need to be able to use a constraint. Any suggestions as > to packages or other software that will work for our problem would be > much appreciated. > > Thanks, > > Chris Wilcox and Greg Thonier > > ______________________________________________ > R-help at r-project.org mailing list > https://stat.ethz.ch/mailman/listinfo/r-help > PLEASE do read the posting guide http://www.R-project.org/posting- > guide.html > and provide commented, minimal, self-contained, reproducible code.