Improving strong branching by domain propagation

One of the essential components of a branch-and-bound based mixed-integer linear programming (MIP) solver is the branching rule. Strong branching is a method used by many state-of-the-art branching rules to select the variable to branch on. It precomputes the dual bounds of potential child nodes by...

Descripción completa

Guardado en:

Detalles Bibliográficos
Autor principal:	Gerald Gamrath
Formato:	article
Lenguaje:	EN
Publicado:	Elsevier 2014
Materias:	90C10 90C11 90B40 9008 90C57 9008 90C57 Applied mathematics. Quantitative methods T57-57.97 Electronic computers. Computer science QA75.5-76.95
Acceso en línea:	https://doaj.org/article/041acfb2425f40c2b14433b148b10f1a
Etiquetas:	Agregar Etiqueta Sin Etiquetas, Sea el primero en etiquetar este registro!

id	oai:doaj.org-article:041acfb2425f40c2b14433b148b10f1a
record_format	dspace
spelling	oai:doaj.org-article:041acfb2425f40c2b14433b148b10f1a2021-12-02T05:00:39ZImproving strong branching by domain propagation2192-440610.1007/s13675-014-0021-8https://doaj.org/article/041acfb2425f40c2b14433b148b10f1a2014-08-01T00:00:00Zhttp://www.sciencedirect.com/science/article/pii/S2192440621000290https://doaj.org/toc/2192-4406One of the essential components of a branch-and-bound based mixed-integer linear programming (MIP) solver is the branching rule. Strong branching is a method used by many state-of-the-art branching rules to select the variable to branch on. It precomputes the dual bounds of potential child nodes by solving auxiliary linear programs and thereby helps to take good branching decisions that lead to a small search tree. In this paper, we describe how these dual bound predictions can be improved by including domain propagation into strong branching. Domain propagation is a technique that MIP solvers usually apply at every node of the branch-and-bound tree to tighten the local domains of variables. Computational experiments on standard MIP instances indicate that our improved strong branching method significantly improves the quality of the predictions and causes almost no additional effort. For a full strong branching rule, we are able to obtain substantial reductions of the branch-and-bound tree size as well as the solving time. Moreover, the state-of-the-art hybrid branching rule can be improved this way as well.Gerald GamrathElsevierarticle90C1090C1190B40 9008 90C57900890C57Applied mathematics. Quantitative methodsT57-57.97Electronic computers. Computer scienceQA75.5-76.95ENEURO Journal on Computational Optimization, Vol 2, Iss 3, Pp 99-122 (2014)
institution	DOAJ
collection	DOAJ
language	EN
topic	90C10 90C11 90B40 9008 90C57 9008 90C57 Applied mathematics. Quantitative methods T57-57.97 Electronic computers. Computer science QA75.5-76.95
spellingShingle	90C10 90C11 90B40 9008 90C57 9008 90C57 Applied mathematics. Quantitative methods T57-57.97 Electronic computers. Computer science QA75.5-76.95 Gerald Gamrath Improving strong branching by domain propagation
description	One of the essential components of a branch-and-bound based mixed-integer linear programming (MIP) solver is the branching rule. Strong branching is a method used by many state-of-the-art branching rules to select the variable to branch on. It precomputes the dual bounds of potential child nodes by solving auxiliary linear programs and thereby helps to take good branching decisions that lead to a small search tree. In this paper, we describe how these dual bound predictions can be improved by including domain propagation into strong branching. Domain propagation is a technique that MIP solvers usually apply at every node of the branch-and-bound tree to tighten the local domains of variables. Computational experiments on standard MIP instances indicate that our improved strong branching method significantly improves the quality of the predictions and causes almost no additional effort. For a full strong branching rule, we are able to obtain substantial reductions of the branch-and-bound tree size as well as the solving time. Moreover, the state-of-the-art hybrid branching rule can be improved this way as well.
format	article
author	Gerald Gamrath
author_facet	Gerald Gamrath
author_sort	Gerald Gamrath
title	Improving strong branching by domain propagation
title_short	Improving strong branching by domain propagation
title_full	Improving strong branching by domain propagation
title_fullStr	Improving strong branching by domain propagation
title_full_unstemmed	Improving strong branching by domain propagation
title_sort	improving strong branching by domain propagation
publisher	Elsevier
publishDate	2014
url	https://doaj.org/article/041acfb2425f40c2b14433b148b10f1a
work_keys_str_mv	AT geraldgamrath improvingstrongbranchingbydomainpropagation
_version_	1718400810151313408

Improving strong branching by domain propagation

Ejemplares similares