Rearrange Rows Within Columns

[pepsibrandon]

[TABLE="width: 288"]
<colgroup><col width="64" style="width: 48pt;" span="6"> <tbody>[TR]
[TD="width: 64, bgcolor: transparent"]1
[/TD]
[TD="width: 64, bgcolor: transparent"]2[/TD]
[TD="width: 64, bgcolor: transparent"]3[/TD]
[TD="width: 64, bgcolor: transparent"]4[/TD]
[TD="width: 64, bgcolor: transparent"]5[/TD]
[TD="width: 64, bgcolor: transparent"]Total
[/TD]
[/TR]
[TR]
[TD="bgcolor: transparent"]685[/TD]
[TD="bgcolor: transparent"]1713[/TD]
[TD="bgcolor: transparent"]1477[/TD]
[TD="bgcolor: transparent"]1637[/TD]
[TD="bgcolor: transparent"]1885[/TD]
[TD="bgcolor: transparent"]7397[/TD]
[/TR]
[TR]
[TD="bgcolor: transparent"]1282[/TD]
[TD="bgcolor: transparent"]1998[/TD]
[TD="bgcolor: transparent"]596[/TD]
[TD="bgcolor: transparent"]1282[/TD]
[TD="bgcolor: transparent"]1705[/TD]
[TD="bgcolor: transparent"]6863[/TD]
[/TR]
[TR]
[TD="bgcolor: transparent"]817[/TD]
[TD="bgcolor: transparent"]2008[/TD]
[TD="bgcolor: transparent"]1720[/TD]
[TD="bgcolor: transparent"]1573[/TD]
[TD="bgcolor: transparent"]1997[/TD]
[TD="bgcolor: transparent"]8115[/TD]
[/TR]
[TR]
[TD="bgcolor: transparent"]1144[/TD]
[TD="bgcolor: transparent"]1526[/TD]
[TD="bgcolor: transparent"]2028[/TD]
[TD="bgcolor: transparent"]1947[/TD]
[TD="bgcolor: transparent"]2007[/TD]
[TD="bgcolor: transparent"]8652[/TD]
[/TR]
[TR]
[TD="bgcolor: transparent"]552[/TD]
[TD="bgcolor: transparent"]1299[/TD]
[TD="bgcolor: transparent"]1884[/TD]
[TD="bgcolor: transparent"]1964[/TD]
[TD="bgcolor: transparent"]0[/TD]
[TD="bgcolor: transparent"]5699[/TD]
[/TR]
[TR]
[TD="bgcolor: transparent"]1901[/TD]
[TD="bgcolor: transparent"]2117[/TD]
[TD="bgcolor: transparent"]1662[/TD]
[TD="bgcolor: transparent"]1640[/TD]
[TD="bgcolor: transparent"]0[/TD]
[TD="bgcolor: transparent"]7320[/TD]
[/TR]
[TR]
[TD="bgcolor: transparent"]1082[/TD]
[TD="bgcolor: transparent"]1703[/TD]
[TD="bgcolor: transparent"]1523[/TD]
[TD="bgcolor: transparent"]1475[/TD]
[TD="bgcolor: transparent"]0[/TD]
[TD="bgcolor: transparent"]5783[/TD]
[/TR]
[TR]
[TD="bgcolor: transparent"]1785[/TD]
[TD="bgcolor: transparent"]1979[/TD]
[TD="bgcolor: transparent"]1071[/TD]
[TD="bgcolor: transparent"]1020[/TD]
[TD="bgcolor: transparent"]0[/TD]
[TD="bgcolor: transparent"]5855[/TD]
[/TR]
[TR]
[TD="bgcolor: transparent"]1099[/TD]
[TD="bgcolor: transparent"]2023[/TD]
[TD="bgcolor: transparent"]1261[/TD]
[TD="bgcolor: transparent"]1977[/TD]
[TD="bgcolor: transparent"]0[/TD]
[TD="bgcolor: transparent"]6360[/TD]
[/TR]
[TR]
[TD="bgcolor: transparent"]1957[/TD]
[TD="bgcolor: transparent"]1174[/TD]
[TD="bgcolor: transparent"]952[/TD]
[TD="bgcolor: transparent"]2021[/TD]
[TD="bgcolor: transparent"]0[/TD]
[TD="bgcolor: transparent"]6104[/TD]
[/TR]
[TR]
[TD="bgcolor: transparent"]1960[/TD]
[TD="bgcolor: transparent"]1459[/TD]
[TD="bgcolor: transparent"]874[/TD]
[TD="bgcolor: transparent"]2002[/TD]
[TD="bgcolor: transparent"]0[/TD]
[TD="bgcolor: transparent"]6295[/TD]
[/TR]
[TR]
[TD="bgcolor: transparent"]1976[/TD]
[TD="bgcolor: transparent"]1618[/TD]
[TD="bgcolor: transparent"]1533[/TD]
[TD="bgcolor: transparent"]2068[/TD]
[TD="bgcolor: transparent"]0[/TD]
[TD="bgcolor: transparent"]7195[/TD]
[/TR]
[TR]
[TD="bgcolor: transparent"]1546[/TD]
[TD="bgcolor: transparent"]2067[/TD]
[TD="bgcolor: transparent"]1489[/TD]
[TD="bgcolor: transparent"]875[/TD]
[TD="bgcolor: transparent"]0[/TD]
[TD="bgcolor: transparent"]5977
[/TD]
[/TR]
</tbody>[/TABLE]

