Buffered Spectral Laplacian Sparsification for Fixed-Charge Transportation Problems
Abstract: The Fixed-Charge Transportation Problem (FCTP) is an NP-hard problem whose objective is non-convex because every route carries a fixed activation fee. We describe a way to shrink the single global MILP by removing binary variables chosen with spectral graph theory. The fixed and variable costs are merged into edge weights of a bipartite graph, and sources and demand nodes are ordered along the Fiedler vector of its Laplacian. Routes that join nodes on opposite sides of the spectral boundary are fixed to zero, except inside a quantile-controlled overlap region, the δ-buffer, which keeps capacity near the boundary. We prove an exact closed form for the fraction of removed variables, ρ(q)=(|A_||B+ |+|A+||B-|)/(mn), together with monotonicity in q, full recovery at q=1, and an identity for ρ(0) in terms of the sign fractions of the Fiedler vector. Feasibility of the masked problem is characterized through the Gale-Hoffman condition, which gives a critical quantile q^* that binary search finds in O(TMF (m,n)log(m+n)) time, where TMF is the cost of one max-flow check. We also give an a posteriori certificate that bounds the optimality gap from any lower bound, such as the LP relaxation, without solving the full MILP. We test the method on three synthetic scales (20?20, 50?50, 100?100; 20 seeds each; HiGHS). At q=0.10 the mean gap stays below 0.35% and the certified gap below 2.5%. End-to-end speedups over the unpartitioned MILP are 0.38?, 1.27? and 1.72?, so the crossover lies between 20?20 and 50?50. Seeding a full MILP with the sparsified solution recovers exactness but is slower than the sparsified pipeline (0.745 s against 0.615 s at 50?50; 6.03 s against 5.49 s at 100?100). Random and METIS masks run faster but leave larger gaps. The speedups on these instances are modest, and the main contributions are the exact reduction-ratio results, the critical-quantile search, and the optimality certificate.
Keywords: fixed-charge transportation problem, spectral graph theory, Fiedler vector, overlap buffering, MILP sparsification, Gale-Hoffman feasibility, optimality certificate
How to Cite?: Deepak Kumar Mishra, Vishal Vincent Henry, "Buffered Spectral Laplacian Sparsification for Fixed-Charge Transportation Problems", Volume 15 Issue 10, October 2026, International Journal of Science and Research (IJSR), Pages: 449-460, https://www.ijsr.net/getabstract.php?paperid=SR261005204218, DOI: https://dx.doi.org/10.21275/SR261005204218