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.

Skid

Note that "afternoon" is subjective - e.g. over here when I read this, it's 10AM :-) This is probably one of the reasons why the SO convention is to omit greetings etc. from posts. – Platto

@ Péter Török: Noted. Thanks. Sorry I wasn't aware of this convention. – Skid

@JSmaga: In this case there are only 9 possible values of x, so what is the problem with brute force? – Cloison

@Richie: this is an example...... I might want to optimize on several integers, from larger range. – Skid

Just tell us how many integers do you have and what is f -- it will be much easier this way (or rather possible this way). – Sevik

Well basically that's the problem, I have to do something that would work for any function. At the moment, I am computing financial strategies out of an indicator with an input parameter and I would like to find the value of the parameter such that the expected shortfall [en.wikipedia.org/wiki/Expected_shortfall] is minimal. And that's just the beginning. – Skid

OK, but then be warned, that without suitable assumptions about f you won't find a faster-than-brute-force method that will guarantee to calculate the global minimum. – Sevik

I think the problem in this case is that there is still a long ways to go in getting a nice, stable open-source non-linear solver that can handle integer constraints. Writing such a beast takes a lot of time and skill which usually requires a lot of money. The coin-or project may be able to help- but most of their stuff is still under heavy development. – Perceive

Actually there are two such beasts available (though there are no R interfaces) and they are quite good on most problems. For nonconvex problems: projects.coin-or.org/Couenne and for convex problems: projects.coin-or.org/Bonmin. I use them in my work. – Clardy

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.

Cosset

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. – Skid

just looked at your background on your profile. Not surpsised you could help me! – Skid

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

Sevik

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

@Clardy 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. – Sevik

Yes, in the above case, enumeration is the easiest. But the OP says the above was a toy example, and that he is interested in optimizing over several integers over a larger range. In general, brute force is not the best way. You can use a deterministic global solver (which partitions the search space into underestimated convexified regions, and does a B&B to eliminate nonoptimal regions) to rigorously find a certified global optimum. Now, it is not fast, but on average, it is faster than exhaustive enumeration. See here for theory: www.lehigh.edu/~pib208/papers/belotti-etal-couenne.pdf – Clardy

@Clardy 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 ;-) – Sevik

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&B >= Brute force... so I would always choose B&B. That's how I think anyway. ;-) – Clardy

Answer 3

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

Stanton

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 – Skid

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.

Guffey