Re: Maximising a sum of matrix elements

• To: mathgroup at smc.vnet.net
• Subject: [mg60245] Re: Maximising a sum of matrix elements
• 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 =
>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

```

• Prev by Date: Re: Three piece function
• Next by Date: Re: NMinimize InitialPoints BUGREPORT ?
• Previous by thread: Re: Maximising a sum of matrix elements
• Next by thread: ButtonEvaluator with two settings