Re: Maximising a sum of matrix elements

*To*: mathgroup at smc.vnet.net*Subject*: [mg60245] Re: Maximising a sum of matrix elements*From*: Bill Rowe <readnewsciv at earthlink.net>*Date*: Thu, 8 Sep 2005 04:53:32 -0400 (EDT)*Sender*: owner-wri-mathgroup at wolfram.com

On 9/7/05 at 4:04 AM, danl at wolfram.com (Daniel Lichtblau) wrote: >Colin Pratt wrote: >>Could anyone suggest how I might use Mathematica to tackle the >>following? >>Given a n x n matrix with positive entries, find the maximum sum >>involving one and only one entry from each row and column. Is >>there a simple way to enumerate the n! possible sums? >I'd not recommend that approach as it can be quite slow for more >than 10 or so rows. >This is an example of the Assignment Problem from network >programming, dixcussed e.g. in Schrijver's "Theory of Linear and >Integer Programming" or Chvatal's "Linear Programming". >Basically one sets it up as an integer linear program to maximize >the sum over {i,j} of x[i,j]*mat[i,j] where all x[i,j] are 0 or 1, >for each fixed i we have Sum[x[i,j],{j,n}]==1, and likewise for >each fixed j we have Sum[x[i,j],{i,n}]==1. >The nice feature is that one may solve the relaxed linear program >ignoring integrality constraints (that is, just constrain >0<=x[i,j]<=1), and obtain a solution to the problem at hand. This >follows from the observation that our matrix of x[i,j]s is doubly >stochastic (row sums and column sums are all 1, all elements >nonnegative), and permutation matrices are the extremal "points" in >the space of such matrices (Birkoff-von Neumann theorem). >Here is simple code for the problem at hand. >maxPermutationSum[mat_] := Module[ >{n=Length[mat], vars, x, c1, c2, c3, fvars, maxsum, res}, vars = >Array[x,{n,n}]; fvars = Flatten[vars]; c1 = >Thread[Apply[Plus,vars,{1}]==1]; c2 = >Thread[Apply[Plus,Transpose[vars],{1}]==1]; c3 = Map[0<=#<=1&, >fvars]; constraints = Join[c1,c2,c3]; {maxsum,res} = >NMaximize[{Apply[Plus,Flatten[vars*mat]],constraints}, fvars]; >Round[{maxsum, vars/.res}] >] >Quick example: >mat[dim_,max_] := Table[Random[Integer,max], {dim}, {dim}] >In[30]:= InputForm[mm = mat[10,20]] Out[30]//InputForm= {{12, 6, >18, 6, 11, 8, 8, 4, 10, 12}, >{8, 14, 3, 7, 18, 20, 10, 7, 17, 19}, {7, 7, 6, 19, 3, 19, 1, 0, >12, 18}, {3, 10, 3, 0, 15, 3, 16, 1, 19, 3}, {9, 14, 20, 14, 3, 8, >11, 1, 7, 12}, {11, 10, 9, 2, 11, 14, 2, 2, 18, 20}, {17, 11, 18, >9, 2, 0, 18, 11, 14, 16}, {20, 2, 16, 3, 14, 7, 13, 13, 7, 16}, >{15, 7, 15, 2, 3, 19, 11, 7, 13, 8}, {13, 16, 3, 15, 8, 18, 4, 14, >16, 16}} >In[33]:= InputForm[Timing[{m1,p1} = maxPermutationSum[mm]]] >Out[33]//InputForm= {0.21000000000000568*Second, {179, {{0, 0, 1, >0, 0, 0, 0, 0, 0, 0}, >{0, 0, 0, 0, 1, 0, 0, 0, 0, 0}, {0, 0, 0, 1, 0, 0, 0, 0, 0, 0}, {0, >0, 0, 0, 0, 0, 0, 0, 1, 0}, {0, 1, 0, 0, 0, 0, 0, 0, 0, 0}, {0, 0, >0, 0, 0, 0, 0, 0, 0, 1}, {0, 0, 0, 0, 0, 0, 1, 0, 0, 0}, {1, 0, 0, >0, 0, 0, 0, 0, 0, 0}, {0, 0, 0, 0, 0, 1, 0, 0, 0, 0}, {0, 0, 0, 0, >0, 0, 0, 1, 0, 0}}}} I have to admit to being somewhat puzzled. Clearly, doing Max/@m1 selects only one value from each row. And for In[6]:= m1 = {{12, 6, 18, 6, 11, 8, 8, 4, 10, 12}, {8, 14, 3, 7, 18, 20, 10, 7, 17, 19}, {7, 7, 6, 19, 3, 19, 1, 0, 12, 18}, {3, 10, 3, 0, 15, 3, 16, 1, 19, 3}, {9, 14, 20, 14, 3, 8, 11, 1, 7, 12}, {11, 10, 9, 2, 11, 14, 2, 2, 18, 20}, {17, 11, 18, 9, 2, 0, 18, 11, 14, 16}, {20, 2, 16, 3, 14, 7, 13, 13, 7, 16}, {15, 7, 15, 2, 3, 19, 11, 7, 13, 8}, {13, 16, 3, 15, 8, 18, 4, 14, 16, 16}}; In[7]:= Total[Max /@ m1] Out[7]= 191 Which is greater than the maximum sum returned by your code. Why would Max[Total[Max/@m1],Total[Max/@Transpose@m1]] not be the desired maximum sum? -- To reply via email subtract one hundred and four