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 com- putational experiments assessing the reduction of the dual bound for the linear

relaxation achieved by these families of inequalities.