Optimization Problem

[learningtoride]

I have multiple indices with each containing a pool of symbols. Some of these symbols will be unique to the one index and other symbols may be contained in multiple indices. The objective is separate the indices into multiple tranches(the # of tranches would be an adjustable variable) so that to minimize the # of unique symbols contained in each tranche.

So here would be an simple data set example.

<TABLE style="WIDTH: 96pt; BORDER-COLLAPSE: collapse" border=0 cellSpacing=0 cellPadding=0 width=128><COLGROUP><COL style="WIDTH: 48pt" span=2 width=64><TBODY><TR style="HEIGHT: 15pt" height=20><TD style="BORDER-BOTTOM: #ece9d8; BORDER-LEFT: #ece9d8; BACKGROUND-COLOR: transparent; WIDTH: 48pt; HEIGHT: 15pt; BORDER-TOP: #ece9d8; BORDER-RIGHT: #ece9d8" height=20 width=64># of Tranches</TD><TD style="BORDER-BOTTOM: #ece9d8; BORDER-LEFT: #ece9d8; BACKGROUND-COLOR: transparent; WIDTH: 48pt; BORDER-TOP: #ece9d8; BORDER-RIGHT: #ece9d8" width=64 align=right>2</TD></TR><TR style="HEIGHT: 15pt" height=20><TD style="BORDER-BOTTOM: #ece9d8; BORDER-LEFT: #ece9d8; BACKGROUND-COLOR: transparent; HEIGHT: 15pt; BORDER-TOP: #ece9d8; BORDER-RIGHT: #ece9d8" height=20></TD><TD style="BORDER-BOTTOM: #ece9d8; BORDER-LEFT: #ece9d8; BACKGROUND-COLOR: transparent; BORDER-TOP: #ece9d8; BORDER-RIGHT: #ece9d8"></TD></TR><TR style="HEIGHT: 15pt" height=20><TD style="BORDER-BOTTOM: #ece9d8; BORDER-LEFT: #ece9d8; BACKGROUND-COLOR: transparent; HEIGHT: 15pt; BORDER-TOP: #ece9d8; BORDER-RIGHT: #ece9d8" height=20>Indice</TD><TD style="BORDER-BOTTOM: #ece9d8; BORDER-LEFT: #ece9d8; BACKGROUND-COLOR: transparent; BORDER-TOP: #ece9d8; BORDER-RIGHT: #ece9d8">Symbol</TD></TR><TR style="HEIGHT: 15pt" height=20><TD style="BORDER-BOTTOM: #ece9d8; BORDER-LEFT: #ece9d8; BACKGROUND-COLOR: transparent; HEIGHT: 15pt; BORDER-TOP: #ece9d8; BORDER-RIGHT: #ece9d8" height=20>A</TD><TD style="BORDER-BOTTOM: #ece9d8; BORDER-LEFT: #ece9d8; BACKGROUND-COLOR: transparent; BORDER-TOP: #ece9d8; BORDER-RIGHT: #ece9d8" align=right>1</TD></TR><TR style="HEIGHT: 15pt" height=20><TD style="BORDER-BOTTOM: #ece9d8; BORDER-LEFT: #ece9d8; BACKGROUND-COLOR: transparent; HEIGHT: 15pt; BORDER-TOP: #ece9d8; BORDER-RIGHT: #ece9d8" height=20>A</TD><TD style="BORDER-BOTTOM: #ece9d8; BORDER-LEFT: #ece9d8; BACKGROUND-COLOR: transparent; BORDER-TOP: #ece9d8; BORDER-RIGHT: #ece9d8" align=right>2</TD></TR><TR style="HEIGHT: 15pt" height=20><TD style="BORDER-BOTTOM: #ece9d8; BORDER-LEFT: #ece9d8; BACKGROUND-COLOR: transparent; HEIGHT: 15pt; BORDER-TOP: #ece9d8; BORDER-RIGHT: #ece9d8" height=20>B</TD><TD style="BORDER-BOTTOM: #ece9d8; BORDER-LEFT: #ece9d8; BACKGROUND-COLOR: transparent; BORDER-TOP: #ece9d8; BORDER-RIGHT: #ece9d8" align=right>1</TD></TR><TR style="HEIGHT: 15pt" height=20><TD style="BORDER-BOTTOM: #ece9d8; BORDER-LEFT: #ece9d8; BACKGROUND-COLOR: transparent; HEIGHT: 15pt; BORDER-TOP: #ece9d8; BORDER-RIGHT: #ece9d8" height=20>B</TD><TD style="BORDER-BOTTOM: #ece9d8; BORDER-LEFT: #ece9d8; BACKGROUND-COLOR: transparent; BORDER-TOP: #ece9d8; BORDER-RIGHT: #ece9d8" align=right>3</TD></TR><TR style="HEIGHT: 15pt" height=20><TD style="BORDER-BOTTOM: #ece9d8; BORDER-LEFT: #ece9d8; BACKGROUND-COLOR: transparent; HEIGHT: 15pt; BORDER-TOP: #ece9d8; BORDER-RIGHT: #ece9d8" height=20>C</TD><TD style="BORDER-BOTTOM: #ece9d8; BORDER-LEFT: #ece9d8; BACKGROUND-COLOR: transparent; BORDER-TOP: #ece9d8; BORDER-RIGHT: #ece9d8" align=right>3</TD></TR><TR style="HEIGHT: 15pt" height=20><TD style="BORDER-BOTTOM: #ece9d8; BORDER-LEFT: #ece9d8; BACKGROUND-COLOR: transparent; HEIGHT: 15pt; BORDER-TOP: #ece9d8; BORDER-RIGHT: #ece9d8" height=20>C</TD><TD style="BORDER-BOTTOM: #ece9d8; BORDER-LEFT: #ece9d8; BACKGROUND-COLOR: transparent; BORDER-TOP: #ece9d8; BORDER-RIGHT: #ece9d8" align=right>4</TD></TR><TR style="HEIGHT: 15pt" height=20><TD style="BORDER-BOTTOM: #ece9d8; BORDER-LEFT: #ece9d8; BACKGROUND-COLOR: transparent; HEIGHT: 15pt; BORDER-TOP: #ece9d8; BORDER-RIGHT: #ece9d8" height=20>D</TD><TD style="BORDER-BOTTOM: #ece9d8; BORDER-LEFT: #ece9d8; BACKGROUND-COLOR: transparent; BORDER-TOP: #ece9d8; BORDER-RIGHT: #ece9d8" align=right>4</TD></TR><TR style="HEIGHT: 15pt" height=20><TD style="BORDER-BOTTOM: #ece9d8; BORDER-LEFT: #ece9d8; BACKGROUND-COLOR: transparent; HEIGHT: 15pt; BORDER-TOP: #ece9d8; BORDER-RIGHT: #ece9d8" height=20>D</TD><TD style="BORDER-BOTTOM: #ece9d8; BORDER-LEFT: #ece9d8; BACKGROUND-COLOR: transparent; BORDER-TOP: #ece9d8; BORDER-RIGHT: #ece9d8" align=right>5</TD></TR></TBODY></TABLE>

How can I automate this in excel to get Pool 1 has Indice A and B, Pool 2 has Indice C and D. I've Been pulling my hair out trying to figure this out. Much Thanks

 

[VoG]

Try a Pivot Table

 

[learningtoride]

I tried a pivot table but I don't believe that will work since the data must be analyzed by brute force or some other method to sort the indices into tranches

 

[shg]

How many indices, symbols, and tranches are there in a typical example of the problem?

 

[learningtoride]

In the actual sheet there are about 300 indexes and 60,000 symbols that I want to divide up amongst several computers(the tranches in this example).

 

[shg]

That's way beyond computationally impractical. With four tranches, then ...

If you had 4 indices, they could only be divided in one way: {1}{2}{3}{4} (one to each tranch)

If you had 5 indices, they could be divided in 10 ways:

{1,2} {3} {4} {5}
{1,3} {2} {4} {5}
{1} {2,3} {4} {5}
{1,4} {2} {3} {5}
{1} {2,4} {3} {5}
{1} {2} {3,4} {5}
{1,5} {2} {3} {4}
{1} {2,5} {3} {4}
{1} {2} {3,5} {4}
{1} {2} {3} {4,5}

If you had 6: 65 different ways.

7: 350 ways

8: 1,701 ways

9: 7,770 ways

10: 34,105 ways

...

27: 749,329,038,535,350 ways

(See http://oeis.org/A000453)

It's probably possible to do some branch-and-bound or annealing algorithm for an approximate solution. Brute force won't get remotely close.

 

[learningtoride]

Thanks shg, your comments have been greatly appreciated.