Rearrange Rows Within Columns

[pepsibrandon]

1	2	3	4	5	Total
685	1713	1477	1637	1885	7397
1282	1998	596	1282	1705	6863
817	2008	1720	1573	1997	8115
1144	1526	2028	1947	2007	8652
552	1299	1884	1964	0	5699
1901	2117	1662	1640	0	7320
1082	1703	1523	1475	0	5783
1785	1979	1071	1020	0	5855
1099	2023	1261	1977	0	6360
1957	1174	952	2021	0	6104
1960	1459	874	2002	0	6295
1976	1618	1533	2068	0	7195
1546	2067	1489	875	0	5977

<colgroup><col width="64" style="width: 48pt;" span="6"> <tbody> </tbody>

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).

1	2	3	4	5	Total
1144	1979	1071	875	1885	6954
552	2023	1261	1637	1705	7178
1901	1174	952	1282	1997	7306
1082	1459	874	1573	2007	6995
1785	1618	1533	1947	0	6883
1099	2067	1489	1964	0	6619
1957	1713	1477	1640	0	6787
1960	1998	596	1475	0	6029
1976	2008	1720	1020	0	6724
1546	1526	2028	1977	0	7077
685	1299	1884	2021	0	5889
1282	2117	1662	2002	0	7063
817	1703	1523	2068	0	6111

<colgroup><col width="64" style="width: 48pt;" span="5"> <col width="84" style="width: 63pt; mso-width-source: userset; mso-width-alt: 3072;"> <tbody> </tbody>

 

[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.