Quantcast

non-linear integer optimization?

classic Classic list List threaded Threaded
4 messages Options
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

non-linear integer optimization?

darckeen
Are there any packages that do non-linear integer otimization?  Looked at lpSolve but i'm pretty sure it only works with linear programming and not non-linear, tried "L-BFGS-B" optim after flooring all my params, works somewhat but seems really inefficient.  Anything else I should look at?
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: non-linear integer optimization?

Hans W Borchers
darckeen <darckeen <at> hotmail.com> writes:

>
> Are there any packages that do non-linear integer otimization?  Looked at
> lpSolve but i'm pretty sure it only works with linear programming and not
> non-linear, tried "L-BFGS-B" optim after flooring all my params, works
> somewhat but seems really inefficient.  Anything else I should look at?

The most general answer is:  There is no R package for MINLP problems !

But: Would have been nice if you had done the following things:

  - Have a look into the 'optimization' task view
  - Provide an example of a function you would like to optimize
    (can it be reduced to a quadratic or convex problem?).
  - Tell whether you need to do it repeatedly or only a few times
    (e.g., utilizing an interface to the NEOS solvers).
  - How many integer variables, binary or really integer, etc.
    (could you do your own branch-and-bound, e.g.)?

Providing as little information as above makes communicating difficult.

Hans Werner

P. S.:  The R-Forge project "Integer and Nonlinear Optimization in R (RINO)"
        will (hopefully) make some of those COIN-OR solvers available.

______________________________________________
[hidden email] 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.
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: non-linear integer optimization?

darckeen
This is an example of the type of problem, and how i'm currently using optim() to solve it.

mydata <- runif(500,-1,1)

myfunc <- function(p,d)
{
	print(p <- floor(p))
	ws <- function(i,n,x) sum(x[i-n+1]:x[i])
	ws1 <- c(rep(NA,p[1]-1),sapply(p[1]:NROW(d),ws,p[1],d))
	ws2 <- c(rep(NA,p[2]-1),sapply(p[2]:NROW(d),ws,p[2],d))
	ws3 <- c(rep(NA,p[3]-1),sapply(p[3]:NROW(d),ws,p[3],d))
	var(ws1+ws2+ws3,na.rm=TRUE)
}

opt <- optim(c(25,50,150),myfunc,method="L-BFGS-B",
		control=list(fnscale=-1,parscale=c(1,1,1),factr=1,ndeps=c(5,5,5)),
		lower=t(c(1,51,101)),upper=t(c(50,100,200)),d=mydata)

print(floor(opt$par))
print(myfunc(opt$par,mydata))

So the parameters to the function to be optimized are parameters to functions that only accept integer values.  All of the paramters to be optimized are integers that are subject to upper lower bound constraints.  This was the solution I came up with after checking CRAN, searching nabble etc.  

It runs but not very efficiently, and does not seem to really explore the sample space very well before focusing on a local minimum.  I also looked at the constrOptim function but I couldn't figure out how to implement two sided constraints with it.
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: non-linear integer optimization?

Hans W Borchers
darckeen <darckeen <at> hotmail.com> writes:

> This is an example of the type of problem, and how i'm currently using
> optim() to solve it.


I would classify this as an integer programming (IP) problem, it is not
even non-linear, as there are no continuous variables. Your approach with
optim() will not work, especially not with method 'L-BFGS-B' for numerical
optimization. Maybe it's worth to try method 'SANN'.

Integer programming needs special techniques. If you don't know more about
your function, it may boil down to an exhaustive discrete search that will
be slow anyway.

Hans Werner

Example: With

    set.seed(8232); mydata <- runif(500,-1,1)   # fix these parameters

the 'optim()' approach finds a minimum of 0.9887148 with "L-BFGS-B" and
0.9139314 with method "SANN", while the global minimum is 0.7360688 in your
constraint area. DEoptim (in package DEoptim) returns 0.750277. The minimum
is more difficult to find in this example as it appears on the boundary.


> mydata <- runif(500,-1,1)
>
> myfunc <- function(p,d)
> {
> print(p <- floor(p))
> ws <- function(i,n,x) sum(x[i-n+1]:x[i])
> ws1 <- c(rep(NA,p[1]-1),sapply(p[1]:NROW(d),ws,p[1],d))
> ws2 <- c(rep(NA,p[2]-1),sapply(p[2]:NROW(d),ws,p[2],d))
> ws3 <- c(rep(NA,p[3]-1),sapply(p[3]:NROW(d),ws,p[3],d))
> var(ws1+ws2+ws3,na.rm=TRUE)
> }
>
> opt <- optim(c(25,50,150),myfunc,method="L-BFGS-B",
> control=list(fnscale=-1,parscale=c(1,1,1),factr=1,ndeps=c(5,5,5)),
> lower=t(c(1,51,101)),upper=t(c(50,100,200)),d=mydata)
>
> print(floor(opt$par))
> print(myfunc(opt$par,mydata))
>
> So the parameters to the function to be optimized are parameters to
> functions that only accept integer values.  All of the paramters to be
> optimized are integers that are subject to upper lower bound constraints.
> This was the solution I came up with after checking CRAN, searching nabble
> etc.  
>
> It runs but not very efficiently, and does not seem to really explore the
> sample space very well before focusing on a local minimum.  I also looked at
> the constrOptim function but I couldn't figure out how to implement two
> sided constraints with it.

______________________________________________
[hidden email] 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.
Loading...