The 2D Subarray Polytope.

Given a d -dimensional array, the maximum subarray problem consists in finding an axis-parallel slice of the array maximizing the sum of its entries. In this work we start a polyhedral study of a natural integer programming formulation for this problem when d = 2. Such an exploration is motivated by the need of solving large-scale instances of the rectilinear picture compression problem (RPC), a problem which arises in different scenarios. The obtained results can be useful to solve the column generation phase of a branch and price approach for RPC, a technique that applies naturally to this problem. We thus define the 2D subarray polytope , explore conditions ensuring the validity of linear inequalities, and provide several families of facet-inducing inequalities. [ABSTRACT FROM AUTHOR]