  


Correlative Sparsity Structures and Semidefinite Relaxations for Concave Cost Transportation Problems with Change of Variables
Tomohiko Mizutani (mizutanikanagawau.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 NPhard, with $p$ suppliers and $q$ demanders. In particular, we study cases in which the cost function is quadratic or squareroot 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\})^{\omega1}), \ \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. 10731100, 2013 Download: [PDF] Entry Submitted: 10/10/2011 Modify/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  