3
$\begingroup$

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.

$\endgroup$
5
$\begingroup$

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.

| improve this answer | |
$\endgroup$
  • 1
    $\begingroup$ If $(i,j)$ is missing, then $r_i$ and $c_j$ cannot be selected simultaneously, then you need to add $r_i = 1 => c_j =0$ and $c_j = 1 => r_i = 0$ as constraints. $\endgroup$ – user3680510 Aug 25 at 14:54
  • 1
    $\begingroup$ One conflict constraint does that: $r_i+c_j \le 1$. $\endgroup$ – RobPratt Aug 25 at 14:57
  • $\begingroup$ What does it mean for a column or row to be selected here? Is it that at least one must be equal to 1? $\endgroup$ – Dimitriy V. Masterov Aug 27 at 2:00
  • $\begingroup$ A subarray is completely determined by which rows and columns are selected. If both row $i$ and column $j$ are selected ($r_i=c_j=1$), then entry $(i,j)$ is selected $x_{i,j}=1$ and reward $B_{i,j}$ accrues. $\endgroup$ – RobPratt Aug 27 at 2:06
  • $\begingroup$ And if $c_{j'}$ is then added, then $x_{i,j'}=1$? $\endgroup$ – Dimitriy V. Masterov Aug 27 at 2:11

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.