0
$\begingroup$

I am trying to solve a referee assignment problem, but I simply can't think of a way to relate my variable to one of the parameters, and I hope that someone in here can help.

I have the following binary variable

  • x(r,m) = 1 if referee r is assigned match m

and the following parameters:

  • time(m,t) = 1 if match m takes place at time t
  • avail(r,t) = 1 if referee cannot officiate a game at time t

I want to define my x variable to 0, when avail(r,t)=1, but is this even possible?

$\endgroup$
2

1 Answer 1

1
$\begingroup$

Yes.

This appears to be an instance of the assignment problem. In the assignment problem, you construct a bipartite graph. The vertices on the left represent referees. The vertices on the right represent matches. You draw an edge from a referee $r$ to a match $m$ if the referee $r$ is potentially available to officiate in that match. You can use the time() and avail() parameters to work out which edges to draw. Then, a solution to the assignment problem (a maximum matching in this bipartite graph) will represent a way to assign referees to matches. Thus, this captures the restrictions you want to enforce in a simple and natural way.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.