Type of Document Dissertation Author Al-Loughani, Intesar Mansour Author's Email Address loughani@vt.edu URN etd-7497-124042 Title Algorithmic Approaches for Solving the Euclidean Distance Location and Location-Allocation Problems Degree PhD Department Industrial and Systems Engineering Advisory Committee

Advisor Name Title Sherali, Hanif D. Committee Chair Burns, John A. Committee Member Koelling, Charles Patrick Committee Member Loganathan, G. V. Committee Member Sarin, Subhash C. Committee Member Keywords

- Reformulation-Linearization Technique
- Location-Allocation
- Location
Date of Defense 1997-07-08 Availability unrestricted AbstractThis dissertation is concerned with the development of algorithmic approaches for solvingthe minisum location and location-allocation problems in which the Euclidean metric is

used to measure distances. To overcome the nondifferentiability difficulty associated with

the Euclidean norm function, specialized solution procedures are developed for both the

location and the location-allocation problems. For the multifacility location problem

(EMFLP), two equivalent convex differentiable reformulations are proposed. The first of

these is formulated directly in the primal space, and relationships between its Karush-Kuhn-

Tucker (KKT) conditions and the necessary and sufficient optimality conditions for

EMFLP are established in order to explore the use of standard convex differentiable

nonlinear programming algorithms that are guaranteed to converge to KKT solutions. The

second equivalent differentiable formulation is derived via a Lagrangian dual approach

based on the optimum of a linear function over a unit ball (circle). For this dual approach,

which recovers Francis and Cabot's (1972) dual problem, we also characterize the

recovery of primal location decisions, hence settling an issue that has remained open since

1972. In another approach for solving EMFLP, conjugate or deflected subgradient based

algorithms along with suitable line-search strategies are proposed. The subgradient

deflection method considered is the Average Direction Strategy (ADS) imbedded within

the Variable Target Value Method (VTVM). The generation of two types of subgradients

that are employed in conjunction with ADS are investigated. The first type is a simple

valid subgradient that assigns zero components corresponding to the nondifferentiable

terms in the objective function. The second type expends more effort to derive a low-norm

member of the subdifferential in order to enhance the prospect of obtaining a descent

direction. Furthermore, a Newton-based line-search is also designed and implemented in

order to enhance the convergence behavior of the developed algorithm. Various

combinations of the above strategies are composed and evaluated on a set of test

problems. Computational results for all the proposed algorithmic approaches are

presented, using a set of test problems that include some standard problems from the

literature. These results exhibit the relative advantages of employing the new proposed

procedures.

Finally, we study the capacitated Euclidean distance location-allocation problem. There

exists no global optimization algorithm that has been developed and tested for this class of

problems, aside from a total enumeration approach. We develop a branch-and-bound

algorithm that implicitly/partially enumerates the vertices of the feasible region of the

transportation constraints in order to determine a global optimum for this nonconvex

problem. For deriving lower bounds on node subproblems, a specialized variant of the

Reformulation-Linearization Technique (RLT) is suitably designed which transforms the

representation of this nonconvex problem from the original defining space into a higher

dimensional space associated with a lower bounding (largely linear) convex program. The

maximum of the RLT relaxation based lower bound that is obtained via a deflected

subgradient strategy applied to a Lagrangian dual formulation of this problem, and another

readily computed lower bound in the projected location space is considered at each node

of the branch-and-bound tree for fathoming purposes. In addition, certain cut-set

inequalities in the allocation space, and objective function based cuts in the location space

are generated to further tighten the lower bounding relaxation. Computational experience

is provided on a set of randomly generated test problems to investigate both the RLT-based

and the projected location- space lower bounding schemes. The results indicate that

the proposed global optimization approach for this class of problem offers a promising

viable solution procedure. In fact, for two instances available available in the in the

literature, we report significantly improved solutions. The dissertation concludes with

recommendations for further research for this challenging class of problems. Data for the

collection of test problems is provided in the Appendix to facilitate further testing in this

area.

Files

Filename Size Approximate Download Time (Hours:Minutes:Seconds)

28.8 Modem 56K Modem ISDN (64 Kb) ISDN (128 Kb) Higher-speed Access ABSTRACT.PDF6.89 Kb 00:00:01 < 00:00:01 < 00:00:01 < 00:00:01 < 00:00:01 ACKNOW_2.PDF2.68 Kb < 00:00:01 < 00:00:01 < 00:00:01 < 00:00:01 < 00:00:01 APPENDIX.PDF21.55 Kb 00:00:05 00:00:03 00:00:02 00:00:01 < 00:00:01 CH1.PDF32.96 Kb 00:00:09 00:00:04 00:00:04 00:00:02 < 00:00:01 CH2.PDF74.91 Kb 00:00:20 00:00:10 00:00:09 00:00:04 < 00:00:01 CH3_1.PDF48.47 Kb 00:00:13 00:00:06 00:00:06 00:00:03 < 00:00:01 CH3_2.PDF69.78 Kb 00:00:19 00:00:09 00:00:08 00:00:04 < 00:00:01 CH3_3.PDF39.59 Kb 00:00:10 00:00:05 00:00:04 00:00:02 < 00:00:01 CH3_4.PDF46.49 Kb 00:00:12 00:00:06 00:00:05 00:00:02 < 00:00:01 CH4.PDF80.15 Kb 00:00:22 00:00:11 00:00:10 00:00:05 < 00:00:01 CH5_1.PDF31.93 Kb 00:00:08 00:00:04 00:00:03 00:00:01 < 00:00:01 CH5_10.PDF23.49 Kb 00:00:06 00:00:03 00:00:02 00:00:01 < 00:00:01 CH5_2.PDF31.19 Kb 00:00:08 00:00:04 00:00:03 00:00:01 < 00:00:01 CH5_3.PDF31.85 Kb 00:00:08 00:00:04 00:00:03 00:00:01 < 00:00:01 CH5_4.PDF23.70 Kb 00:00:06 00:00:03 00:00:02 00:00:01 < 00:00:01 CH5_5.PDF14.09 Kb 00:00:03 00:00:02 00:00:01 < 00:00:01 < 00:00:01 CH5_6.PDF40.24 Kb 00:00:11 00:00:05 00:00:05 00:00:02 < 00:00:01 CH5_7.PDF40.53 Kb 00:00:11 00:00:05 00:00:05 00:00:02 < 00:00:01 CH5_8.PDF60.89 Kb 00:00:16 00:00:08 00:00:07 00:00:03 < 00:00:01 CH5_9.PDF51.04 Kb 00:00:14 00:00:07 00:00:06 00:00:03 < 00:00:01 CH6.PDF12.61 Kb 00:00:03 00:00:01 00:00:01 < 00:00:01 < 00:00:01 CONTENT.PDF10.96 Kb 00:00:03 00:00:01 00:00:01 < 00:00:01 < 00:00:01 COVER.PDF2.32 Kb < 00:00:01 < 00:00:01 < 00:00:01 < 00:00:01 < 00:00:01 REF.PDF50.83 Kb 00:00:14 00:00:07 00:00:06 00:00:03 < 00:00:01 VITA.PDF3.68 Kb 00:00:01 < 00:00:01 < 00:00:01 < 00:00:01 < 00:00:01

Browse All Available ETDs by
( Author |
Department )

If you have questions or technical problems, please Contact DLA.