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...
Guardado en:
Autores principales: | , |
---|---|
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 |