[R] Constrined dependent optimization.
Florin Maican
florin.maican at handels.gu.se
Thu Apr 2 20:54:08 CEST 2009
Ravi,
You are right. I did not specified the type of problem:
large problems with smooth functions and not large-scale discrete
problems. I am sorry for confusion. For non-smooth
functions, I can suggest subplex.
http://cran.r-project.org/web/packages/subplex/index.html
Florin
On Thu, 2 Apr 2009 11:57:52 -0400
"Ravi Varadhan" <RVaradhan at jhmi.edu> wrote:
> 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 ---
More information about the R-help
mailing list