Correlative sparsity structures and semidefinite relaxations for concave cost transportation problems with change of variables |
| |
Authors: | Tomohiko Mizutani Makoto Yamashita |
| |
Affiliation: | 1. Department of Information Systems Creation, Kanagawa University, 3-27-1 Rokkakubashi, Kanagawa-ku, Yokohama, Kanagawa, 221-8686, Japan 2. Department of Mathematical and Computing Sciences, Tokyo Institute of Technology, 2-12-1-W8-29 Ookayama, Meguro-ku, Tokyo, 52-8552, Japan
|
| |
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}) ω ) 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. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|