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