I'm working with the table above and would like to be able to rearrange the values within each column to give me the combination that has the totals as close as possible to each other. The values can move up/down within the columns but can't move from one column to another.

Thanks

 

[Jerry Sullivan]

Here's a clarification of what I think the OP is requesting.

As DSCfromCFA noted, the average of the totals is about 6,740, so the perfect solution would rearrange the numbers so that each row totaled 6,740.

The screenshot below shows the in the posted arrangement the first row totals 7397 which varies from 6740 by 657. The sum of all the variances is 10,209 and the maximum variance is the 4th row which totals 1912.

Excel 2016 (Windows) 32 bit
	A	B	C	D	E	F	G	H
2							Variance
3	1	2	3	4	5	Total	From Target
4	685	1,713	1,477	1,637	1,885	7,397	657
5	1,282	1,998	596	1,282	1,705	6,863	123
6	817	2,008	1,720	1,573	1,997	8,115	1,375
7	1,144	1,526	2,028	1,947	2,007	8,652	1,912
8	552	1,299	1,884	1,964	0	5,699	1,041
9	1,901	2,117	1,662	1,640	0	7,320	580
10	1,082	1,703	1,523	1,475	0	5,783	957
11	1,785	1,979	1,071	1,020	0	5,855	885
12	1,099	2,023	1,261	1,977	0	6,360	380
13	1,957	1,174	952	2,021	0	6,104	636
14	1,960	1,459	874	2,002	0	6,295	445
15	1,976	1,618	1,533	2,068	0	7,195	455
16	1,546	2,067	1,489	875	0	5,977	763
17							10,209	Sum
18					Target:	6,740	1,912	Max
Sheet1

If we exchange the positions of 2007 and 0 in column 5, the new sum of Variances from Target is 8,317 and the new Maximum variance is 1,375.

Excel 2016 (Windows) 32 bit
	A	B	C	D	E	F	G	H
23							Variance
24	1	2	3	4	5	Total	From Target
25	685	1,713	1,477	1,637	1,885	7,397	657
26	1,282	1,998	596	1,282	1,705	6,863	123
27	817	2,008	1,720	1,573	1,997	8,115	1,375
28	1,144	1,526	2,028	1,947	0	6,645	95
29	552	1,299	1,884	1,964	2,007	7,706	966
30	1,901	2,117	1,662	1,640	0	7,320	580
31	1,082	1,703	1,523	1,475	0	5,783	957
32	1,785	1,979	1,071	1,020	0	5,855	885
33	1,099	2,023	1,261	1,977	0	6,360	380
34	1,957	1,174	952	2,021	0	6,104	636
35	1,960	1,459	874	2,002	0	6,295	445
36	1,976	1,618	1,533	2,068	0	7,195	455
37	1,546	2,067	1,489	875	0	5,977	763
38							8,317	Sum
39					Target:	6,740	1,375	Max
Sheet1

The best solution can be found by brute force by trying all combinations however there are optimization approaches such a "Branch and Bound" that can greatly reduce the amount of combinations that need to be tested. https://en.wikipedia.org/wiki/Branch_and_bound

@pepsibrandon, please clarify, when you say that you want the totals to be as close as possible to each other, is the goal to minimize the Total of Variance from Target; or to minimize the value of the row with the Max variance?

 

