Constrined dependent optimization.

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: rvaradhan at jhmi.edu

Webpage:
http://www.jhsph.edu/agingandhealth/People/Faculty/Varadhan.html

 

----------------------------------------------------------------------------
--------


-----Original Message-----
From: r-help-bounces at r-project.org
[mailto:r-help-bounces at r-project.org] On Behalf Of Florin Maican
Sent: Thursday, April 02, 2009 11:33 AM
To: r-help at 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
<rkevinburton at 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 <phhs80 at 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,  <rkevinburton at 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 <phhs80 at 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 <phhs80 at 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 
<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

--
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.