0
$\begingroup$

I have what I believe is an attribution problem: Given an $m \times n$ matrix, I need to select $p = \min\{m,n\}$ elements maximizing their sum such that they do not share a row or column.

More formally, I have the following linear optimization problem to solve:

\begin{align} \max \sum x_{ij} m_{ij} \\ \text{subject to} \\ \begin{cases} \sum_i x_{ij} \le 1 \\ \sum_j x_{ij} \le 1 \\ x_{ij} \in \{0,1\} \end{cases} \end{align}

For example, for the following matrix, I'd like to select the bolded elements:

\begin{equation} \left[ \begin{array}{cccc} \mathbf{4} & 2 & 1 & 2 \\ 0 & \mathbf{7} & 3 & 1 \\ 4 & 0 & 1 & \mathbf{9} \end{array} \right] \end{equation}

Until now, I have tried:

  • brute force testing all possible combinations of $p$ elements to check if they satisfy the restrictions, which needs $\binom{mn}{p}$ tests
  • not-so-brute test of all possible permutations of all $p-$combinations of the largest dimension $q = \max\{m,n\}$. This seems to need $q!\cdot p$ tests.

I have considered sorting all elements by value, and testing combinations in decreasing value order until one is found that satisfy the criteria, but haven't come up with an algorithm to accomplish that.

My searches for an existing algorithm have been unfruitful; any pointer is appreciated.

$\endgroup$
1
$\begingroup$

Put in $\max(m+n) - \min(m,n) = |m-n|$ fake rows (or columns) as needed to make a square. Put all the same value, all $0$ if allowed, in the fake entries. Then optimize for the square

http://en.wikipedia.org/wiki/Assignment_problem

Note that the actual http://en.wikipedia.org/wiki/Generalized_assignment_problem throws in weight constraints that you do not mention, and is therefore someone else's problem.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Ah, it's 'assignment problem', not 'attribution problem'! No wonder I couldn't find what I was looking for. Thanks for your pointer! $\endgroup$ – Bruno Kim Dec 14 '14 at 12:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.