CODEWITHSUNDEEP
algorithmoptimization
nair.ashvin
nair.ashvin

Reputation: 801

Multiple Assignment / Matrix Maximization

I was wondering if anyone can point me to an efficient way to do this:

Maximize the sum of chosen elements in a 6 row x 10 column array such that there are exactly 3 elements chosen in every column and 5 elements chosen in every row.

I don't see an easy way to extend the assignment problem (and the Hungarian algorithm) to this task. We need to do thousands of these for our larger problem, so brute force is out of the question.

Upvotes: 2

Views: 802

Answers (1)

Haile
Haile

Reputation: 3180

As Vaughn wrote, a fast and easy way to solve your problem is to transform it in a Integer Linear Programming problem and then solve it with one of the many specialized solvers. So let's do it!

Modeling

First of all, we need a modeling language. I'll use MathProg, the GNU modeling language, wich is quite similar to (a subset of) AMPL.

The general model for our problem: (max.mod)

param rows;
param columns;
param matrix{i in 1..rows, j in 1..columns}; # the input matrix

## the variables of our problem. choose[i,j] = 1 means that we 
## pick element (i,j), otherwise is choose[i,j] = 0
var choose{i in 1..rows, j in 1..columns} binary; 

## the linear function we want to maximize: the sum of all the 
## choosen elements in the matrix.
maximize Sum:
    sum{i in 1..rows, j in 1..columns} choose[i,j] * matrix[i,j];

## first linear constraint: we have to choose exactly 3 elements for each column
subject to Cols{j in 1..columns}:
    sum{i in 1..rows} choose[i,j] = 3;

## second linear constraint: we have to choose exactly 5 elements for each row
subject to Rows{i in 1..rows}:
    sum{j in 1..columns} choose[i,j] = 5;

solve;

## to print the solution
printf "Solution: \n";
for{i in 1..rows}
{
    for{j in 1..columns}
    {
        printf (if choose[i,j] = 1 then "%d " else "- "), matrix[i,j];
    }
    printf "\n";
}
printf "\nSum = %d", sum{i in 1..rows, j in 1..columns} choose[i,j]*matrix[i,j];

We need a data file, too: (max.dat)

param rows := 6;
param columns := 10;

param matrix : 
    1 2 3 4 5 6 7 8 9 10 :=
1   1 6 9 1 0 7 5 4 3 2
2   9 7 4 6 4 3 2 1 4 9
3   9 6 4 3 2 1 5 7 8 9
4   6 5 4 3 7 8 9 6 4 2
5   7 5 4 3 2 8 9 6 7 8 
6   9 7 6 5 3 9 6 3 2 1;

Solving

Now we need a solver. I'll use the nice GLPK (the GNU Linear Programming Kit) from the command line, but it has a set of nice interfaces to a bunch of programming languages.

alberto@alberto-notebook:~/Desktop$ glpsol --model max.mod --data max.dat

INTEGER OPTIMAL SOLUTION FOUND
Time used:   0.0 secs
Memory used: 0.2 Mb (235703 bytes)

Solution: 
- 6 9 - - 7 5 - 3 - 
9 7 - 6 4 - - - - 9 
9 - - 3 - - - 7 8 9 
- - 4 - 7 8 9 6 - - 
- - - - - 8 9 6 7 8 
9 7 6 5 3 - - - - - 

Sum = 203

Upvotes: 2

Related Questions