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

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...

Descripción completa

Guardado en:
Detalles Bibliográficos
Autores principales: Marenco, Javier, Koch, Ivo
Formato: info:eu-repo/semantics/preprint submittedVersion
Lenguaje:Inglés
Publicado: 2023
Materias:
Maximum subarray problem
Integer programming
Facets
Acceso en línea:https://repositorio.utdt.edu/handle/20.500.13098/11877
https://doi.org/10.1016/j.dam.2021.09.031
Aporte de:
Repositorio Digital Universidad Torcuato Di Tella de Universidad Torcuato Di Tella
id I57-R163-20.500.13098-11877
record_format dspace
spelling I57-R163-20.500.13098-118772023-06-16T07:00:18Z The maximum 2D subarray polytope: facet-inducing inequalities and polyhedral computations Marenco, Javier Koch, Ivo Maximum subarray problem Integer programming Facets 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. 2023-06-15T14:19:10Z 2023-06-15T14:19:10Z 2022 info:eu-repo/semantics/preprint info:eu-repo/semantics/submittedVersion https://repositorio.utdt.edu/handle/20.500.13098/11877 https://doi.org/10.1016/j.dam.2021.09.031 eng Koch, I., & Marenco, J. (2022). The maximum 2D subarray polytope: Facet-inducing inequalities and polyhedral computations. Discrete Applied Mathematics, 323, 286–301. https://doi.org/10.1016/j.dam.2021.09.031 info:eu-repo/semantics/openAccess https://creativecommons.org/licenses/by-sa/2.5/ar/ 34 p. application/pdf application/pdf
institution Universidad Torcuato Di Tella
institution_str I-57
repository_str R-163
collection Repositorio Digital Universidad Torcuato Di Tella
language Inglés
orig_language_str_mv eng
topic Maximum subarray problem
Integer programming
Facets
spellingShingle Maximum subarray problem
Integer programming
Facets
Marenco, Javier
Koch, Ivo
The maximum 2D subarray polytope: facet-inducing inequalities and polyhedral computations
topic_facet Maximum subarray problem
Integer programming
Facets
description 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.
format info:eu-repo/semantics/preprint
submittedVersion
author Marenco, Javier
Koch, Ivo
author_facet Marenco, Javier
Koch, Ivo
author_sort Marenco, Javier
title The maximum 2D subarray polytope: facet-inducing inequalities and polyhedral computations
title_short The maximum 2D subarray polytope: facet-inducing inequalities and polyhedral computations
title_full The maximum 2D subarray polytope: facet-inducing inequalities and polyhedral computations
title_fullStr The maximum 2D subarray polytope: facet-inducing inequalities and polyhedral computations
title_full_unstemmed The maximum 2D subarray polytope: facet-inducing inequalities and polyhedral computations
title_sort maximum 2d subarray polytope: facet-inducing inequalities and polyhedral computations
publishDate 2023
url https://repositorio.utdt.edu/handle/20.500.13098/11877
https://doi.org/10.1016/j.dam.2021.09.031
work_keys_str_mv AT marencojavier themaximum2dsubarraypolytopefacetinducinginequalitiesandpolyhedralcomputations
AT kochivo themaximum2dsubarraypolytopefacetinducinginequalitiesandpolyhedralcomputations
AT marencojavier maximum2dsubarraypolytopefacetinducinginequalitiesandpolyhedralcomputations
AT kochivo maximum2dsubarraypolytopefacetinducinginequalitiesandpolyhedralcomputations
_version_ 1769355029003632640

Ejemplares similares