Penalty Alternating Direction Methods for Mixed-Integer Optimization: A New View on Feasibility Pumps

Beitrag in einer Fachzeitschrift
(Originalarbeit)


Details zur Publikation

Autorinnen und Autoren: Geißler B, Morsi A, Schewe L, Schmidt M
Zeitschrift: SIAM Journal on Optimization
Verlag: Taylor & Francis
Jahr der Veröffentlichung: 2017
Band: 27
Heftnummer: 3
Seitenbereich: 1611-1636
ISSN: 1052-6234
Sprache: Englisch


Abstract


Feasibility pumps are highly effective primal heuristics for mixed-integer linear and nonlinear optimization. However, despite their success in practice there are only 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.



FAU-Autorinnen und Autoren / FAU-Herausgeberinnen und Herausgeber

Geißler, Björn Dr.
Lehrstuhl für Angewandte Mathematik (Gemischt-ganzzahlige lineare und nichtlineare Optimierung)
Morsi, Antonio Dr.
Lehrstuhl für Angewandte Mathematik (Gemischt-ganzzahlige lineare und nichtlineare Optimierung)
Schewe, Lars PD Dr.
Lehrstuhl für Angewandte Mathematik (Gemischt-ganzzahlige lineare und nichtlineare Optimierung)
Schmidt, Martin Prof. Dr.
Juniorprofessur für Optimierung von Energiesystemen


Zitierweisen

APA:
Geißler, B., Morsi, A., Schewe, L., & Schmidt, M. (2017). Penalty Alternating Direction Methods for Mixed-Integer Optimization: A New View on Feasibility Pumps. SIAM Journal on Optimization, 27(3), 1611-1636. https://dx.doi.org/10.1137/16M1069687

MLA:
Geißler, Björn, et al. "Penalty Alternating Direction Methods for Mixed-Integer Optimization: A New View on Feasibility Pumps." SIAM Journal on Optimization 27.3 (2017): 1611-1636.

BibTeX: 

Zuletzt aktualisiert 2018-11-08 um 02:24