Penalty alternating direction methods for mixed-integer optimization: A new view on feasibility pumps

Björn Geißler, Antonio Morsi, Lars Schewe, Martin Schmidt

Research output: Contribution to journalArticlepeer-review

Abstract

Feasibility pumps are highly effective primal heuristics for mixed-integer linear and nonlinear optimization. However, despite their success in practice there are only a few works considering their theoretical properties. We show that feasibility pumps can be seen as alternating direction methods applied to special reformulations of the original problem, inheriting the convergence theory of these methods. Moreover, we propose a novel penalty framework that encompasses this alternating direction method, which allows us to refrain from random perturbations that are applied in standard versions of feasibility pumps in case of failure. We present a convergence theory for the new penalty based alternating direction method and compare the new variant of the feasibility pump with existing versions in an extensive numerical study for mixed-integer linear and nonlinear problems.

Original languageEnglish
Pages (from-to)1611-1636
Number of pages26
JournalSiam journal on optimization
Volume27
Issue number3
DOIs
Publication statusPublished - 8 Aug 2017

Keywords

  • Alternating direction methods
  • Feasibility pump
  • Mixed-integer linear optimization
  • Mixed-integer nonlinear optimization
  • Penalty methods

Fingerprint

Dive into the research topics of 'Penalty alternating direction methods for mixed-integer optimization: A new view on feasibility pumps'. Together they form a unique fingerprint.

Cite this