A Primal Heuristic for MINLP based on Dual Information
Jesco Humpola (humpolazib.de)
Abstract: 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.
Keywords: Mixed-Integer Nonlinear Programming; Relaxations; Heuristics; Duality; Nonlinear Network Design Applications
Category 1: Applications -- Science and Engineering
Category 2: Combinatorial Optimization (Meta Heuristics )
Category 3: Nonlinear Optimization (Constrained Nonlinear Optimization )
Citation: Zuse Report 13-49, Konrad Zuse Zentrum für Informationstechnik, Takustraße 7, 14195 Berlin, Germany.
Entry Submitted: 11/20/2013
Modify/Update this entry
|Visitors||Authors||More about us||Links|
Search, Browse the Repository
Give us feedback
|Optimization Journals, Sites, Societies|