Branch-and-price-and-cut for large-scale multicommodity capacitated fixed-charge network design

We present a branch-and-price-and-cut algorithm for solving large-scale instances of the multicommodity capacitated fixed-charge network design problem. We assume good feasible solutions are already known and we focus on an efficient algorithm for proving the optimality of the solutions. The restric...

Descripción completa

Guardado en:
Detalles Bibliográficos
Autores principales: Bernard Gendron, Mathieu Larose
Formato: article
Lenguaje:EN
Publicado: Elsevier 2014
Materias:
Acceso en línea:https://doaj.org/article/9fd39dea92a84415a7c7eafe5f8d9019
Etiquetas: Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
id oai:doaj.org-article:9fd39dea92a84415a7c7eafe5f8d9019
record_format dspace
spelling oai:doaj.org-article:9fd39dea92a84415a7c7eafe5f8d90192021-12-02T05:00:38ZBranch-and-price-and-cut for large-scale multicommodity capacitated fixed-charge network design2192-440610.1007/s13675-014-0020-9https://doaj.org/article/9fd39dea92a84415a7c7eafe5f8d90192014-06-01T00:00:00Zhttp://www.sciencedirect.com/science/article/pii/S2192440621000253https://doaj.org/toc/2192-4406We present a branch-and-price-and-cut algorithm for solving large-scale instances of the multicommodity capacitated fixed-charge network design problem. We assume good feasible solutions are already known and we focus on an efficient algorithm for proving the optimality of the solutions. The restricted master problem solved at each column generation iteration is obtained directly from the compact arc-based model by considering only a subset of the commodity flow variables. The pricing subproblem corresponds to a Lagrangian relaxation of the flow conservation and capacity constraints, leaving in the Lagrangian subproblem only the strong inequalities. The column generation procedure is completed by a cut generation step based on strong inequalities. The resulting column-and-row generation procedure is embedded within an enumerative scheme. Computational experiments on a large set of randomly generated instances are presented and analyzed.Bernard GendronMathieu LaroseElsevierarticle90C11 Mixed integer programming90C35 Programming involving graphs or networks90B10 Network modelsdeterministicApplied mathematics. Quantitative methodsT57-57.97Electronic computers. Computer scienceQA75.5-76.95ENEURO Journal on Computational Optimization, Vol 2, Iss 1, Pp 55-75 (2014)
institution DOAJ
collection DOAJ
language EN
topic 90C11 Mixed integer programming
90C35 Programming involving graphs or networks
90B10 Network models
deterministic
Applied mathematics. Quantitative methods
T57-57.97
Electronic computers. Computer science
QA75.5-76.95
spellingShingle 90C11 Mixed integer programming
90C35 Programming involving graphs or networks
90B10 Network models
deterministic
Applied mathematics. Quantitative methods
T57-57.97
Electronic computers. Computer science
QA75.5-76.95
Bernard Gendron
Mathieu Larose
Branch-and-price-and-cut for large-scale multicommodity capacitated fixed-charge network design
description We present a branch-and-price-and-cut algorithm for solving large-scale instances of the multicommodity capacitated fixed-charge network design problem. We assume good feasible solutions are already known and we focus on an efficient algorithm for proving the optimality of the solutions. The restricted master problem solved at each column generation iteration is obtained directly from the compact arc-based model by considering only a subset of the commodity flow variables. The pricing subproblem corresponds to a Lagrangian relaxation of the flow conservation and capacity constraints, leaving in the Lagrangian subproblem only the strong inequalities. The column generation procedure is completed by a cut generation step based on strong inequalities. The resulting column-and-row generation procedure is embedded within an enumerative scheme. Computational experiments on a large set of randomly generated instances are presented and analyzed.
format article
author Bernard Gendron
Mathieu Larose
author_facet Bernard Gendron
Mathieu Larose
author_sort Bernard Gendron
title Branch-and-price-and-cut for large-scale multicommodity capacitated fixed-charge network design
title_short Branch-and-price-and-cut for large-scale multicommodity capacitated fixed-charge network design
title_full Branch-and-price-and-cut for large-scale multicommodity capacitated fixed-charge network design
title_fullStr Branch-and-price-and-cut for large-scale multicommodity capacitated fixed-charge network design
title_full_unstemmed Branch-and-price-and-cut for large-scale multicommodity capacitated fixed-charge network design
title_sort branch-and-price-and-cut for large-scale multicommodity capacitated fixed-charge network design
publisher Elsevier
publishDate 2014
url https://doaj.org/article/9fd39dea92a84415a7c7eafe5f8d9019
work_keys_str_mv AT bernardgendron branchandpriceandcutforlargescalemulticommoditycapacitatedfixedchargenetworkdesign
AT mathieularose branchandpriceandcutforlargescalemulticommoditycapacitatedfixedchargenetworkdesign
_version_ 1718400845322649600