I’m trying to find an efficient algorithm for the following optimization problem:
Given a matrix $A$ with elements $a_{ij}$ and dimension $k$, select exactly $n$ elements from $A$ ($n<k$) such that the sum of the elements is maximized, subject to the constraint that any index of $a_{ij}$ is only used once. In other words: if element $a_{ij}$ has been selected, no other elements from rows and columns i and j can be selected.
Notes:
- It is allowed to select elements from the diagonal.
- The order of magnitude of $k$ is 10,000.
I have a dynamic programming algorithm but the downside is that it can't be parallelized.
The problem resembles the assignment problem. This can be solved using the Hungarian Algorithm, which can be easily parallelized using Java 8 streams. However, the assignment problem has the constraint that from each row and column only one element can be selected. This is less strict than above problem since it allows to select both $a_{ij}$ and $a_{ji}$.
Question: do you know how to adjust the Hungarian Problem for the stricter constraint?
Context:
This algorithm is used to optimize large-scale power storage, which can be modelled as a collection of spread options.