- Correlative Sparsity Structures and Semidefinite Relaxations for Concave Cost Transportation Problems with Change of Variables Tomohiko Mizutani (mizutanikanagawa-u.ac.jp) Makoto Yamashita (Makoto.Yamashitais.titech.ac.jp) Abstract: 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\})^\omega)$ in the relaxation order $\omega$. The sequence of optimal values of SDP relaxations converges to the global minimum of the CCTP as the relaxation order $\omega$ goes to infinity. Furthermore, the size of the matrix variables can be reduced to $O((\min \{p, q\})^{\omega-1}), \ \omega \ge 2$ by using Reznick's theorem. Numerical experiments were conducted to assess the performance of the relaxation methods. Keywords: transportation problem, concave cost minimization, SDP relaxation, sparsity, change of variables Category 1: Linear, Cone and Semidefinite Programming Citation: Journal of Global Optimization, 56(3), pp. 1073-1100, 2013 Download: [PDF]Entry Submitted: 10/10/2011Entry Accepted: 10/10/2011Entry Last Modified: 09/27/2013Modify/Update this entry Visitors Authors More about us Links Subscribe, Unsubscribe Digest Archive Search, Browse the Repository Submit Update Policies Coordinator's Board Classification Scheme Credits Give us feedback Optimization Journals, Sites, Societies Optimization Online is supported by the Mathematical Optmization Society.