I am working on a variant of the assignment problem. The original assignment problem is as follows:
We are given a bipartite graph with 2n vertices. Each edge has a non-negative integer weight $w_{i,j}$. Missing edges can be handled by giving them very high edge weights. The problem is to find the minimum weight perfect matching. This can be expressed as a linear program:
$\min \sum_{i,j} w_{i,j}x_{i,j}$
such that
$\sum_{i}x_{i,j}=1$
$\sum_{j}x_{i,j}=1$
$x_{ij}\ge0$
This problem can be solved in polynomial time using general purpose linear programming approaches, or even specialized algorithms such as the Hungarian Algorithm.
However, I am interested in finding a perfect matching with a particular weight say W (not minimal). Naively, if we add the constraint $\sum_{i,j}w_{i,j}x_{i,j}\ge W$ to the above linear program, then I don't think we can get integer 0/1 solutions to $x_{i,j}$s since the constraints are no longer totally-unimodular (please correct me if I'm wrong on this).
Another approach I thought of was to encode it as a quadratic program with linear constraints:
$\min \left(\sum_{i,j} w_{i,j}x_{i,j} - W\right)^2$
such that
$\sum_{i}x_{i,j}=1$
$\sum_{j}x_{i,j}=1$
$x_{ij}\ge0$
If $\vec{w}$ is the vector of edge weights, then the squared term can be expressed as
$\vec{x}^{T}\textbf{Q}\vec{x}$, where the matrix $\textbf{Q} = \vec{w}\vec{w}^{T}$, which I believe is positive semidefinite.
My question is, can this quadratic program be solved in polynomial time? Will the optimal $x_{i,j}$s be 0/1 since constraints are totally-unimodular? I am not very familiar with optimization theory so any help will be appreciated.
More generally, is there a way of finding a perfect matching with a particular weight W in polynomial time? Thanks!