Optimization Online


A Primal Heuristic for MINLP based on Dual Information

Jesco Humpola (humpola***at***zib.de)
Armin Fügenschuh (fuegenschuh***at***hsu-hh.de)
Thomas Lehmann (lehmann***at***zib.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.

Download: [PDF]

Entry Submitted: 11/20/2013
Entry Accepted: 11/20/2013
Entry Last Modified: 11/20/2013

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society