Research Reports from the Department of Operations
Document Type
Dissertation
Publication Date
8-27-1975
Abstract
This dissertation deals with four problems in Location Theory, in which all the distances involved are Euclidean distances. The first problem is the Min-max-one-location problem with arbitrary positive weights. An algorithm to solve the problem of minimizing a ratio of a convex quadratic over a positive linear function subject to a convex set bound by linear constraints is given. It is shown that this ratio problem can be solved by parametrically solving quadratic programming problems. Complementary Pivot Theory is used (Cottle and Dantzig [10]). It is shown that Hearn's Fractional Dual [26], which provides the solution to the Min-max-one-location problem with arbitrary positive weights, can be written in the form of this ratio problem. Therefore, the proposed algorithm can be used to solve the Fractional Dual. The question of finiteness is discussed. Two examples that illustrate the algorithm are given. An algorithm to solve the Min-max-one-location problem with arbitrary positive weights, through constrained optimization, is also given. The second problem is the Max-min-one-location problem restricted to a bounded set. Two algorithms to solve the equal weight problem in E2 are given. One algorithm is designed to solve problems in which the binding set is the convex hull of the given points. The other algorithm is designed to solve the extension of the binding set to a set that contains the convex hull of the given points. Although the second algorithm solves the first case, each algorithm was designed to solve the corresponding problem efficiently. A general algorithm to solve the Max-min-one-location problem with equal weights in E2 is also given. A brief discussion about the arbitrary positive weight problem is provided. The two last problems are introduced, for the first time, in this dissertation. The problems are combinatorial problems. The problems are the Min-max-two-location problem in E2 with concentrated population on the given points and with uniformly distributed population over the convex hull of the given points, respectively. As with the Max-min-one-location problem, these two problems are non-convex problems. A heuristic algorithm for the concentrated population problem was written and tested. A computer program list is given in the Appendix. Computational experiences are provided. A lower bound in the solution is found, and it is shown not to exceed 13.4% of the optimal solution. The max-cut problem in a Euclidean network is also discussed and proposed for further research. Finally, an algorithm for the uniformly distributed population problem in E2 is given. For certain well-defined situations, the algorithm may lead to a "near-to-optimal" solution. However, it seems to be acceptable since the problem is a non-convex problem.
Keywords
Operations research, Location problems (Programming), Quadratic programming, Algorithms, Combinatorial optimization, Nonconvex optimization, Mathematical optimization
Publication Title
Dissertation, Department of Operations, School of Management, Case Western Reserve University
Issue
Technical memorandum no. 381 ; Submitted in partial fulfillment of the requirements for the Degree of Doctor of Philosophy.
Rights
This work is in the public domain and may be freely downloaded for personal or academic use
Recommended Citation
Pacca, Marcos J.A.P., "Some Problems in Location Theory" (1975). Research Reports from the Department of Operations. 543.
https://commons.case.edu/wsom-ops-reports/543