ตัวแปรของปัญหา subarray sum สูงสุด?

Question

สิ่งนี้เกี่ยวข้องกับ Q foillowing บน Cross Validated https://stats.stackexchange.com/questions/483002/experimental-design-problem-with-goofy-constraints ซึ่งฉันพยายามจะตอบ แต่ปัญหาการเพิ่มประสิทธิภาพต้องการความเชี่ยวชาญอื่น ๆ ซึ่งฉันหวังว่าจะพบที่นี่ ... สรุปสั้น ๆ : มีเมทริกซ์สี่เหลี่ยม $B$ด้วยตัวเลขที่ไม่เป็นค่าลบ (ภาวะแทรกซ้อนบางอย่างที่อธิบายไว้ด้านล่าง) และต้องการหา subarray รูปสี่เหลี่ยมผืนผ้า (ไม่จำเป็นต้องติดกัน) ที่มีผลรวมสูงสุดโดยให้ขนาด (โดยประมาณ) ของ subarray อัลกอริทึมที่มีประสิทธิภาพมีอะไรบ้าง? โปรดดูคำถามที่เชื่อมโยงสำหรับรายละเอียดและความเป็นมา (และนี่คือการตีความคำถามนั้นของฉันฉันอาจเข้าใจผิดบางอย่าง)

ภาวะแทรกซ้อน : บางส่วนของรายการ$B$อาจไม่ได้กำหนดและเรารู้น้อยมากเกี่ยวกับรูปแบบของความไม่กำหนดที่เป็นไปได้ ฉันคิดว่าอาจจะแค่แทนที่รายการที่ไม่ได้กำหนดด้วยจำนวนลบที่มากพอ แต่ไม่แน่ใจว่าดีพอ วิธีแก้ปัญหาโดยไม่ต้องคำนึงถึงภาวะแทรกซ้อนนี้เป็นสิ่งที่น่าสนใจ แต่ยังดีกว่าแนวคิดบางอย่างเกี่ยวกับวิธีจัดการกับภาวะแทรกซ้อน

Answer 1

ฉันตก $B_{i,j}$เป็นที่ทราบกันดีว่าคุณสามารถแก้ปัญหาได้โดยใช้โปรแกรมเชิงเส้นจำนวนเต็มดังนี้ ให้ตัวแปรการตัดสินใจไบนารี$x_{i,j}$ ระบุว่ารายการ $(i,j)$ ถูกเลือกปล่อยให้ตัวแปรการตัดสินใจแบบไบนารี $r_i$ ระบุว่าแถว $i$ ถูกเลือกและปล่อยให้ตัวแปรการตัดสินใจแบบไบนารี $c_j$ ระบุว่าคอลัมน์ $j$ถูกเลือก ปัญหาคือการทำให้เกิดประโยชน์สูงสุด$\sum_{i,j} B_{i,j} x_{i,j}$ภายใต้ข้อ จำกัด เชิงเส้น: \ begin {align} x_ {i, j} & \ le r_i && \ text {สำหรับทุกคน$i,j$} \\ x_ {i, j} & \ le c_j && \ text {สำหรับทุกคน $i,j$} \\ \ sum_i r_i & = L \\ \ sum_j c_j & = V \ end {align}ถ้าบาง$B_{i,j}$ ไม่ทราบคุณสามารถแก้ไขได้ $x_{i,j}=0$ หรือละเว้น $x_{i,j}$ จากปัญหา