Re: Simple n-tuple problem - with no simple solution
- To: mathgroup at smc.vnet.net
- Subject: [mg116041] Re: Simple n-tuple problem - with no simple solution
- From: DrMajorBob <btreat1 at austin.rr.com>
- Date: Sat, 29 Jan 2011 19:43:47 -0500 (EST)
In that case, for large n you may need to generate all solutions in the
compact form, then generate the rearrangements one at a time.
Better yet, you can use LinearProgramming (not Solve), to maximize any
linear function of the percentages. If total return is linear in the
percentages, you can go to the optimum overall solution in one go, without
looking at the other 10 million.
With a bit more work, you can also use LP to solve non-linear maximization
problems by linearizing locally and searching iteratively. Again, you
could reach optimum without looking at all 10 million rearrangements.
Bobby
On Sat, 29 Jan 2011 04:26:17 -0600, Don <donabc at comcast.net> wrote:
> On Jan 27, 12:39 am, DrMajorBob <btre... at austin.rr.com> wrote:
>> "Therefore, the time it takes to generate all possible states
>> is prohibitive for large n (n > 10) and searches through
>> such a voluminous state space is not feasible."
>>
>> Not true. The number of distinct solutions never exceeds 627. Those
>> millions of others are only rearrangements.
>>
>> Unless there's some reason the order matters? You haven't mentioned a
>> reason.
>>
>> Bobby
>>
>>
>>
>>
>>
>> On Wed, 26 Jan 2011 04:06:07 -0600, Don <don... at comcast.net> wrote:
>> > On Jan 24, 2:22 am, DrMajorBob <btre... at austin.rr.com> wrote:
>> >> Brilliant!
>>
>> >> Bobby
>>
>> >> On Sun, 23 Jan 2011 16:32:03 -0600, Dana DeLouis <dana.... at gmail.com>
>> >> wrote:
>>
>> >> > On Jan 22, 3:23 am, DrMajorBob <btre... at austin.rr.com> wrote:
>> >> >> Here are some timings.
>>
>> >> >> n = 5; addends = Rationalize@Range[0, 1.0, 0.05];
>> >> >> Length@t1[addends, n] // Timing
>>
>> >> >> {1.44372, 192}
>> >> >> {23.6318, 192}
>>
>> >> >> n = 7;
>> >> >> Length@t1[addends, n] // Timing
>> >> >> {1.85135, 364}
>>
>> >> >> n = 9;
>> >> >> Length@t1[addends, n] // Timing
>> >> >> {2.04216, 488}
>>
>> >> >> The Compositions method rendered Mathematica unresponsive at n = =
> 10,
>> >> but
>> >> >> here's n = 25 for my approach:
>> >> >> n = 25;
>> >> >> Length@t1[addends, n] // Timing
>>
>> >> >> {2.57619, 627}
>>
>> >> >> I'd say Solve (which must use Integer Linear Programming for
>> this) =
> is
>> >> >> the
>> >> >> way to go.
>>
>> >> > Hi. Just some thoughts. With the smallest unit 1, the most n =
> can be
>> >> > is 20.
>>
>> >> > If we assume that solution sizes smaller than n have implied 0's, =
>
>> >> then. ..
>>
>> >> > IntegerPartitions[20,5]//Length //Timing
>> >> > {0.000085,192}
>>
>> >> > IntegerPartitions[20,20]//Length //Timing
>> >> > {0.000244,627}
>>
>> >> > If we want to look at each exact n, then the function uses {n}
>>
>> >> > Table[Length[IntegerPartitions[20,{j}]],{j,20}]
>> >> > {1,10,33,64,84,90,82,70,54,42,30,22,15,11,7,5,3,2,1,1}
>>
>> >> > Accumulate[%]
>> >> > =
>>
>> >>
>> {1,11,44,108,192,282,364,434,488,530,560,582,597,608,615,620,623,625,6=
> 26,62=AD=AD7}
>>
>> >> > By adding them up, we see that for n=5, we get the 192. For n=
> =7, 364,
>> >> > etc.
>>
>> >> > If the question was "Count all possible combinations" as in the
>> last
>> >> > total above, then one additional way...
>>
>> >> > Timing[SeriesCoefficient[
>> >> > 1/Times @@ (1 - n^#1 & ) /@
>> >> > Range[20], {n, 0, 20}]]
>>
>> >> > {0.0003, 627}
>>
>> >> > = = = = = = = = = =
>> >> > HTH : >)
>> >> > Dana DeLouis
>>
>> >> --
>> >> DrMajor... at yahoo.com- Hide quoted text -
>>
>> >> - Show quoted text -
>>
>> > Thank you all for the in-depth analysis
>> > of this problem.
>> > The proposed solutions do solve the problem of
>> > memory overflow as opposed to the simple
>> > solution of generating all possible tuples and only then Selecting out
>> > those whose elements sum to 1.
>>
>> > I should add perhaps a little context to the original problem.
>> > It is part of an optimization problem.
>> > All the n-tuples (with the requirement
>> > that all elements of any given tuple add to 1.0 - as explained in
>> > the original problem definition) constitute
>> > essentially the state space
>> > that has to be searched ( in some clever way) to find
>> > the maximum value of an objective function subject
>> > to well defined independent constraints.
>>
>> > The hope was that
>> > the requirement of summing to one would inhibit the
>> > state space from growing too fast for "reasonable"
>> > sizes of n ("reasonable" being about a max of 15 for
>> > the current application). Many of the solutions
>> > proposed show that that is not feasible: the state space
>> > grows very rapidly from about a 5-tuple to larger values of n up to
>> > 15.
>> > (A person more knowledgeable than I in combinatorics might have seen
>> > this coming.)
>> > Using the NumberOfCompositons function
>> > from the Combinatorica package (special thanks to those
>> > who introduced me to this package) shows how quickly
>> > the state space grows.
>>
>> > Needs["Combinatorica`"] // Quiet
>> > max = 15;
>> > For[n = 5, n <= max, n++,
>> > Print["n = ",n, " " , AbsoluteTiming[c2b = 0.05 Compositions[=
> 20,
>> > n] ;] ]
>> > ]
>>
>> > Therefore, the time it takes to generate all possible states
>> > is prohibitive for large n (n > 10) and searches through
>> > such a voluminous state space is not feasible.
>> > A heuristic is being worked on that will, hopefully, reduce
>> > the size of the state space while not sacrificing an optimum
>> > solution for the objective function. Thank you again for all your
>> > input into this.
>>
>> --
>> DrMajor... at yahoo.com- Hide quoted text -
>>
>> - Show quoted text -
>
>
> I didn't want to burden people with the details of the application ...
> but to answer
> the rearrangements question ... Rearrangements are very important.
> The values of the n-tuples (which always sum to one)
> are percentages. The first element of the n-tuple is the percentage
> of asset #1 that goes to make up a portfolio of financial assets.
> The second element of the n-tuple is the percentage for asset
> #2 as part of the portfolio, etc. How those percentages
> are distributed across assets is crucially important
> in determining properties of the portfolio like Total Return
> and the degree of Risk (represented by multiple
> risk functions) of the portfolio. In fact, the optimization
> problem is to determine just which arrangement
> maximizes an objective function while minimizing other
> functions such as overall portfolio risk. And the functions
> have no nice properties that can be exploited
> to find the solution like convexity, continuity etc.
>
>
>
--
DrMajorBob at yahoo.com