Skip to main content

relax Relax a rectangular linear assignment problem

I wonder if there is any literature on the following problem

$\min_{X\in R^{m\times n}}\sum_{i,j} C_{i,j}X_{i,j}, s.t. \sum_{i}X_{i,j}=\sum_{j}X_{i,j}=1, X_{i,j}\geq 0$$$\begin{array}{ll} \underset{X \in \mathbb R^{m\times n}}{\text{minimize}} & \displaystyle\sum_{i,j} C_{i,j} X_{i,j}\\ \text{subject to} & \displaystyle\sum_{i} X_{i,j} = \displaystyle\sum_{j} X_{i,j} = 1\\ & X_{i,j} \geq 0\end{array}$$

The closest related problem might be Rectangular Linear Assignment Problem (RLAP)$^\dagger$, as RLAP further constrains $X_{i,j}$ to take only 0 or 1 (refer to http://www.optimization-online.org/DB_FILE/2008/10/2115.pdf)$X_{i,j} \in \{0,1\}$. I understand that the proposed problem is a relaxrelaxed version of the RLAP. But my intuition is that the optimum for the relax problem should occur at "vertex". So, do the relaxed RLAP share the same optimum as RLAP?


$\dagger$ Solving the Rectangular assignment problem and applications.

relax a rectangular linear assignment problem

I wonder if there is any literature on the following problem

$\min_{X\in R^{m\times n}}\sum_{i,j} C_{i,j}X_{i,j}, s.t. \sum_{i}X_{i,j}=\sum_{j}X_{i,j}=1, X_{i,j}\geq 0$

The closest related problem might be Rectangular Linear Assignment Problem (RLAP), as RLAP further constrains $X_{i,j}$ to take only 0 or 1 (refer to http://www.optimization-online.org/DB_FILE/2008/10/2115.pdf). I understand that the proposed problem is a relax version of the RLAP. But my intuition is that the optimum for the relax problem should occur at "vertex". So, do the relaxed RLAP share the same optimum as RLAP?

Relax a rectangular linear assignment problem

I wonder if there is any literature on the following problem

$$\begin{array}{ll} \underset{X \in \mathbb R^{m\times n}}{\text{minimize}} & \displaystyle\sum_{i,j} C_{i,j} X_{i,j}\\ \text{subject to} & \displaystyle\sum_{i} X_{i,j} = \displaystyle\sum_{j} X_{i,j} = 1\\ & X_{i,j} \geq 0\end{array}$$

The closest related problem might be Rectangular Linear Assignment Problem (RLAP)$^\dagger$, as RLAP further constrains $X_{i,j} \in \{0,1\}$. I understand that the proposed problem is a relaxed version of the RLAP. But my intuition is that the optimum for the relax problem should occur at "vertex". So, do the relaxed RLAP share the same optimum as RLAP?


$\dagger$ Solving the Rectangular assignment problem and applications.

Source Link

relax a rectangular linear assignment problem

I wonder if there is any literature on the following problem

$\min_{X\in R^{m\times n}}\sum_{i,j} C_{i,j}X_{i,j}, s.t. \sum_{i}X_{i,j}=\sum_{j}X_{i,j}=1, X_{i,j}\geq 0$

The closest related problem might be Rectangular Linear Assignment Problem (RLAP), as RLAP further constrains $X_{i,j}$ to take only 0 or 1 (refer to http://www.optimization-online.org/DB_FILE/2008/10/2115.pdf). I understand that the proposed problem is a relax version of the RLAP. But my intuition is that the optimum for the relax problem should occur at "vertex". So, do the relaxed RLAP share the same optimum as RLAP?