Actually, one can use lpSolve to find a solution to your example. To be more precise, it would be necessary to solve a sequence of linear *integer* programs. The first one would be:
max f(x) subject to x >= 0 x <= 100 sum(x) = 100. >From this, one would learn the optimal position of the number 100 (coefficient 50). Afterwards, one would remove the coefficient 50 from the objective function, and the constraints would be: x >= 0 x <= 99 sum(x) = 99. The optimal position for the number 99 would be returned by lpSolve. And so on. 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.-tp22772520p22782922.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.
