Facility layout and location, land use planning and other problems that concern the optimal assignment of activities to locations are complex combinatorial optimization problems. Such problems can be represented by the Quadratic Set Packing (QSP) model, which offers distinct computational advantages over the more general Quadratic Assignment Problem formulation. Further, a lagrangian relaxation of the QSP is a simpler relaxed assignment problem that can be solved efficiently with an exact branch and bound algorithm embedded in a program called MAFLAD (Smith and Macleod, 1988). MAFLAD is based on the assumption that the study region is tesselated by a cartesian grid, and that clusters of grid cells representing alternate locations for each activity are input by the user. The first section of this thesis addresses the topological clustering problem, that is the problem of generating clusters of grid cells for input to MAFLAD. This is a bi-criterion problem in which both attribute data and spatial location impact the optimal grouping. Initially, this bi-criterion problem is decomposed and formulated as two non-linear zero-one integer programming problems that are solved successively to identify the optimal grouping. Due to the complexity of this approach, the topological clustering problem is reformulated as a QSP problem which is optimally solved with the branch and bound algorithm embedded in MAFLAD. The efficiency of this solution method is enhanced via data reduction techniques that exploit the geometry of the topological clustering problem to reduce the depth and breadth of the branch and bound tree. The second section of this thesis presents a parallel version of MAFLAD designed for an implemented on a Sequent Symmetry S-81 multiprocessor. This is an asynchronous algorithm in which multiple processors execute the branch and bound procedure on private data while sharing the best bound. This algorithm avoids problems associated with data dependency, minimizes overhead, and exploits the tightly coupled/shared memory architecture of the Sequent multiprocessor. A heuristic for ordering the sequence of assignments in the branch and bound procedure and a data partitioning algorithm to generate input for the parallel version of MAFLAD are presented, along with the results and analysis of experiments.
| Identifer | oai:union.ndltd.org:UMASS/oai:scholarworks.umass.edu:dissertations-7911 |
| Date | 01 January 1990 |
| Creators | Smith, Julie DelVecchio |
| Publisher | ScholarWorks@UMass Amherst |
| Source Sets | University of Massachusetts, Amherst |
| Language | English |
| Detected Language | English |
| Type | text |
| Source | Doctoral Dissertations Available from Proquest |
Page generated in 0.0022 seconds