A primal heuristic for optimizing the topology of gas networks based on dual information

We present a novel heuristic to identify feasible solutions of a mixed-integer nonlinear programming problem arising in natural gas transportation: the selection of new pipelines to enhance the network’s capacity to a desired level in a cost-efficient way. We solve this problem in a linear programmi...

Full description

Saved in:

Bibliographic Details
Main Authors:	Jesco Humpola, Armin Fügenschuh, Thomas Lehmann
Format:	article
Language:	EN
Published:	Elsevier 2015
Subjects:	90-xx Mathematical Programming Operations Research Applied mathematics. Quantitative methods T57-57.97 Electronic computers. Computer science QA75.5-76.95
Online Access:	https://doaj.org/article/c6b0756f4ad04f0ea2db21dd7f5fa417
Tags:	Add Tag No Tags, Be the first to tag this record!

id	oai:doaj.org-article:c6b0756f4ad04f0ea2db21dd7f5fa417
record_format	dspace
spelling	oai:doaj.org-article:c6b0756f4ad04f0ea2db21dd7f5fa4172021-12-02T05:00:42ZA primal heuristic for optimizing the topology of gas networks based on dual information2192-440610.1007/s13675-014-0029-0https://doaj.org/article/c6b0756f4ad04f0ea2db21dd7f5fa4172015-02-01T00:00:00Zhttp://www.sciencedirect.com/science/article/pii/S2192440621000393https://doaj.org/toc/2192-4406We present a novel heuristic to identify feasible solutions of a mixed-integer nonlinear programming problem arising in natural gas transportation: the selection of new pipelines to enhance the network’s capacity to a desired level in a cost-efficient way. We solve this problem in a linear programming based branch-and-cut approach, where we deal with the nonlinearities by linear outer approximation and spatial branching. At certain nodes of the branching tree, we compute a KKT point of a nonlinear relaxation. Based on the information from the KKT point we alter some of the binary variables in a locally promising way exploiting our problem-specific structure. On a test set of real-world instances, we are able to increase the chance of identifying feasible solutions by some order of magnitude compared to standard MINLP heuristics that are already built in the general-purpose MINLP solver SCIP.Jesco HumpolaArmin FügenschuhThomas LehmannElsevierarticle90-xx Mathematical ProgrammingOperations ResearchApplied mathematics. Quantitative methodsT57-57.97Electronic computers. Computer scienceQA75.5-76.95ENEURO Journal on Computational Optimization, Vol 3, Iss 1, Pp 53-78 (2015)
institution	DOAJ
collection	DOAJ
language	EN
topic	90-xx Mathematical Programming Operations Research Applied mathematics. Quantitative methods T57-57.97 Electronic computers. Computer science QA75.5-76.95
spellingShingle	90-xx Mathematical Programming Operations Research Applied mathematics. Quantitative methods T57-57.97 Electronic computers. Computer science QA75.5-76.95 Jesco Humpola Armin Fügenschuh Thomas Lehmann A primal heuristic for optimizing the topology of gas networks based on dual information
description	We present a novel heuristic to identify feasible solutions of a mixed-integer nonlinear programming problem arising in natural gas transportation: the selection of new pipelines to enhance the network’s capacity to a desired level in a cost-efficient way. We solve this problem in a linear programming based branch-and-cut approach, where we deal with the nonlinearities by linear outer approximation and spatial branching. At certain nodes of the branching tree, we compute a KKT point of a nonlinear relaxation. Based on the information from the KKT point we alter some of the binary variables in a locally promising way exploiting our problem-specific structure. On a test set of real-world instances, we are able to increase the chance of identifying feasible solutions by some order of magnitude compared to standard MINLP heuristics that are already built in the general-purpose MINLP solver SCIP.
format	article
author	Jesco Humpola Armin Fügenschuh Thomas Lehmann
author_facet	Jesco Humpola Armin Fügenschuh Thomas Lehmann
author_sort	Jesco Humpola
title	A primal heuristic for optimizing the topology of gas networks based on dual information
title_short	A primal heuristic for optimizing the topology of gas networks based on dual information
title_full	A primal heuristic for optimizing the topology of gas networks based on dual information
title_fullStr	A primal heuristic for optimizing the topology of gas networks based on dual information
title_full_unstemmed	A primal heuristic for optimizing the topology of gas networks based on dual information
title_sort	primal heuristic for optimizing the topology of gas networks based on dual information
publisher	Elsevier
publishDate	2015
url	https://doaj.org/article/c6b0756f4ad04f0ea2db21dd7f5fa417
work_keys_str_mv	AT jescohumpola aprimalheuristicforoptimizingthetopologyofgasnetworksbasedondualinformation AT arminfugenschuh aprimalheuristicforoptimizingthetopologyofgasnetworksbasedondualinformation AT thomaslehmann aprimalheuristicforoptimizingthetopologyofgasnetworksbasedondualinformation AT jescohumpola primalheuristicforoptimizingthetopologyofgasnetworksbasedondualinformation AT arminfugenschuh primalheuristicforoptimizingthetopologyofgasnetworksbasedondualinformation AT thomaslehmann primalheuristicforoptimizingthetopologyofgasnetworksbasedondualinformation
_version_	1718400852740276224

A primal heuristic for optimizing the topology of gas networks based on dual information

Similar Items