An exploratory computational analysis of dual degeneracy in mixed-integer programming

Dual degeneracy, i.e., the presence of multiple optimal bases to a linear programming (LP) problem, heavily affects the solution process of mixed integer programming (MIP) solvers. Different optimal bases lead to different cuts being generated, different branching decisions being taken and different...

Descripción completa

Guardado en:

Detalles Bibliográficos
Autores principales:	Gerald Gamrath, Timo Berthold, Domenico Salvagnin
Formato:	article
Lenguaje:	EN
Publicado:	Elsevier 2020
Materias:	90C10 90C11 90C57 Applied mathematics. Quantitative methods T57-57.97 Electronic computers. Computer science QA75.5-76.95
Acceso en línea:	https://doaj.org/article/02acf5f02ecf4593a8b6c0599764c3ca
Etiquetas:	Agregar Etiqueta Sin Etiquetas, Sea el primero en etiquetar este registro!

id	oai:doaj.org-article:02acf5f02ecf4593a8b6c0599764c3ca
record_format	dspace
spelling	oai:doaj.org-article:02acf5f02ecf4593a8b6c0599764c3ca2021-12-03T04:01:14ZAn exploratory computational analysis of dual degeneracy in mixed-integer programming2192-440610.1007/s13675-020-00130-zhttps://doaj.org/article/02acf5f02ecf4593a8b6c0599764c3ca2020-10-01T00:00:00Zhttp://www.sciencedirect.com/science/article/pii/S2192440621001295https://doaj.org/toc/2192-4406Dual degeneracy, i.e., the presence of multiple optimal bases to a linear programming (LP) problem, heavily affects the solution process of mixed integer programming (MIP) solvers. Different optimal bases lead to different cuts being generated, different branching decisions being taken and different solutions being found by primal heuristics. Nevertheless, only a few methods have been published that either avoid or exploit dual degeneracy. The aim of the present paper is to conduct a thorough computational study on the presence of dual degeneracy for the instances of well-known public MIP instance collections. How many instances are affected by dual degeneracy? How degenerate are the affected models? How does branching affect degeneracy: Does it increase or decrease by fixing variables? Can we identify different types of degenerate MIPs? As a tool to answer these questions, we introduce a new measure for dual degeneracy: the variable–constraint ratio of the optimal face. It provides an estimate for the likelihood that a basic variable can be pivoted out of the basis. Furthermore, we study how the so-called cloud intervals—the projections of the optimal face of the LP relaxations onto the individual variables—evolve during tree search and the implications for reducing the set of branching candidates.Gerald GamrathTimo BertholdDomenico SalvagninElsevierarticle90C1090C1190C57Applied mathematics. Quantitative methodsT57-57.97Electronic computers. Computer scienceQA75.5-76.95ENEURO Journal on Computational Optimization, Vol 8, Iss 3, Pp 241-261 (2020)
institution	DOAJ
collection	DOAJ
language	EN
topic	90C10 90C11 90C57 Applied mathematics. Quantitative methods T57-57.97 Electronic computers. Computer science QA75.5-76.95
spellingShingle	90C10 90C11 90C57 Applied mathematics. Quantitative methods T57-57.97 Electronic computers. Computer science QA75.5-76.95 Gerald Gamrath Timo Berthold Domenico Salvagnin An exploratory computational analysis of dual degeneracy in mixed-integer programming
description	Dual degeneracy, i.e., the presence of multiple optimal bases to a linear programming (LP) problem, heavily affects the solution process of mixed integer programming (MIP) solvers. Different optimal bases lead to different cuts being generated, different branching decisions being taken and different solutions being found by primal heuristics. Nevertheless, only a few methods have been published that either avoid or exploit dual degeneracy. The aim of the present paper is to conduct a thorough computational study on the presence of dual degeneracy for the instances of well-known public MIP instance collections. How many instances are affected by dual degeneracy? How degenerate are the affected models? How does branching affect degeneracy: Does it increase or decrease by fixing variables? Can we identify different types of degenerate MIPs? As a tool to answer these questions, we introduce a new measure for dual degeneracy: the variable–constraint ratio of the optimal face. It provides an estimate for the likelihood that a basic variable can be pivoted out of the basis. Furthermore, we study how the so-called cloud intervals—the projections of the optimal face of the LP relaxations onto the individual variables—evolve during tree search and the implications for reducing the set of branching candidates.
format	article
author	Gerald Gamrath Timo Berthold Domenico Salvagnin
author_facet	Gerald Gamrath Timo Berthold Domenico Salvagnin
author_sort	Gerald Gamrath
title	An exploratory computational analysis of dual degeneracy in mixed-integer programming
title_short	An exploratory computational analysis of dual degeneracy in mixed-integer programming
title_full	An exploratory computational analysis of dual degeneracy in mixed-integer programming
title_fullStr	An exploratory computational analysis of dual degeneracy in mixed-integer programming
title_full_unstemmed	An exploratory computational analysis of dual degeneracy in mixed-integer programming
title_sort	exploratory computational analysis of dual degeneracy in mixed-integer programming
publisher	Elsevier
publishDate	2020
url	https://doaj.org/article/02acf5f02ecf4593a8b6c0599764c3ca
work_keys_str_mv	AT geraldgamrath anexploratorycomputationalanalysisofdualdegeneracyinmixedintegerprogramming AT timoberthold anexploratorycomputationalanalysisofdualdegeneracyinmixedintegerprogramming AT domenicosalvagnin anexploratorycomputationalanalysisofdualdegeneracyinmixedintegerprogramming AT geraldgamrath exploratorycomputationalanalysisofdualdegeneracyinmixedintegerprogramming AT timoberthold exploratorycomputationalanalysisofdualdegeneracyinmixedintegerprogramming AT domenicosalvagnin exploratorycomputationalanalysisofdualdegeneracyinmixedintegerprogramming
_version_	1718373910688301056

An exploratory computational analysis of dual degeneracy in mixed-integer programming

Ejemplares similares