Uma variante do problema de subarray de soma máxima?

Question

Isso está relacionado ao seguinte Q em Validação Cruzadahttps://stats.stackexchange.com/questions/483002/experimental-design-problem-with-goofy-constraintsque estou tentando responder, mas o problema de otimização precisa de algum outro conhecimento que espero encontrar aqui ... Breve resumo: Existe uma matriz retangular$B$com números não negativos (algumas complicações descritas abaixo) e deseja-se encontrar algum subarray retangular (não necessariamente contíguo) com soma máxima, dado um tamanho (aproximado) do subarray. Quais são alguns algoritmos eficazes? Consulte a pergunta vinculada para obter detalhes e antecedentes (e, esta é minha interpretação dessa pergunta, posso ter entendido algo errado).

Complicações : Algumas das entradas de$B$pode ser indefinido, e sabemos muito pouco sobre os possíveis padrões de indefinição. Eu pensei que talvez apenas substitua as entradas indefinidas por algum número negativo grande o suficiente, mas não tenho certeza se isso é bom o suficiente. Uma solução sem considerar essa complicação seria interessante, mas melhor ainda algumas ideias sobre como lidar com a complicação.

Answer 1

Eu cai$B_{i,j}$são conhecidos, você pode resolver o problema por meio de programação linear inteira da seguinte maneira. Deixe a variável de decisão binária$x_{i,j}$indicar se a entrada$(i,j)$é selecionado, deixe a variável de decisão binária$r_i$indique se a linha$i$é selecionado e permite que a variável de decisão binária$c_j$indique se a coluna$j$é selecionado. O problema é maximizar$\sum_{i,j} B_{i,j} x_{i,j}$sujeito a restrições lineares: \begin{align} x_{i,j} &\le r_i &&\text{para todos$i,j$}\\ x_{i,j} &\le c_j &&\texto{para todos$i,j$}\\ \sum_i r_i &= L \\ \sum_j c_j &= V \end{align} Se algum$B_{i,j}$é desconhecido, você pode corrigir$x_{i,j}=0$ou omitir$x_{i,j}$do problema.