Re: Maximising a sum of matrix elements

*To*: mathgroup at smc.vnet.net*Subject*: [mg60209] Re: [mg60174] Maximising a sum of matrix elements*From*: Daniel Lichtblau <danl at wolfram.com>*Date*: Wed, 7 Sep 2005 04:04:07 -0400 (EDT)*References*: <200509060227.WAA25774@smc.vnet.net>*Sender*: owner-wri-mathgroup at wolfram.com

Colin Pratt wrote: > Hi > > 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? > > Regards > Colin 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}}}} Daniel Lichtblau Wolfram Research

**Follow-Ups**:**Re: Re: Maximising a sum of matrix elements***From:*Daniel Lichtblau <danl@wolfram.com>

**References**:**Maximising a sum of matrix elements***From:*Colin Pratt <coke101@blueyonder.co.uk>