Una variante del problema del subarray della somma massima?

Question

Ciò è correlato alla sventagliata Q su Cross Validated https://stats.stackexchange.com/questions/483002/experimental-design-problem-with-goofy-constraints a cui sto cercando di rispondere, ma il problema di ottimizzazione necessita di qualche altra competenza che spero di trovare qui ... Breve riassunto: c'è una matrice rettangolare $B$con numeri non negativi (alcune complicazioni descritte di seguito) e si vuole trovare qualche sottoarray rettangolare (non necessariamente contiguo) con somma massima, data una dimensione (approssimativa) del sottoarray. Quali sono alcuni algoritmi efficaci? Si prega di consultare la domanda collegata per i dettagli e il background (e, questa è la mia interpretazione di quella domanda, potrei aver frainteso qualcosa.)

Complicazioni : alcune delle voci di$B$potrebbe essere indefinito e sappiamo molto poco sui possibili modelli di non definizione. Ho pensato che forse basta sostituire le voci indefinite con un numero negativo abbastanza grande, ma non sono sicuro che sia abbastanza buono. Una soluzione senza considerare questa complicazione sarebbe interessante, ma ancora meglio alcune idee su come gestire la complicazione.

Answer 1

Cado $B_{i,j}$sono noti, è possibile risolvere il problema tramite la programmazione lineare intera come segue. Lascia che la decisione binaria sia variabile$x_{i,j}$ indicare se l'ingresso $(i,j)$ è selezionato, lascia la variabile di decisione binaria $r_i$ indicare se riga $i$ è selezionato e lascia la variabile di decisione binaria $c_j$ indicare se colonna $j$è selezionato. Il problema è massimizzare$\sum_{i,j} B_{i,j} x_{i,j}$soggetto a vincoli lineari: \ begin {align} x_ {i, j} & \ le r_i && \ text {for all$i,j$} \\ x_ {i, j} & \ le c_j && \ text {per tutti $i,j$} \\ \ sum_i r_i & = L \\ \ sum_j c_j & = V \ end {align} Se alcuni$B_{i,j}$ è sconosciuto, puoi aggiustarlo $x_{i,j}=0$ o omettere $x_{i,j}$ dal problema.