Optimization Online


Correlative Sparsity Structures and Semidefinite Relaxations for Concave Cost Transportation Problems with Change of Variables

Tomohiko Mizutani (mizutani***at***kanagawa-u.ac.jp)
Makoto Yamashita (Makoto.Yamashita***at***is.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/2011
Entry Accepted: 10/10/2011
Entry Last Modified: 09/27/2013

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society