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](http://www.optimization-online.org/DB_FILE/2008/10/2115.pdf).



Relax a rectangular linear assignment problem
Your constraints are incorrect if $m \ne n$. Presuming $m < n$, then the constraints would be 
$ \sum\_{i}X\_{i,j} \le 1, \sum\_{j}X\_{i,j}=1, X\_{i,j}\geq 0$, with the obvious modification for $m > n$.


This can be converted into a Square Assignment Problem by adding dummy "i" indices with zero costs (or dummy "j" indices if $m > n$). The converted problem is a standard assignment problem whose optimal objective cost is the same as that of the Rectangular Assignment Problem. Per the Integrality Theorem, the Assignment Problem, without integrality constraints, has an optimal solution consisting of all integers (which must be 0 and 1). I.e., the Square Assignment Problem can be solved as a Continuous Linear Program and will produce the correct optimal objective value for the Assignment Problem constrained to have integer (binary) solutions. Therefore, the Rectangular Assignment Problem can also be solved as a Continuous Linear Program and will produce the correct optimal objective value. Note however, that although there is a binary optimal solution, it is possible, for instance if using an interior point solver, for the Continuous Linear Program to produce a non-integer (non-binary) optimal solution (even though there is also an optimal solution which is binary).


Alternatively, note that in the original rectangular formulation, the problem has totally unimodular constraint matrix and integer constraint right-hand side, so the Integrality Theorem directly applies.


