[R] Constrined dependent optimization.

[Hans W. Borchers]

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,  <rkevinburton at 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 at 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.