Non Linear Integer Programming

Question

I would like to know if there is a package in R handling non linear integer optimization.

"Basically", I would like to solve the following problem:

max f(x) s.t x in (0,10) and x is integer.

I know that some branching algorithms are able to handle the linear version of this problem, but here my function f() might be more complicated. (I can't even make sure it would be quadratic of the form f(x)=xQx).

I guess there is always the brute force solution to test all the possibilities as long as they are bounded, but I was wondering if there wasn't anything smarter.

Answer 1

I have a few options for you, but none of them is the silver bullet, although it looks like your silver bullet is in the works under the rino project: http://r-forge.r-project.org/projects/rino/.

Since your function is complicated, you may want to use a genetic algorithm (i.e., gradient-based optimizers may not be reliable). genoud in the rgenoud library may do the trick (link text). If you set data.type.int=TRUE it should do the trick. I have not used this library, but have some experience with GAs in matlab and the time to convergence is sensitive to the settings, so you'll be well served to read the man page a few times through.

Or, if your function in strictly concave (unlikely, since you say it may be complicated) you can solve with a gradient solver (e.g., optim) then check the neighborhood around the optimum (can't be more than 2^n points to check).

Sorry, I can't be of more help.

Answer 2

If it is hardly nonlinear there is no better method than brute force (you will never know if the minimum is local or if some flat-looking fragment doesn't have any narrow and deep valleys), except of course symbolic computation (which probably won't work because the function is too complicated) or soft computing, I mean things like genetic algorithms, Monte-Carlo, swarms, etc. (here you don't have a guarantee that it will find the very global minimum and because you have integer x it can be slower than brute force).

Answer 3

http://cran.r-project.org/web/views/Optimization.html lists the packages Rdonlp2 and Rsolnp which may be suitable.

Answer 4

Discrete filled function method is one of the recent methods that can find global solution of nonlinear integer programming with about 100 constraints and variables.