Two-row and two-column mixed-integer presolve using hashing-based pairing methods

In state-of-the-art mixed-integer programming solvers, a large array of reduction techniques are applied to simplify the problem and strengthen the model formulation before starting the actual branch-and-cut phase. Despite their mathematical simplicity, these methods can have significant impact on t...

Descripción completa

Guardado en:

Detalles Bibliográficos
Autores principales:	Patrick Gemander, Wei-Kun Chen, Dieter Weninger, Leona Gottwald, Ambros Gleixner, Alexander Martin
Formato:	article
Lenguaje:	EN
Publicado:	Elsevier 2020
Materias:	90C05 90C10 90C11 65Y05 Applied mathematics. Quantitative methods T57-57.97 Electronic computers. Computer science QA75.5-76.95
Acceso en línea:	https://doaj.org/article/87aae383cabe4346ba569049661df2fd
Etiquetas:	Agregar Etiqueta Sin Etiquetas, Sea el primero en etiquetar este registro!

id	oai:doaj.org-article:87aae383cabe4346ba569049661df2fd
record_format	dspace
spelling	oai:doaj.org-article:87aae383cabe4346ba569049661df2fd2021-12-03T04:01:13ZTwo-row and two-column mixed-integer presolve using hashing-based pairing methods2192-440610.1007/s13675-020-00129-6https://doaj.org/article/87aae383cabe4346ba569049661df2fd2020-10-01T00:00:00Zhttp://www.sciencedirect.com/science/article/pii/S2192440621001283https://doaj.org/toc/2192-4406In state-of-the-art mixed-integer programming solvers, a large array of reduction techniques are applied to simplify the problem and strengthen the model formulation before starting the actual branch-and-cut phase. Despite their mathematical simplicity, these methods can have significant impact on the solvability of a given problem. However, a crucial property for employing presolve techniques successfully is their speed. Hence, most methods inspect constraints or variables individually in order to guarantee linear complexity. In this paper, we present new hashing-based pairing mechanisms that help to overcome known performance limitations of more powerful presolve techniques that consider pairs of rows or columns. Additionally, we develop an enhancement to one of these presolve techniques by exploiting the presence of set-packing structures on binary variables in order to strengthen the resulting reductions without increasing runtime. We analyze the impact of these methods on the MIPLIB 2017 benchmark set based on an implementation in the MIP solver SCIP.Patrick GemanderWei-Kun ChenDieter WeningerLeona GottwaldAmbros GleixnerAlexander MartinElsevierarticle90C0590C1090C1165Y05Applied mathematics. Quantitative methodsT57-57.97Electronic computers. Computer scienceQA75.5-76.95ENEURO Journal on Computational Optimization, Vol 8, Iss 3, Pp 205-240 (2020)
institution	DOAJ
collection	DOAJ
language	EN
topic	90C05 90C10 90C11 65Y05 Applied mathematics. Quantitative methods T57-57.97 Electronic computers. Computer science QA75.5-76.95
spellingShingle	90C05 90C10 90C11 65Y05 Applied mathematics. Quantitative methods T57-57.97 Electronic computers. Computer science QA75.5-76.95 Patrick Gemander Wei-Kun Chen Dieter Weninger Leona Gottwald Ambros Gleixner Alexander Martin Two-row and two-column mixed-integer presolve using hashing-based pairing methods
description	In state-of-the-art mixed-integer programming solvers, a large array of reduction techniques are applied to simplify the problem and strengthen the model formulation before starting the actual branch-and-cut phase. Despite their mathematical simplicity, these methods can have significant impact on the solvability of a given problem. However, a crucial property for employing presolve techniques successfully is their speed. Hence, most methods inspect constraints or variables individually in order to guarantee linear complexity. In this paper, we present new hashing-based pairing mechanisms that help to overcome known performance limitations of more powerful presolve techniques that consider pairs of rows or columns. Additionally, we develop an enhancement to one of these presolve techniques by exploiting the presence of set-packing structures on binary variables in order to strengthen the resulting reductions without increasing runtime. We analyze the impact of these methods on the MIPLIB 2017 benchmark set based on an implementation in the MIP solver SCIP.
format	article
author	Patrick Gemander Wei-Kun Chen Dieter Weninger Leona Gottwald Ambros Gleixner Alexander Martin
author_facet	Patrick Gemander Wei-Kun Chen Dieter Weninger Leona Gottwald Ambros Gleixner Alexander Martin
author_sort	Patrick Gemander
title	Two-row and two-column mixed-integer presolve using hashing-based pairing methods
title_short	Two-row and two-column mixed-integer presolve using hashing-based pairing methods
title_full	Two-row and two-column mixed-integer presolve using hashing-based pairing methods
title_fullStr	Two-row and two-column mixed-integer presolve using hashing-based pairing methods
title_full_unstemmed	Two-row and two-column mixed-integer presolve using hashing-based pairing methods
title_sort	two-row and two-column mixed-integer presolve using hashing-based pairing methods
publisher	Elsevier
publishDate	2020
url	https://doaj.org/article/87aae383cabe4346ba569049661df2fd
work_keys_str_mv	AT patrickgemander tworowandtwocolumnmixedintegerpresolveusinghashingbasedpairingmethods AT weikunchen tworowandtwocolumnmixedintegerpresolveusinghashingbasedpairingmethods AT dieterweninger tworowandtwocolumnmixedintegerpresolveusinghashingbasedpairingmethods AT leonagottwald tworowandtwocolumnmixedintegerpresolveusinghashingbasedpairingmethods AT ambrosgleixner tworowandtwocolumnmixedintegerpresolveusinghashingbasedpairingmethods AT alexandermartin tworowandtwocolumnmixedintegerpresolveusinghashingbasedpairingmethods
_version_	1718373943253925888

Two-row and two-column mixed-integer presolve using hashing-based pairing methods

Ejemplares similares