7

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.

kjetil b halvorsen
  • 1,206
  • 2
  • 18
  • 28
SRKX
  • 1,806
  • 1
  • 21
  • 42
  • 1
    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. – Péter Török Jul 13 '10 at 07:42
  • @ Péter Török: Noted. Thanks. Sorry I wasn't aware of this convention. – SRKX Jul 13 '10 at 07:50
  • @JSmaga: In this case there are only 9 possible values of `x`, so what is the problem with brute force? – Richie Cotton Jul 13 '10 at 09:42
  • @Richie: this is an example...... I might want to optimize on several integers, from larger range. – SRKX Jul 13 '10 at 09:58
  • 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). – mbq Jul 13 '10 at 15:10
  • 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 [http://en.wikipedia.org/wiki/Expected_shortfall] is minimal. And that's just the beginning. – SRKX Jul 14 '10 at 02:34
  • 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. – mbq Jul 14 '10 at 22:19
  • 2
    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](http://www.coin-or.org) project may be able to help- but most of their stuff is still under heavy development. – Sharpie Jul 17 '10 at 14:05
  • Actually there are two such beasts available (though there are no R interfaces) and they are quite good on most problems. For nonconvex problems: https://projects.coin-or.org/Couenne and for convex problems: https://projects.coin-or.org/Bonmin. I use them in my work. – Gilead Aug 27 '10 at 15:13

4 Answers4

8

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.

Richard Herron
  • 9,760
  • 12
  • 69
  • 116
  • 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. – SRKX Jul 14 '10 at 02:35
  • just looked at your background on your profile. Not surpsised you could help me! – SRKX Jul 14 '10 at 03:09
4

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
  • 18,510
  • 6
  • 49
  • 72
  • Oh there are better ways than brute force or symbolic computation. Here's just one example: https://projects.coin-or.org/Couenne – Gilead Aug 27 '10 at 03:40
  • @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 Aug 27 '10 at 08:44
  • 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 – Gilead Aug 27 '10 at 15:12
  • @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 Aug 27 '10 at 18:32
  • 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. ;-) – Gilead Aug 27 '10 at 22:57
3

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

James
  • 65,548
  • 14
  • 155
  • 193
  • 3
    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 – SRKX Jul 13 '10 at 09:53
2

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.

ali
  • 21
  • 1