info:eu-repo/semantics/preprint
The maximum 2D subarray polytope: facet-inducing inequalities and polyhedral computations
Fecha
2022Autor
Marenco, Javier
Koch, Ivo
Institución
Resumen
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.