This work proposes a combinatorial branch-and-bound (B&B) algorithm for the capacitated facility location problem under strict customer preferences (CFLP-SCP). We use combinatorial insights into the problem structure to do preprocessing, model branching implications, enforce feasibility or prove infeasibility in each node, select variables and derive primal and dual bounds in each node of the B&B tree.
We benchmark this algorithm against the strongest currently known mixed-integer linear programming
formulation for the CFLP-SCP. We find that our B&B algorithm finds better primal solutions for more
instances and, if slowly, makes progress on solving instances with 1000 customers and 1000 facilities. In
comparison, the solver struggles with memory requirements and fails on larger instances. However, we find the linear programming based dual bounds generally outperform our combinatorial bounds, allowing the solver to prove optimality faster for small instances.