A variant of maximum sum subarray problem?

Question

This is related to the foillowing Q on Cross Validated https://stats.stackexchange.com/questions/483002/experimental-design-problem-with-goofy-constraints which I am trying to answer, but the optimization problem needs some other expertize which I hope to find here ... Very brief summary: There is a rectangular matrix $B$ with nonnegative numbers (some complications described below) and one want to find some rectangular subarray (not necessarily contiguous) with maximum sum, given an (approximate) size of the subarray. What are some effective algorithms? Please see the linked question for details and background (and, this is my interpretation of that question, I might have misunderstood something.)

Complications: Some of the entries of $B$ might be undefined, and we know very little about the possible patterns of unefinedness. I have thought that maybe just replace the undefined entries with some large enough negative number, but not sure that is good enough. A solution without considering this complication woud be interesting, but even better some ideas about how handling the complication.

Answer 1

If all $B_{i,j}$ are known, you can solve the problem via integer linear programming as follows. Let binary decision variable $x_{i,j}$ indicate whether entry $(i,j)$ is selected, let binary decision variable $r_i$ indicate whether row $i$ is selected, and let binary decision variable $c_j$ indicate whether column $j$ is selected. The problem is to maximize $\sum_{i,j} B_{i,j} x_{i,j}$ subject to linear constraints: \begin{align} x_{i,j} &\le r_i &&\text{for all $i,j$}\\ x_{i,j} &\le c_j &&\text{for all $i,j$}\\ \sum_i r_i &= L \\ \sum_j c_j &= V \end{align} If some $B_{i,j}$ is unknown, you can fix $x_{i,j}=0$ or omit $x_{i,j}$ from the problem.