change of variables

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

  • Tomohiko Mizutani
  • Makoto Yamashita
    • Categories Linear, Cone and Semidefinite Programming Tags , , , ,

    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 … Read more