A Lagrangian-Based Branch-and-Bound Algorithm for the Two-Level Uncapacitated Facility Location Problem with Single-Assignment Constraints

A Lagrangian-Based Branch-and-Bound Algorithm for the Two-Level Uncapacitated Facility Location Problem with Single-Assignment Constraints

0.00 Avg rating0 Votes
Article ID: iaor20164869
Volume: 50
Issue: 4
Start Page Number: 1286
End Page Number: 1299
Publication Date: Nov 2016
Journal: Transportation Science
Authors: , ,
Keywords: combinatorial optimization, programming: branch and bound, programming: multiple criteria, heuristics
Abstract:

We consider the two‐level uncapacitated facility location problem with single‐assignment constraints (TUFLP‐S), a problem that arises in industrial applications in freight transportation and telecommunications. We present a new Lagrangian relaxation approach for the TUFLP‐S, based on solving a single‐level uncapacitated facility location problem (UFLP) as the Lagrangian subproblem. We also develop a Lagrangian heuristic that includes a mixed‐integer programming–based large neighborhood search heuristic exploring neighborhoods by solving a series of small UFLPs. The dual and primal bounds thus obtained are used within an enumerative algorithm that implements specialized branching rules. Our computational experiments on instances derived from an industrial application in freight transportation as well as on large, hard, artificial instances confirm the efficiency of our specialized branch‐and‐bound algorithm.

Reviews

Required fields are marked *. Your email address will not be published.