The maximum 2D subarray polytope: Facet-inducing inequalities and polyhedral computations

Abstract Given a matrix with real-valued entries, the maximum 2D subarray problem consists in finding a rectangular submatrix with consecutive rows and columns maximizing the sum of its entries. In this work we start a polyhedral study of an integer programming formulation for 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. We also report computational experiments assessing the reduction of the dual bound for the linear relaxation achieved by these families of inequalities.