Services & ResourcesWolfram ForumsMathGroup Archive

[Date Index] [Thread Index] [Author Index]

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>