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

Share

COinS
 
 

To view the content in your browser, please download Adobe Reader or, alternately,
you may Download the file to your hard drive.

NOTE: The latest versions of Adobe Reader do not support viewing PDF files within Firefox on Mac OS and if you are using a modern (Intel) Mac, there is no official plugin for viewing PDF files within the browser window.