[R] Constrined dependent optimization.

[Paul Smith]

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
<hwborchers at 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,  <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.
>
> ______________________________________________
> 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.
>