A Dual Approach To Sparse Transportation Problem

Transportation Problem is a classical model in Operation Re-search. The critical idea is how to design the transportation routes which can satisfy the delivery requirements and minimize the freights? A lot of correspond-ing theory and algorithms are proposed. With the society developing, there is a big change in supply chain. The traditional Transportation Problem model can not suit to new problem. Meanwhile, in the era of big data, sparse opti-mization becomes an international leading issue. It has been applied into Sig-nal Processing, Image Recovery, Economic Management. Two scholars in MIT combined Transportation Problem with sparse optimization and proposed Sparse Transportation Problem(STP). In this paper, we extend STP into Sparse Linear Programming(SLP). We establish corresponding Lagrangian duality theorem. Be-sides, We also design the dual algorithm to solve SLP. We do some numerical experiments and analysis the results.