Eine Variante des Maximum-Summen-Subarray-Problems?

Question

Dies hängt mit dem folgenden Q bei Cross Validated zusammen https://stats.stackexchange.com/questions/483002/experimental-design-problem-with-goofy-constraints was ich zu beantworten versuche, aber das Optimierungsproblem braucht ein anderes Fachwissen, das ich hoffentlich hier finden werde ... Sehr kurze Zusammenfassung: Es gibt eine rechteckige Matrix $B$mit nichtnegativen Zahlen (einige Komplikationen werden unten beschrieben) und man möchte ein rechteckiges Subarray (nicht unbedingt zusammenhängend) mit maximaler Summe finden, wenn eine (ungefähre) Größe des Subarrays gegeben ist. Was sind einige effektive Algorithmen? Einzelheiten und Hintergrundinformationen finden Sie in der verknüpften Frage (und dies ist meine Interpretation dieser Frage, ich habe möglicherweise etwas falsch verstanden.)

Komplikationen : Einige der Einträge von$B$könnte undefiniert sein, und wir wissen sehr wenig über die möglichen Muster der Undefiniertheit. Ich habe gedacht, dass vielleicht nur die undefinierten Einträge durch eine ausreichend große negative Zahl ersetzt werden, aber nicht sicher, ob das gut genug ist. Eine Lösung ohne Berücksichtigung dieser Komplikation wäre interessant, aber noch besser einige Ideen zum Umgang mit der Komplikation.

Answer 1

Ich falle $B_{i,j}$bekannt sind, können Sie das Problem über eine ganzzahlige lineare Programmierung wie folgt lösen. Lassen Sie die binäre Entscheidungsvariable$x_{i,j}$ Geben Sie an, ob der Eintrag vorhanden ist $(i,j)$ ausgewählt ist, sei binäre Entscheidungsvariable $r_i$ Geben Sie an, ob die Zeile $i$ ausgewählt ist, und lassen Sie die binäre Entscheidungsvariable $c_j$ Geben Sie an, ob die Spalte $j$ist ausgewählt. Das Problem ist zu maximieren$\sum_{i,j} B_{i,j} x_{i,j}$unterliegt linearen Einschränkungen: \ begin {align} x_ {i, j} & \ le r_i && \ text {für alle$i,j$} \\ x_ {i, j} & \ le c_j && \ text {für alle $i,j$} \\ \ sum_i r_i & = L \\ \ sum_j c_j & = V \ end {align} Wenn einige$B_{i,j}$ ist unbekannt, können Sie beheben $x_{i,j}=0$ oder weglassen $x_{i,j}$ vom Problem.