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

The authors 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. The authors 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. The authors 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. The authors computational experiments on instances derived from an industrial application in freight transportation as well as on large, hard, artificial instances confirm the efficiency of the authors specialized branch-and-bound algorithm.

Language

  • English

Media Info

Subject/Index Terms

Filing Info

  • Accession Number: 01630790
  • Record Type: Publication
  • Files: TRIS
  • Created Date: Mar 7 2017 4:11PM