Ravi, You are right. I did not specified the type of problem: large problems with smooth functions and not large-scale discrete problems. I am sorry for confusion. For non-smooth functions, I can suggest subplex. http://cran.r-project.org/web/packages/subplex/index.html
Florin On Thu, 2 Apr 2009 11:57:52 -0400 "Ravi Varadhan" <rvarad...@jhmi.edu> wrote: > Florin, > > Please allow me to clarify some issues: > > Many, if not most, problems in science involve optimization in one > form or another. Consequently, "optimization" is a vast area. There > are many different types of optimization. Here is a one way to > classify optimzation problems (neither mutually exclusive nor > exhaustive): > > - smooth versus non-smooth > - unconstrained versus constrained > - linear versus non-linear > - real & continuous versus discrete, integer or mixed (or > combinatorial problems) > - scalar versus multi-objective > - small versus large-scale > > Given such vastness and diversity of optimization problems, it is > important that one chooses an appropriate optimization tool for one's > particular problem. I am not sure what kind of optimization problem > that you were trying to solve, but the packages that you mentioned > can only deal with real, smooth, box-constrained optimization (except > for optim(), whose Nelder-Mead and SANN can handle real, non-smooth > problems, but with no constraints). Large-scale discrete problems, > such as binning problems or travelling salesman problem are > challenging, and, as far as I know, R does not have strong > capabilties in this area. > > Ravi. > > > ---------------------------------------------------------------------------- > ------- > > Ravi Varadhan, Ph.D. > > Assistant Professor, The Center on Aging and Health > > Division of Geriatric Medicine and Gerontology > > Johns Hopkins University > > Ph: (410) 502-2619 > > Fax: (410) 614-9625 > > Email: rvarad...@jhmi.edu > > Webpage: > http://www.jhsph.edu/agingandhealth/People/Faculty/Varadhan.html > > > > ---------------------------------------------------------------------------- > -------- > > > -----Original Message----- > From: r-help-boun...@r-project.org > [mailto:r-help-boun...@r-project.org] On Behalf Of Florin Maican > Sent: Thursday, April 02, 2009 11:33 AM > To: r-help@r-project.org > Subject: Re: [R] Constrined dependent optimization. > > > I tried many optimizers in R on my large scale optimization > problems. I am not satisfied with their speed on large op problems. > But you may try in this order > > nlminb > > ucminf ucminf package > > spq BB package > > optim > > Is here someone that try to port Ipopt in R? > > https://projects.coin-or.org/Ipopt > > > Florin > > > > On Thu, 2 Apr 2009 7:49:45 -0700 > <rkevinbur...@charter.net> wrote: > > > Sorry I sent a description of the function I was trying to minimize > > but I must not have sent it to this group (and you). Hopefully with > > this clearer description of my problem you might have some > > suggestions. > > > > It is basically a warehouse placement problem. You have a warehouse > > that has many items each placed in a certain bin (the "real" > > warehouse has about 20,000 of these bins, hence the large number of > > variables that I want to input to optimize). Now assume that an > > order comes in for three items A, B, and C. In the worst case A > > will be on one end of the warehouse, B in the middle and C on the > > other end of the warehouse. The "work" involved in getting these > > items to fulfill this order is roughly proportional to the distance > > from A to B plus the distance from B to C (assuming the absolute > > positions are sorted). So the cost for fulfilling this order is > > this distance. In the ideal world A, B, and C would be right next > > to each other and the cost/distance would be minimized. So the > > function I want to minimize would be placing these 20,000 items in > > such a way so that the minimum "work" is involved in fulfilling the > > orders for the past month or two. Clearer? > > > > I can see that I may need to cut back on the variables 20,000 is > > probably too many. Maybe I can take the top 1,000 or so. I just am > > not sure of the packages available what to reasonably expect. I > > would like this optimization to complete in a reasonable amount of > > time (less than a few days). I have heard that SANN is slower than > > other optimization methods but it does have the feature of > > supplying a "gradient" as you pointed out. Are there other packages > > out there that might be better suited to such a large scale > > optimizaiton? > > > > Thanks again. > > > > Kevin > > ---- Paul Smith <phh...@gmail.com> wrote: > > > As I told you before, without knowing the definition of your > > > function f, one cannot help much. > > > > > > Paul > > > > > > > > > On Wed, Apr 1, 2009 at 3:15 PM, <rkevinbur...@charter.net> wrote: > > > > Thank you I had not considered using "gradient" in this fashion. > > > > Now as an add on question. You (an others) have suggested using > > > > SANN. Does your answer change if instead of 100 "variables" or > > > > bins there are 20,000? From the documentation L-BFGS-B is > > > > designed for a large number of variables. But maybe SANN can > > > > handle this as well. > > > > > > > > Kevin > > > > > > > > ---- Paul Smith <phh...@gmail.com> wrote: > > > >> Apparently, the convergence is faster if one uses this new swap > > > >> function: > > > >> > > > >> swapfun <- function(x,N=100) { > > > >> loc <- > > > >> c(sample(1:(N/2),size=1,replace=FALSE),sample((N/2):100,1)) tmp > > > >> <- x[loc[1]] x[loc[1]] <- x[loc[2]] > > > >> x[loc[2]] <- tmp > > > >> x > > > >> } > > > >> > > > >> It seems that within 20 millions of iterations, one gets the > > > >> exact optimal solution, which does not take too long. > > > >> > > > >> Paul > > > >> > > > >> > > > >> On Mon, Mar 30, 2009 at 5:11 PM, Paul Smith <phh...@gmail.com> > > > >> wrote: > > > >> > Optim with SANN also solves your example: > > > >> > > > > >> > ------------------------------------------- > > > >> > > > > >> > f <- function(x) sum(c(1:50,50:1)*x) > > > >> > > > > >> > swapfun <- function(x,N=100) { > > > >> > loc <- sample(N,size=2,replace=FALSE) > > > >> > tmp <- x[loc[1]] > > > >> > x[loc[1]] <- x[loc[2]] > > > >> > x[loc[2]] <- tmp > > > >> > x > > > >> > } > > > >> > > > > >> > N <- 100 > > > >> > > > > >> > opt1 <- > > > >> > optim(fn=f,par=sample(1:N,N),gr=swapfun,method="SANN",control=l > > > >> > ist(maxit=50000,fnscale=-1,trace=10)) > > > >> > opt1$par opt1$value > > > >> > > > > >> > ------------------------------------------- > > > >> > > > > >> > We need to specify a large number of iterations to get the > > > >> > optimal solution. The objective function at the optimum is > > > >> > 170425, and one gets a close value with optim and SANN. > > > >> > > > > >> > Paul > > > >> > > > > >> > > > > >> > On Mon, Mar 30, 2009 at 2:22 PM, Hans W. Borchers > > > >> > <hwborch...@googlemail.com> wrote: > > > >> >> > > > >> >> Image you want to minimize the following linear function > > > >> >> > > > >> >> f <- function(x) sum( c(1:50, 50:1) * x / (50*51) ) > > > >> >> > > > >> >> on the set of all permutations of the numbers 1,..., 100. > > > >> >> > > > >> >> I wonder how will you do that with lpSolve? I would simply > > > >> >> order the coefficients and then sort the numbers 1,...,100 > > > >> >> accordingly. > > > >> >> > > > >> >> I am also wondering how optim with "SANN" could be applied > > > >> >> here. > > > >> >> > > > >> >> As this is a problem in the area of discrete optimization > > > >> >> resp. constraint programming, I propose to use an > > > >> >> appropriate program here such as the free software Bprolog. > > > >> >> I would be interested to learn what others propose. > > > >> >> > > > >> >> Of course, if we don't know anything about the function f > > > >> >> then it amounts to an exhaustive search on the 100! > > > >> >> permutations -- probably not a feasible job. > > > >> >> > > > >> >> Regards, Hans Werner > > > >> >> > > > >> >> > > > >> >> > > > >> >> Paul Smith wrote: > > > >> >>> > > > >> >>> On Sun, Mar 29, 2009 at 9:45 PM, > > > >> >>> <rkevinbur...@charter.net> wrote: > > > >> >>>> I have an optimization question that I was hoping to get > > > >> >>>> some suggestions on how best to go about sovling it. I > > > >> >>>> would think there is probably a package that addresses > > > >> >>>> this problem. > > > >> >>>> > > > >> >>>> This is an ordering optimzation problem. Best to describe > > > >> >>>> it with a simple example. Say I have 100 "bins" each with > > > >> >>>> a ball in it numbered from 1 to 100. Each bin can only > > > >> >>>> hold one ball. This optimization is that I have a > > > >> >>>> function 'f' that this array of bins and returns a > > > >> >>>> number. The number returned from f(1,2,3,4....) would > > > >> >>>> return a different number from that of f(2,1,3,4....). > > > >> >>>> The optimization is finding the optimum order of these > > > >> >>>> balls so as to produce a minimum value from 'f'.I cannot > > > >> >>>> use the regular 'optim' algorithms because a) the values > > > >> >>>> are discrete, and b) the values are dependent ie. when > > > >> >>>> the "variable" representing the bin location is changed > > > >> >>>> (in this example a new ball is put there) the existing > > > >> >>>> ball will need to be moved to another bin (probably > > > >> >>>> swapping positions), and c) each "variable" is > > > >> >>>> constrained, in the example above the only allowable > > > >> >>>> values are integers from 1-100. So the problem becomes > > > >> >>>> finding the optimum order of the "balls". > > > >> >>>> > > > >> >>>> Any suggestions? > > > >> >>> > > > >> >>> If your function f is linear, then you can use lpSolve. > > > >> >>> > > > >> >>> Paul > > > >> >>> > > > >> >>> ______________________________________________ > > > >> >>> R-help@r-project.org 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. > > > >> >>> > > > >> >>> > > > >> >> > > > >> >> -- > > > >> >> View this message in context: > > > >> >> http://www.nabble.com/Constrined-dependent-optimization.-tp227 > > > >> >> 72520p22782922.html Sent from the R help mailing list > > > >> >> archive at Nabble.com. > > > >> >> > > > >> >> ______________________________________________ > > > >> >> R-help@r-project.org 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. > > > >> >> > > > >> > > > > >> > > > >> ______________________________________________ > > > >> R-help@r-project.org 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. > > > > > > > > > > > > > > ______________________________________________ > > > R-help@r-project.org 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. > > > > ______________________________________________ > > R-help@r-project.org 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. > > -- Florin G. Maican ================================== Ph.D. candidate, Department of Economics, School of Business, Economics and Law, Gothenburg University, Sweden ----------------------------------- P.O. Box 640 SE-405 30, Gothenburg, Sweden Mobil: +46 76 235 3039 Phone: +46 31 786 4866 Fax: +46 31 786 4154 Home Page: http://maicanfg.googlepages.com/index.html E-mail: florin.mai...@handels.gu.se ------------------------------------ "Not everything that counts can be counted, and not everything that can be counted counts." --- Einstein --- ______________________________________________ R-help@r-project.org 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.
