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];
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