0
$\begingroup$

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.

$\endgroup$

1 Answer 1

0
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ Hi Mark, if my understanding is right, I can say that the linear assignment problem with doubly stochastic constraint is exactly the same as the one with permutation constraints. However, I cannot find any proof of it. Would you like to provide any references? $\endgroup$
    – lisi
    Commented Mar 25, 2020 at 10:08
  • $\begingroup$ Plenty of references for this standard result: Google linear assignment problem integrality theorem $\endgroup$ Commented Mar 25, 2020 at 12:31

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .