  We study the extended version of the non-uniform, capacitated facility
location problem with multiple fulfilment channels between the facilities and
clients, each with their own channel capacities and service cost. Though the
problem has been extensively studied in the literature, all the prior works
assume a single channel of fulfilment, and the existing methods based on linear
programming, primal-dual relationships, local search heuristics etc. do not
scale for a large supply chain system involving millions of decision variables.
Using the concepts of sub-modularity and optimal transport theory, we present a
scalable algorithm for determining the set of facilities to be opened under a
cardinality constraint. By introducing various schemes such as: (i) iterative
facility selection using incremental gain, (ii) approximation of the linear
program using novel multi-stage Sinkhorn iterations, (iii) creation of
facilities one for each fulfilment channel etc., we develop a fast but a tight
approximate solution, requiring
$\mathcal{O}\left(\frac{3+k}{m}ln\left(\frac{1}{\epsilon}\right)\right)$
instances of optimal transport problems to select k facilities from m options,
each solvable in linear time. Our algorithm is implicitly endowed with all the
theoretical guarantees enjoyed by submodular maximisation problems and the
Sinkhorn distances. When compared against the state-of-the-art commercial MILP
solvers, we obtain a 100-fold speedup in computation, while the difference in
objective values lies within a narrow range of 3%.
