Challenging Problem

[jfish1288]

I have a 24 by 11 matrix of numbers. I would like to determine the largest sum that can be created from 24 of these numbers given a set of constraints.

For example only 1 number can and must be chosen from a each row, and at least 1 number must be chosen from each column.

I would like to further constrain it to 2 numbers from column 1, 3 from column 2, 2 from column 3 etc.

The data is descending within the columns, but not rows. I am not sure how to go about this, any thoughts?

 

[tweedle]

Q: The 24 x 11: is that 24 columns or 24 rows?

The straight forward solution appears to be to MAX() along the '24 axis' and SUM() the MAXes. [I'm sure there's a fancy array formula to do that in 1 cell]

The constraints presented appear to be contradictory to the point of improbable if not impossible.

from 24 of these numbers
...only 1 number can and must be chosen from a each row

Possibly further explanation would assist us. Are these different scenarios?

to further constrain it to 2 numbers from column 1, 3 from column 2, 2 from column 3 etc.

Was that suppose to be 4 from column 3 ???

 

[jfish1288]

It was originally 24 rows by 11 columns, but I have condensed it tow 14 rows by 6 columns. Here is the data:

<table border="0" cellpadding="0" cellspacing="0" width="384"><colgroup><col style="width:48pt" span="6" width="64"> </colgroup><tbody><tr style="height:12.75pt" height="17"> <td class="xl22" style="height:12.75pt; width:48pt" align="right" height="17" width="64">298</td> <td class="xl22" style="width:48pt" align="right" width="64">260</td> <td class="xl22" style="width:48pt" align="right" width="64">223</td> <td class="xl22" style="width:48pt" align="right" width="64">180</td> <td class="xl22" style="width:48pt" align="right" width="64">199</td> <td class="xl22" style="width:48pt" align="right" width="64">148</td> </tr> <tr style="height:12.75pt" height="17"> <td class="xl22" style="height:12.75pt" align="right" height="17">279</td> <td class="xl22" align="right">217</td> <td class="xl22" align="right">207</td> <td class="xl22" align="right">180</td> <td class="xl22" align="right">199</td> <td class="xl22" align="right">148</td> </tr> <tr style="height:12.75pt" height="17"> <td class="xl22" style="height:12.75pt" align="right" height="17">257</td> <td class="xl22" align="right">205</td> <td class="xl22" align="right">182</td> <td class="xl22" align="right">180</td> <td class="xl22" align="right">199</td> <td class="xl22" align="right">148</td> </tr> <tr style="height:12.75pt" height="17"> <td class="xl22" style="height:12.75pt" align="right" height="17">253</td> <td class="xl22" align="right">177</td> <td class="xl22" align="right">171</td> <td class="xl22" align="right">165</td> <td class="xl22" align="right">199</td> <td class="xl22" align="right">148</td> </tr> <tr style="height:12.75pt" height="17"> <td class="xl22" style="height:12.75pt" align="right" height="17">249</td> <td class="xl22" align="right">173</td> <td class="xl22" align="right">155</td> <td class="xl22" align="right">163</td> <td class="xl22" align="right">199</td> <td class="xl22" align="right">148</td> </tr> <tr style="height:12.75pt" height="17"> <td class="xl22" style="height:12.75pt" align="right" height="17">244</td> <td class="xl22" align="right">161</td> <td class="xl22" align="right">146</td> <td class="xl22" align="right">148</td> <td class="xl22" align="right">199</td> <td class="xl22" align="right">148</td> </tr> <tr style="height:12.75pt" height="17"> <td class="xl22" style="height:12.75pt" align="right" height="17">234</td> <td class="xl22" align="right">150</td> <td class="xl22" align="right">130</td> <td class="xl22" align="right">136</td> <td class="xl22" align="right">192</td> <td class="xl22" align="right">148</td> </tr> <tr style="height:12.75pt" height="17"> <td class="xl22" style="height:12.75pt" align="right" height="17">232</td> <td class="xl22" align="right">141</td> <td class="xl22" align="right">127</td> <td class="xl22" align="right">124</td> <td class="xl22" align="right">159</td> <td class="xl22" align="right">148</td> </tr> <tr style="height:12.75pt" height="17"> <td class="xl22" style="height:12.75pt" align="right" height="17">214</td> <td class="xl22" align="right">127</td> <td class="xl22" align="right">122</td> <td class="xl22" align="right">121</td> <td class="xl22" align="right">156</td> <td class="xl22" align="right">148</td> </tr> <tr style="height:12.75pt" height="17"> <td class="xl22" style="height:12.75pt" align="right" height="17">198</td> <td class="xl22" align="right">116</td> <td class="xl22" align="right">115</td> <td class="xl22" align="right">117</td> <td class="xl22" align="right">153</td> <td class="xl22" align="right">146</td> </tr> <tr style="height:12.75pt" height="17"> <td class="xl22" style="height:12.75pt" align="right" height="17">161</td> <td class="xl22" align="right">113</td> <td class="xl22" align="right">112</td> <td class="xl22" align="right">107</td> <td class="xl22" align="right">117</td> <td class="xl22" align="right">145</td> </tr> <tr style="height:12.75pt" height="17"> <td class="xl22" style="height:12.75pt" align="right" height="17">147</td> <td class="xl22" align="right">93</td> <td class="xl22" align="right">105</td> <td class="xl22" align="right">98</td> <td class="xl22" align="right">112</td> <td class="xl22" align="right">126</td> </tr> <tr style="height:12.75pt" height="17"> <td class="xl22" style="height:12.75pt" align="right" height="17">133</td> <td class="xl22" align="right">73</td> <td class="xl22" align="right">85</td> <td class="xl22" align="right">89</td> <td class="xl22" align="right">107</td> <td class="xl22" align="right">108</td> </tr> <tr style="height:12.75pt" height="17"> <td class="xl22" style="height:12.75pt" align="right" height="17">119</td> <td class="xl22" align="right">53</td> <td class="xl22" align="right">71</td> <td class="xl22" align="right">81</td> <td class="xl22" align="right">98</td> <td class="xl22" align="right">90</td> </tr> </tbody></table>
The constraints:
1 number from each row is selected to be summed (for a total of 14)
Each column must have at least one selection
Each column can not have more selections than as defined below:
Column 1= 2
Column 2= 4
Column 3= 4
Column 4= 2
Column 5= 2
Column 6= 2


I want find what which 14 selections that meet the constraints result in the largest summation.

The max() and then sum() method would work if it were not for the constraints.

Also you cannot simply find the max in a row and check if it meets the criteria, and if not find the next largest and do the same because this method overlooks the fact that the columns decrease at different rates.

I think that this just may be too complex, but I thought I would see if someone saw a simple way to do it.

 

[tweedle]

I believe I will concede on this one, though I believe applying a binary mask to generate a second table is the way to go, my head won't allow me to code the cycling of the binary through all the permutations.

 

[jfish1288]

Thanks for looking at it though