[R] Constrined dependent optimization.
Ravi Varadhan
RVaradhan at jhmi.edu
Thu Apr 2 17:57:52 CEST 2009
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
> > >> >>>
> > >> >>> ______________________________________________
> > >> >>> 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.-tp227
> > >> >> 72520p22782922.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.
> > >> >>
> > >> >
> > >>
> > >> ______________________________________________
> > >> 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.
> > >
> > >
> >
> > ______________________________________________
> > 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.
>
> ______________________________________________
> 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.
--
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.maican at handels.gu.se
------------------------------------
"Not everything that counts can be
counted, and not everything that can be counted counts."
--- Einstein ---
______________________________________________
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.
More information about the R-help
mailing list