3
$\begingroup$

Consider the assignment problem where we have two groups $u = {1, \ldots, n}$ and $v = {1, \ldots, n}$. The task is to assign each of the elements of $u$ to one and only element in $v$, such that the sum of costs is minimized. The cost $c_{ij}$ is the cost of assigning $u_i$ to $v_j$. This can also be represented as bipartite graph.

I am aware that this problem can be solved using the Hungarian algorithm in $O(n^3)$ time. There is also a network flow formulation to solve the problem.

Question:

I have a slightly different variant. I have additional pair-wise assignment constraints. For example, if $u_1$ is assigned to $v_2$ then $u_2$ cannot be assigned that $v_3$. In other words, there are pair of assignments which are restricted. I understand that this can lead to situations where there might not be a feasible solution. Is there an algorithm which gives the optimal solution and returns failure if one does not exist? Any pointers on how the Hungarian algorithm or the network flow algorithms can be modified for the needful. Alternatively, can we show it that a polynomial time solution does not exist?

Mathematical formulation of the assignment problem:

Minimize: $\sum_{i=1}^n \sum_{j=1}^n c_{ij}x_{ij}$

subject to : $\sum_{i=1}^n x_{ij}=1 \quad j = 1,\ldots, n\\ \sum_{j=1}^n x_{ij}=1 \quad i = 1, \ldots, n\\x_{ij} \in \{0, 1\} \quad i, j = 1,\ldots, n$

$\endgroup$
2
  • $\begingroup$ Is it the cost $c_{ij}$ is the cost assigning $u_i$ to $v_j$? $\endgroup$ Commented Jan 21, 2019 at 1:37
  • 1
    $\begingroup$ Yes, you are correct. I will fix it. $\endgroup$ Commented Jan 21, 2019 at 1:38

1 Answer 1

Reset to default
1
+50
$\begingroup$

Suppose that when the assignment $u_i\to v_j$ is made, the assignment $u_k\to v_p$ becomes forbidden.

There is a symmetry then, because if the assignment $u_k\to v_p$ is made, it cannot have been forbidden, and so we know assignment $u_i\to v_j$ is impossible. We can express this situation, where two such assignments cannot be both made as the constraint. $$x_{i j}+x_{k p}\leq 1.$$

Supposing that an arbitrary number $M$ of such constraints are added to the problem, so that $$x_{i_m j_m}+x_{k_m p_m}\leq 1.$$ Add all the new constraints together to give $$\sum_{m=1}^{M} (x_{i_m j_m}+x_{k_m p_m})\leq M.$$ Then remove the assignment constraints $\sum_{i=1}^n x_{i j }=1$ and $\sum_{i=1}^n x_{i j }=1$, as well as the $M$ new constraints, (but not $\sum_{m=1}^{M} (x_{i_m j_m}+x_{k_m p_m})\leq M$), and the problem is a binary knapsack problem.

Therefore, your problem relaxes to a particular case of the binary knapsack problem, (one with integer weights). Although this doesn't prove anything properly about the existence of a polynomial time algorithm to your problem, it suggests there is not one, which you should be able to show.

You said you were interested in gaining insight into the problem. I suggest you investigate a set partitioning formulation. If you introduce the $x_{i_m j_m}+x_{k_m p_m}\leq 1$ constraints with slack variables $s_m\in\{0,1\}$, then you can have equality as $x_{i_m j_m}+x_{k_m p_m}+s_m= 1$. Thereby, your constraints are in the form $A x =e, x\in\{0,1\}^N$, where $A$ is a matrix with binary entries. So the problem very nicely becomes a set partitioning problem.

If $A$ is a Perfect Matrix, then the linear programming relaxation without the binary constraints is naturally integer. The same is true if $A$ is totally unimodular or Balanced, although it can be shown that the $A$ in this case is neither TU nor Balanced. However, I suspect strongly that it can be perfect.

There are a host of computational techniques to solve these problems faster than the usual branch-and-bound algorithms. For example, this problem has so-called limited subsequence, so constraint branching is likely to be very effective.

However, this advice is only really important for large problems. In practice, modern solvers can solve SPPs efficiently using heuristics, without resorting to these specialized techniques.

$\endgroup$
2
  • $\begingroup$ The proof seems to be correct. I was hoping it could provide further insight as to how to solve the problem. How would one solve the problem then? Only way I can think of is to formulate it as an Integer Linear Programming problem and use and external solver. $\endgroup$ Commented Jan 21, 2019 at 4:43
  • $\begingroup$ @Saurav, yes, that is the straightforward way. You can obtain a lower bound on your objective function by solving the assignment problem without the "forbidden pair" constraints, and add that lower bound to the problem you pass to the solver. It may improve the speed, or it may not. You'd need to experiment. See my edit though, I've written about another perspective to the problem. $\endgroup$ Commented Jan 21, 2019 at 6:01

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.