[pepsibrandon]

The goal is to minimize the value of the row with the Max variance

 

[pepsibrandon]

To add some context if I had a Total Variance from target of 390 and was working with 13 rows I would rather have all 13 rows have a variance of 30 than have 11 rows have a variance of 0 and the remaining 2 rows have a variance of 195.

 

[MickG]

Try this Example file, based on your data :-
https://app.box.com/s/hgqnc8z6v6p7knt1op6ko963kmypvwei

 

[pepsibrandon]

MikeG thank you for the reply and the file. I ran the file and it gave me a best solution in which the difference between the maximum total and minimum is 1,417. If I manually move values around I can get these values to be much closer so I'm not sure where the disconnect is in the file and how it is choosing it's values. The table below is the solution it gave. Row 3 has the max total of 7,306. Row 8 has a total of 6,029. If I take the values for each of these rows from Column 3 and swap them row 3 total becomes 6,950 and row 8 total becomes 6,385 (just one example).

[TABLE="width: 303"]
<colgroup><col width="64" style="width: 48pt;" span="5"> <col width="84" style="width: 63pt; mso-width-source: userset; mso-width-alt: 3072;"> <tbody>[TR]
[TD="width: 64, bgcolor: white"]1[/TD]
[TD="width: 64, bgcolor: white"]2[/TD]
[TD="width: 64, bgcolor: white"]3[/TD]
[TD="width: 64, bgcolor: white"]4[/TD]
[TD="width: 64, bgcolor: white"]5[/TD]
[TD="width: 84, bgcolor: white"]Total[/TD]
[/TR]
[TR]
[TD="width: 64, bgcolor: #92D050"]1144[/TD]
[TD="width: 64, bgcolor: #92D050"]1979[/TD]
[TD="width: 64, bgcolor: #92D050"]1071[/TD]
[TD="width: 64, bgcolor: #92D050"]875[/TD]
[TD="width: 64, bgcolor: #92D050"]1885[/TD]
[TD="width: 84, bgcolor: yellow"]6954[/TD]
[/TR]
[TR]
[TD="width: 64, bgcolor: #92D050"]552[/TD]
[TD="width: 64, bgcolor: #92D050"]2023[/TD]
[TD="width: 64, bgcolor: #92D050"]1261[/TD]
[TD="width: 64, bgcolor: #92D050"]1637[/TD]
[TD="width: 64, bgcolor: #92D050"]1705[/TD]
[TD="width: 84, bgcolor: yellow"]7178[/TD]
[/TR]
[TR]
[TD="width: 64, bgcolor: #92D050"]1901[/TD]
[TD="width: 64, bgcolor: #92D050"]1174[/TD]
[TD="width: 64, bgcolor: #92D050"]952[/TD]
[TD="width: 64, bgcolor: #92D050"]1282[/TD]
[TD="width: 64, bgcolor: #92D050"]1997[/TD]
[TD="width: 84, bgcolor: yellow"]7306[/TD]
[/TR]
[TR]
[TD="width: 64, bgcolor: #92D050"]1082[/TD]
[TD="width: 64, bgcolor: #92D050"]1459[/TD]
[TD="width: 64, bgcolor: #92D050"]874[/TD]
[TD="width: 64, bgcolor: #92D050"]1573[/TD]
[TD="width: 64, bgcolor: #92D050"]2007[/TD]
[TD="width: 84, bgcolor: yellow"]6995[/TD]
[/TR]
[TR]
[TD="width: 64, bgcolor: #92D050"]1785[/TD]
[TD="width: 64, bgcolor: #92D050"]1618[/TD]
[TD="width: 64, bgcolor: #92D050"]1533[/TD]
[TD="width: 64, bgcolor: #92D050"]1947[/TD]
[TD="width: 64, bgcolor: #92D050"]0[/TD]
[TD="width: 84, bgcolor: yellow"]6883[/TD]
[/TR]
[TR]
[TD="width: 64, bgcolor: #92D050"]1099[/TD]
[TD="width: 64, bgcolor: #92D050"]2067[/TD]
[TD="width: 64, bgcolor: #92D050"]1489[/TD]
[TD="width: 64, bgcolor: #92D050"]1964[/TD]
[TD="width: 64, bgcolor: #92D050"]0[/TD]
[TD="width: 84, bgcolor: yellow"]6619[/TD]
[/TR]
[TR]
[TD="width: 64, bgcolor: #92D050"]1957[/TD]
[TD="width: 64, bgcolor: #92D050"]1713[/TD]
[TD="width: 64, bgcolor: #92D050"]1477[/TD]
[TD="width: 64, bgcolor: #92D050"]1640[/TD]
[TD="width: 64, bgcolor: #92D050"]0[/TD]
[TD="width: 84, bgcolor: yellow"]6787[/TD]
[/TR]
[TR]
[TD="width: 64, bgcolor: #92D050"]1960[/TD]
[TD="width: 64, bgcolor: #92D050"]1998[/TD]
[TD="width: 64, bgcolor: #92D050"]596[/TD]
[TD="width: 64, bgcolor: #92D050"]1475[/TD]
[TD="width: 64, bgcolor: #92D050"]0[/TD]
[TD="width: 84, bgcolor: yellow"]6029[/TD]
[/TR]
[TR]
[TD="width: 64, bgcolor: #92D050"]1976[/TD]
[TD="width: 64, bgcolor: #92D050"]2008[/TD]
[TD="width: 64, bgcolor: #92D050"]1720[/TD]
[TD="width: 64, bgcolor: #92D050"]1020[/TD]
[TD="width: 64, bgcolor: #92D050"]0[/TD]
[TD="width: 84, bgcolor: yellow"]6724[/TD]
[/TR]
[TR]
[TD="width: 64, bgcolor: #92D050"]1546[/TD]
[TD="width: 64, bgcolor: #92D050"]1526[/TD]
[TD="width: 64, bgcolor: #92D050"]2028[/TD]
[TD="width: 64, bgcolor: #92D050"]1977[/TD]
[TD="width: 64, bgcolor: #92D050"]0[/TD]
[TD="width: 84, bgcolor: yellow"]7077[/TD]
[/TR]
[TR]
[TD="width: 64, bgcolor: #92D050"]685[/TD]
[TD="width: 64, bgcolor: #92D050"]1299[/TD]
[TD="width: 64, bgcolor: #92D050"]1884[/TD]
[TD="width: 64, bgcolor: #92D050"]2021[/TD]
[TD="width: 64, bgcolor: #92D050"]0[/TD]
[TD="width: 84, bgcolor: yellow"]5889[/TD]
[/TR]
[TR]
[TD="width: 64, bgcolor: #92D050"]1282[/TD]
[TD="width: 64, bgcolor: #92D050"]2117[/TD]
[TD="width: 64, bgcolor: #92D050"]1662[/TD]
[TD="width: 64, bgcolor: #92D050"]2002[/TD]
[TD="width: 64, bgcolor: #92D050"]0[/TD]
[TD="width: 84, bgcolor: yellow"]7063[/TD]
[/TR]
[TR]
[TD="width: 64, bgcolor: #92D050"]817[/TD]
[TD="width: 64, bgcolor: #92D050"]1703[/TD]
[TD="width: 64, bgcolor: #92D050"]1523[/TD]
[TD="width: 64, bgcolor: #92D050"]2068[/TD]
[TD="width: 64, bgcolor: #92D050"]0[/TD]
[TD="width: 84, bgcolor: yellow"]6111[/TD]
[/TR]
</tbody>[/TABLE]

 

[MickG]

Sorry it does not work for you !!!
My code just loops each column one row at a time from top to bottom, with one column at a time taking the max and min at each step.
Sound like you want the permutations of each column, combined that with the permutations of each other column. That sound like a very, very big number.

 

[Jerry Sullivan]

Hi Mick, Yes, the brute force approach would require testing require 13! * 5! combinations which is about 740 billion trials.

I'm working on a branch and bound approach, but I'm still trying to wrap my head around a few steps to optimize that process.

Mick's example is using a definition of "totals to be as close as possible" that is slightly different than my interpretation of Brandon's clarification in Posts 12 and 13.

Mick was minimizing the difference between the highest and lowest row totals. I'm understanding the goal to be minimizing the largest difference between any single row and the average of all rows. That distinction is significant when trying to optimize an algorithm, since the latter only requires testing one row against the best candidate total.

Brandon, does this latter definition work for you?
"Minimize the largest difference between any single row and the average of all rows"

 

[pepsibrandon]

Yes, that definition works for me.