Correlative sparsity structures and semidefinite relaxations for concave cost transportation problems with change of variables

We present a hierarchy of semidefinite programming (SDP) relaxations for solving the concave cost transportation problem (CCTP), which is known to be NP-hard, with p suppliers and q demanders. In particular, we study cases in which the cost function is quadratic or square-root concave. The key idea of our relaxation methods is in the change of variables to CCTPs, and due to this, we can construct SDP relaxations whose matrix variables are of size O((min {p, q}) ^ω ) in the relaxation order ω. The sequence of optimal values of SDP relaxations converges to the global minimum of the CCTP as the relaxation order ω goes to infinity. Furthermore, the size of the matrix variables can be reduced to O((min {p, q}) ^ω-1 ), ω ≥  2 by using Reznick’s theorem. Numerical experiments were conducted to assess the performance of the relaxation methods.