A new duality based approach for the problem of locating a semi-obnoxious facility

Abstract

In dieser Arbeit wird ein neuer Zugang zur Lösung des nicht-konvexen Standortproblems mit anziehenden und abstoßenden Anlagen vorgestellt. Unter Nutzung der Dualitätstheorie von Toland und Singer für d.c. Optimierungsprobleme wird die Existenz von optimalen Lösungen untersucht. Zudem werden Dualitätsaussagen, geometrische Eigenschaften und Diskretisierungsergebnisse formuliert und gezeigt. Weiterhin wird in der Arbeit eine verallgemeinerte restringierte Version des Standortproblems betrachtet. Es wird gezeigt, dass die meisten gewonnenen Resultate des unrestringierten Problems auf den restringierten Fall übertragen werden können. Schließlich werden Algorithmen zur exakten Bestimmung von optimalen Lösungen entwickelt, bei denen das nicht-konvexe Ausgangsproblem auf eine endliche Zahl von konvexen Problemen zurückgeführt wird. Die entwickelten Algorithmen sind in Matlab implementiert. Obwohl ein skalares Optimierungsproblem betrachtet wird, zeigt die Arbeit interessante Zusammenhänge zu den Bereichen der linearen Vektoroptimierung und der Geometrischen Dualitätstheorie.

This thesis presents a new approach for solving the non-convex optimization problem of locating a semi-obnoxious facility. By applying the duality theory by Toland and Singer for d.c. optimization problems the existence of optimal solutions is studied. Duality assertions, geometrical properties and discretization results are stated and proven. Moreover, this thesis considers the more general case of a constrained location problem. It is shown that most of the results obtained for the unconstrained location problem can be generalized to the constrained case. The obtained results are applied in order to formulate algorithms, which determine exact solutions by leading back the non-convex optimization problem to a finite number of convex problems. The developed algorithms are implemented as Matlab functions. Although, a scalar optimization problem is considered, this thesis shows interesting relations to the fields of linear vector optimization and geometric duality theory.