Services & Resources / Wolfram Forums
-----
 /
MathGroup Archive
2005
*January
*February
*March
*April
*May
*June
*July
*August
*September
*October
*November
*December
*Archive Index
*Ask about this page
*Print this page
*Give us feedback
*Sign up for the Wolfram Insider

MathGroup Archive 2005

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

Search the Archive

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







  • Prev by Date: Re: Hold[] ReleaseHold[] ? or what ?
  • Next by Date: NMinimize InitialPoints BUGREPORT ?
  • Previous by thread: Maximising a sum of matrix elements
  • Next by thread: Re: Re: Maximising a sum of matrix elements