{"id":{"repo_id":"vt","oai_identifier":"oai:vtechworks.lib.vt.edu:10919/45116"},"canonical_url":"https://search.dev.ndltd.org/etd/vt/oai:vtechworks.lib.vt.edu:10919/45116","repository":{"repo_id":"vt","name":"Virginia Tech","base_url":"https://vtechworks.lib.vt.edu/oai/request"},"display":{"title":"A reformulation-linearization based implicit enumeration algorithm for the rectilinear distance location-allocation problem","abstract":"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.","abstract_html":"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.","abstract_has_math":false,"creators":["Ramachandran, Sridhar"],"institution":"Virginia Tech","degree_name":"Master of Science","degree_level":"masters","degree_discipline":"Industrial and Systems Engineering","degree_department":"Industrial and Systems Engineering","school":null,"contributors":[],"advisors":[],"committee_chairs":[],"committee_members":[],"year":1991,"date_issued":"1991","date_published":"1991","updated_at":"2026-07-24T05:55:54Z","subjects":["Combinatorial enumeration problems"],"languages":["en"],"rights":["In Copyright"],"rights_urls":["http://rightsstatements.org/vocab/InC/1.0/"],"identifier_entries":[{"key":"dc:identifier.other","label":"Dc Identifier Other","values":["etd-10102009-020147"],"render_values":[{"text":"etd-10102009-020147","href":null,"code":true}]}]},"links":{"outbound_url":"http://hdl.handle.net/10919/45116","outbound_label":"Handle","outbound_source":"dc:identifier.uri"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor.department","label":"Department","values":["Industrial and Systems Engineering"]},{"key":"dc:creator","label":"Author","values":["Ramachandran, Sridhar"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date.accessioned","label":"Dc Date Accessioned","values":["2014-03-14T21:47:14Z"]},{"key":"dc:date.available","label":"Dc Date Available","values":["2014-03-14T21:47:14Z","2009-10-10"]},{"key":"dc:date.issued","label":"Date","values":["1991"]},{"key":"dc:publisher","label":"Institution","values":["Virginia Tech"]},{"key":"dc:type","label":"Dc Type","values":["Thesis"]},{"key":"dc:type.dcmitype","label":"Dc Type Dcmitype","values":["Text"]},{"key":"thesis:degree_discipline","label":"Discipline","values":["Industrial and Systems Engineering"]},{"key":"thesis:degree_level","label":"Degree Level","values":["masters"]},{"key":"thesis:degree_name","label":"Degree Name","values":["Master of Science"]},{"key":"thesis:institution_name","label":"Thesis Institution Name","values":["Virginia Polytechnic Institute and State University"]}]},{"id":"subjects_keywords","label":"Subjects and Keywords","entries":[{"key":"dc:subject","label":"Dc Subject","values":["Combinatorial enumeration problems"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language.iso","label":"Language (ISO)","values":["en"]},{"key":"dc:rights","label":"Dc Rights","values":["In Copyright"]},{"key":"dc:rights.uri","label":"Rights URI","values":["http://rightsstatements.org/vocab/InC/1.0/"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier.other","label":"Dc Identifier Other","values":["etd-10102009-020147"]},{"key":"dc:identifier.uri","label":"Identifier URI","values":["http://hdl.handle.net/10919/45116"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description.abstract","label":"Abstract","values":["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."]},{"key":"dc:description.degree","label":"Dc Description Degree","values":["Master of Science"]},{"key":"dc:format.medium","label":"Dc Format Medium","values":["BTD"]},{"key":"dc:format.mimetype","label":"Dc Format Mimetype","values":["application/pdf"]},{"key":"dc:title","label":"Title","values":["A reformulation-linearization based implicit enumeration algorithm for the rectilinear distance location-allocation problem"]}]}],"canonical_facts":{"dc:contributor.department":["Industrial and Systems Engineering"],"dc:creator":["Ramachandran, Sridhar"],"dc:date.accessioned":["2014-03-14T21:47:14Z"],"dc:date.available":["2014-03-14T21:47:14Z","2009-10-10"],"dc:date.issued":["1991"],"dc:description.abstract":["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."],"dc:description.degree":["Master of Science"],"dc:format.medium":["BTD"],"dc:format.mimetype":["application/pdf"],"dc:identifier.other":["etd-10102009-020147"],"dc:identifier.uri":["http://hdl.handle.net/10919/45116"],"dc:language.iso":["en"],"dc:publisher":["Virginia Tech"],"dc:rights":["In Copyright"],"dc:rights.uri":["http://rightsstatements.org/vocab/InC/1.0/"],"dc:subject":["Combinatorial enumeration problems"],"dc:title":["A reformulation-linearization based implicit enumeration algorithm for the rectilinear distance location-allocation problem"],"dc:type":["Thesis"],"dc:type.dcmitype":["Text"],"thesis:degree_discipline":["Industrial and Systems Engineering"],"thesis:degree_level":["masters"],"thesis:degree_name":["Master of Science"],"thesis:institution_name":["Virginia Polytechnic Institute and State University"]},"updated_at":"2026-07-24T05:55:54Z"}