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...
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | article |
| Language: | EN |
| Published: |
Elsevier
2015
|
| Subjects: | |
| Online Access: | https://doaj.org/article/c6b0756f4ad04f0ea2db21dd7f5fa417 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| Summary: | 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. |
|---|