A reformulation-linearization based implicit enumeration algorithm for the rectilinear distance location-allocation problem

This thesis is concerned with the analysis of a Rectilinear Distance Location Allocation Problem, where the costs are directly proportional to rectilinear distances and the amount shipped. The problem is formulated as a Mixed Integer Bilinear Programming Problem and as a Discrete Location Allocation Problem. Using linear programming relaxations constructed via the Reformulation-Linearization Technique (RLT), the latter formulation is shown to provide stronger lower bounds and is therefore adopted for implementation. In addition, cutting planes are developed to further strengthen the linear programming relaxation. The special structure of the resulting linear program is exploited in order to get a quick lower bound via a suitable Lagrangian dual formulation. This lower bounding scheme is embedded within a finitely convergent Branch and Bound algorithm that enumerates over the location decision variable space. An illustrative example and computational experience are provided to demonstrate the efficacy of the proposed algorithm.

Name thesis:degree_name

Master of Science

Level thesis:degree_level

masters

Discipline thesis:degree_discipline

Industrial and Systems Engineering

Department dc:contributor.department

Industrial and Systems Engineering

Grantor dc:publisher

Virginia Tech

Year dc:date.issued

1991

Author dc:creator

• Ramachandran, Sridhar

• Combinatorial enumeration problems

Statement dc:rights

• In Copyright

Licence dc:rights.uri

• http://rightsstatements.org/vocab/InC/1.0/

Language dc:language.iso

en

Dc Identifier Other

etd-10102009-020147

OAI identifier oai:identifier

oai:vtechworks.lib.vt.edu:10919/45116