- Treffer 1 von 1
A Primal Heuristic for MINLP based on Dual Information
Zitieren Sie bitte immer diese URN: urn:nbn:de:0297-zib-43110
- We present a novel heuristic algorithm 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 for a nonlinear relaxation. Based on the information from the KKT point we alter some of the integer variables in a locally promising way. We describe this heuristic for general MINLPs and then show how to tailor the heuristic to exploit 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.
Verfasserangaben: | Jesco Humpola, Armin Fügenschuh, Thomas Lehmann |
---|---|
Dokumentart: | ZIB-Report |
Freies Schlagwort / Tag: | Duality; Heuristics; Mixed-Integer Nonlinear Programming; Nonlinear Network Design Applications; Relaxations |
MSC-Klassifikation: | 90-XX OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING |
Datum der Erstveröffentlichung: | 21.11.2013 |
Schriftenreihe (Bandnummer): | ZIB-Report (13-49) |
ISSN: | 1438-0064 |
Verlagspublikation: | Appeared under the title "A primal heuristic for optimizing the topology of gas networks based on dual information" in: EURO Journal on Computational Optimization 2014 |
DOI: | https://doi.org/10.1007/s13675-014-0029-0 |
Lizenz (Deutsch): | Creative Commons - Namensnennung-Nicht kommerziell-Keine Bearbeitung |