The impact of filtering in a branch-and-cut algorithm for multicommodity capacitated fixed charge network design

In this paper, we present a state-of-the-art branch-and-cut (B&C) algorithm for the multicommodity capacitated fixed charge network design problem (MCND). This algorithm combines bounding and branching procedures inspired by the latest developments in mixed-integer programming (MIP) software too...

Descripción completa

Guardado en:

Detalles Bibliográficos
Autores principales:	Mervat Chouman, TeodorGabriel Crainic, Bernard Gendron
Formato:	article
Lenguaje:	EN
Publicado:	Elsevier 2018
Materias:	90B10 90C11 Applied mathematics. Quantitative methods T57-57.97 Electronic computers. Computer science QA75.5-76.95
Acceso en línea:	https://doaj.org/article/7775b4131a8a4365948123c9547ea651
Etiquetas:	Agregar Etiqueta Sin Etiquetas, Sea el primero en etiquetar este registro!

id	oai:doaj.org-article:7775b4131a8a4365948123c9547ea651
record_format	dspace
spelling	oai:doaj.org-article:7775b4131a8a4365948123c9547ea6512021-12-02T05:01:06ZThe impact of filtering in a branch-and-cut algorithm for multicommodity capacitated fixed charge network design2192-440610.1007/s13675-017-0091-5https://doaj.org/article/7775b4131a8a4365948123c9547ea6512018-06-01T00:00:00Zhttp://www.sciencedirect.com/science/article/pii/S2192440621000988https://doaj.org/toc/2192-4406In this paper, we present a state-of-the-art branch-and-cut (B&C) algorithm for the multicommodity capacitated fixed charge network design problem (MCND). This algorithm combines bounding and branching procedures inspired by the latest developments in mixed-integer programming (MIP) software tools. Several filtering methods that exploit the structure of the MCND are also developed and embedded within the B&C algorithm. These filtering methods apply inference techniques to forbid combinations of values for some variables. This can take the form of adding cuts, reducing the domains of the variables, or fixing the values of the variables. Our experiments on a large set of randomly generated instances show that an appropriate selection of filtering techniques allows the B&C algorithm to perform better than the variant of the algorithm without filtering. These experiments also show that the B&C algorithm, with or without filtering, is competitive with a state-of-the-art MIP solver.Mervat ChoumanTeodorGabriel CrainicBernard GendronElsevierarticle90B1090C11Applied mathematics. Quantitative methodsT57-57.97Electronic computers. Computer scienceQA75.5-76.95ENEURO Journal on Computational Optimization, Vol 6, Iss 2, Pp 143-184 (2018)
institution	DOAJ
collection	DOAJ
language	EN
topic	90B10 90C11 Applied mathematics. Quantitative methods T57-57.97 Electronic computers. Computer science QA75.5-76.95
spellingShingle	90B10 90C11 Applied mathematics. Quantitative methods T57-57.97 Electronic computers. Computer science QA75.5-76.95 Mervat Chouman TeodorGabriel Crainic Bernard Gendron The impact of filtering in a branch-and-cut algorithm for multicommodity capacitated fixed charge network design
description	In this paper, we present a state-of-the-art branch-and-cut (B&C) algorithm for the multicommodity capacitated fixed charge network design problem (MCND). This algorithm combines bounding and branching procedures inspired by the latest developments in mixed-integer programming (MIP) software tools. Several filtering methods that exploit the structure of the MCND are also developed and embedded within the B&C algorithm. These filtering methods apply inference techniques to forbid combinations of values for some variables. This can take the form of adding cuts, reducing the domains of the variables, or fixing the values of the variables. Our experiments on a large set of randomly generated instances show that an appropriate selection of filtering techniques allows the B&C algorithm to perform better than the variant of the algorithm without filtering. These experiments also show that the B&C algorithm, with or without filtering, is competitive with a state-of-the-art MIP solver.
format	article
author	Mervat Chouman TeodorGabriel Crainic Bernard Gendron
author_facet	Mervat Chouman TeodorGabriel Crainic Bernard Gendron
author_sort	Mervat Chouman
title	The impact of filtering in a branch-and-cut algorithm for multicommodity capacitated fixed charge network design
title_short	The impact of filtering in a branch-and-cut algorithm for multicommodity capacitated fixed charge network design
title_full	The impact of filtering in a branch-and-cut algorithm for multicommodity capacitated fixed charge network design
title_fullStr	The impact of filtering in a branch-and-cut algorithm for multicommodity capacitated fixed charge network design
title_full_unstemmed	The impact of filtering in a branch-and-cut algorithm for multicommodity capacitated fixed charge network design
title_sort	impact of filtering in a branch-and-cut algorithm for multicommodity capacitated fixed charge network design
publisher	Elsevier
publishDate	2018
url	https://doaj.org/article/7775b4131a8a4365948123c9547ea651
work_keys_str_mv	AT mervatchouman theimpactoffilteringinabranchandcutalgorithmformulticommoditycapacitatedfixedchargenetworkdesign AT teodorgabrielcrainic theimpactoffilteringinabranchandcutalgorithmformulticommoditycapacitatedfixedchargenetworkdesign AT bernardgendron theimpactoffilteringinabranchandcutalgorithmformulticommoditycapacitatedfixedchargenetworkdesign AT mervatchouman impactoffilteringinabranchandcutalgorithmformulticommoditycapacitatedfixedchargenetworkdesign AT teodorgabrielcrainic impactoffilteringinabranchandcutalgorithmformulticommoditycapacitatedfixedchargenetworkdesign AT bernardgendron impactoffilteringinabranchandcutalgorithmformulticommoditycapacitatedfixedchargenetworkdesign
_version_	1718400836538728448

The impact of filtering in a branch-and-cut algorithm for multicommodity capacitated fixed charge network design

Ejemplares similares