Exact sequential choice of locations in a network

Medium to large network location problems can often be solved only approximately within reasonable computing time. Standard solution techniques focus on the tentative choice of locations embedded in an enumerative search. In contrast, the method presented here selects or rejects facilities conclusively and thus avoids costly backtracking schemes. It draws on supermodularity and Lagrangian relaxation. We rank well-known variable-fixing tests and propose a hierarchy of tests that provides an attractive time–accuracy trade-off which we assess computationally.