I have given a matrix $A^{m \times n}$ and I am looking for a submatrix $B^{m \times k}$ for a given $k$ that maximizes the following expression:

$$\sum_{i=1}^m \max_{j \in \{1 \dots k\}} B_{i,j}$$

Does this correspond to a binary integer program with a nonlinear function? Can it be formulated as a more specific well-known problem? Are there any optimized algorithms known for it?

  • $\begingroup$ The submatrix can consist of any $k$ columns, i.e. there are $\frac{n!}{k!(n-k)!}$ possible submatrices. $\endgroup$ – Andreas Flueckiger Dec 5 '15 at 9:59

If I am reading this correctly there are only $n-k+1$ possibilities (the start position of the $k$ columns). This is not such a good candidate for a MIP model as this can be efficiently done by complete enumeration.

OK, I interpreted the problem wrong. I assumed submatrices are contiguous (as shown here). But what we need to do here is just select any $k$ columns.

Here is a linear MIP model that does the trick (I think).

We introduce the following variables:

  • a binary variable $\delta_j \in \{0,1\}$ to indicate if a column is selected
  • a binary variable $x_{i,j}\in \{0,1\}$ to indicate values from these columns can be selected
  • a continuous variable $y_i$ to hold the maximum of a row over the selected columns

So we have: $$\sum_j \delta_j = k$$ to select $k$ columns. $$x_{i,j}\le \delta_j \> \forall{i,j}$$ has the result that we only select from admissible columns ($\delta_j=0 \implies x_{i,j}=0)$ $$\sum_j x_{i,j}=1 \> \forall i$$ This allows us to pick exactly one value from each row in the selected columns. $$y_i=\sum_j a_{i,j} x_{i,j} \> \forall i$$ This actually picks the value. Finally we have the objective: $$\max \sum_i y_i$$

The idea is to select $k$ columns using binary variables $\delta_j$ and then select values $x_{i,j}$ from these columns (one value per row). Then add the values up and maximize. It will automatically pick the best ones (no need to maximize again).

The model assumes matrix values $a_{i,j}\ge 0$. If that is not the case, just preprocess the matrix by adding the (absolute value of the) most negative value to all elements.

The results are shown here.

  • $\begingroup$ OK, will do. Lets try some MIP model! $\endgroup$ – Erwin Kalvelagen Dec 5 '15 at 12:59

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.