Non Linear Integer Programming

views:

169

answers:

+1 Q:

Non Linear Integer Programming

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.

Any ideas?

+2 A:

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).

mbq 2010-07-13 08:25:32

Oh there are better ways than brute force or symbolic computation. Here's just one example: https://projects.coin-or.org/Couenne

Gilead 2010-08-27 03:40:47

@Gilead Remember that this is 1D; for this case and very nonlinear function it won't be faster than bf. The only way to be *sure* that there is no minimum hiding is to look at every value.

mbq 2010-08-27 08:44:40

Gilead 2010-08-27 15:12:15

@Gilead I have missed that comment; probably you are right in majority of real cases, still there exist classes of functions for each it either don't work (assumptions) or is not better than bf. With average, there is always a problem of over what ;-)

mbq 2010-08-27 18:32:51

@mbq: yes, when I say on average, it's more of a statement based on experience rather than mathematical fact. Integer problems are NP hard so there's always a chance of hitting a case where full enumeration (bf) is needed. But you see, by doing a branch-and-bound, one has a nonzero (in fact, usually pretty high) probability of getting the solution without doing full enumeration. If one starts by bf, then there is absolutely zero chance of doing any better. If B-)

Gilead 2010-08-27 22:57:15

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

James 2010-07-13 09:40:38

The first one doesn't handle the integer constraint. The second one looks really good, but also does not handle the integer constraint in the current state

JSmaga 2010-07-13 09:53:58

+1 A:

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.

richardh 2010-07-13 13:43:36

I guess that's the right solution at the end of the day. Or using some SLA to try to get to the best solution possible. Otherwise, it's brute force. Thanks for the link. Brilliant function.

JSmaga 2010-07-14 02:35:23

@richardh: just looked at your background on your profile. Not surpsised you could help me!

JSmaga 2010-07-14 03:09:05

ansaurus

tags:

views:

answers:

Non Linear Integer Programming

related questions