Fast bounding procedures for large instances of the Simple Plant Location Problem

Some new, simple and extremely fast bounding procedures are presented for large‐scale instances of the Simple Plant Location Problem. The lower‐bounding procedures are based on dual ascent. The fastest of them runs in $\mathcal{O}(\mathit{mn}\log m)$ time, where m and n are the number of locations and clients, respectively. The upper‐bounding procedures are based on iteratively dropping facilities, and the fastest of them runs in $\mathcal{O}(m(n+\log m))$ time. Extensive computational results show that, in practice, the procedures give very good bounds extremely quickly.