1
$\begingroup$

I posted the same question on stackoverflow and immediately referred to post it here.

I want to think about the best algorithm which let the interviewer meet maximum number of candidates. Suppose that there are n candidates and one interviewer. Each of interview will be held for a fixed time, so we can consider that each interview to be given a time slot. Number of time slots are given as m. All candidates are asked to submit whether they are available for each time slots. If I put it in table format, it looks like this.

1: available
0: not available

         Aoi   Banri  ...   Nami
slot 1    1      1    ...    0
slot 2    0      1    ...    1
 .        .      .    .      .
 .        .      .     .     .
 .        .      .      .    .
slot m    0      1    ...    0
  • Possible approaches 1: solve as a matrix problem

If I interpret this as a matrix problem, it would be reduced to find the Matrix X, expressed as a product of matrices with only one-to-one column exchange, that maximizes trace(AX). A is the schedule table.

Is there any good way to do that?

  • Possible approaches 2: solve as a algorithm problem

If one can think about the best algorithm which always produces best result, it does not necessarily be a matrix problem One that comes to my mind will be something like that:

  1. Find the candidate A which has minimum number of available time slots.
  2. Among the time slots when A is available, find the slot a which has minimum number of candidates who are possible to attend.
  3. Place A on slot a. Remove both from the table.
  4. Repeat above procedure for each candidates.

In the Python code format, it may look like this.

d=[[Aoi, 1, 0, ..., 0
Banri, 1, 1, ..., 1
.
.
.
Nami,  0, 1, ..., 0
]]

d_reserved=[]

d_return=reserve_each(d, d_reserved)


def reserve_each(d, _reserved):
  d_summed = cal_sums(d) # add summ on rows and columns as the outermost row/column.
  d=d[np.argsort(d_summed[-1, :])]

  for i in range(n):
    di=d[i,1:]
    if np.max(di) < 0.1:
      if i > 1:
        researve_each(d[i-1:, :], d[:i-1,:])
      else:
        # alert!!! perhaps goes random?

    di=di[np.argmax(d[-1,1:]*d[i,1:])]

    first = 1
    for dij in di:
      if dij == 1:
        dij = dij*first
        first = 0        

    d[i,1:]=di

  return np.concatenate(d_reserved, d, axis=1))    


def cal_sums(d):
  d=np.concatenate(d, np.sum(d[:, 1:], axis=1))
  d_summed=np.concatenate(d_sorted, [0, np.sum(d[1, 1:], axis=0)])
  return d_summed

However, I can think many ways this algorithm would fail or may not be provide the best answers. I would be happy if anyone facing similar problem knows better ways to do that.

$\endgroup$
3
  • $\begingroup$ How large-scale is your problem? Do you want a custom algorithm or would you also be satisfied by modeling it as ILP and letting a generic ILP solver do the job? $\endgroup$
    – PeterD
    Jun 15 at 7:56
  • $\begingroup$ I am just trying to make an app for myself. If it can be useful I can provide it to people. At most it would be about 500 candidates and 20 interviewers, with about 10 time slots. I simplified to one interviewers because the algorithm for 20 interviewers and 10 time slots is equal to that for single interviewer and 200 time slots. $\endgroup$
    – iyui
    Jun 15 at 8:26
  • $\begingroup$ I created quick and very simple .lp with 100 000 binary variables (500*20*10). Cbc solved it in 1 sec, Scip solved it in 4 sec, Glpsol solved it in 0.4 sec, Symphony was also fast. Presolve removed abt 75 000 variables. $\endgroup$
    – user9050
    Jun 15 at 21:08

2 Answers 2

2
$\begingroup$

You can model your problem as ILP and implement it e.g., in Pythons PuLP library and solve it with commercial solvers (e.g., GUROBI or CPLEX) or non-commercial solvers such as COIN-OR. However, you would need to see how this approach would scale.

Let $i \in I$ be the set of interviewers, $j \in J$ the set of interviewees and $t \in T$ the set of slots. We now define variable $x_{ijt}$ to be a binary variable that is 1 if interviewer $i$ interviews interviewee $j$ at slot $t$. Further, let $y_{jt}$ be the parameter that shows if interviewee $j$ is available in slot $t$.

Linear Program \begin{align} \ & \max z = \sum_{i\in I}\sum_{j\in J}\sum_{t\in T} x_{ijt} \\ \\\textit{S.t.}\\ \\ & \sum_{i\in I} \sum_{t\in T} x_{ijt} \leq 1 \quad \forall j \in J & \tag1 \\ & \sum_{i\in I} x_{ijt} \leq y_{jt} \quad \forall j \in J; t \in T & \tag2 \\ & \sum_{j\in J} x_{ijt} \leq 1 \quad \forall i \in I; t \in T & \tag3 \\ & x_{ijt} \in \{0,1\} \quad \forall i \in I; j \in J; t \in T\tag4 \end{align}

The objective is to maximize the number of interviews held. Equation (1) makes sure that an interviewee is only interviewed at most once. Equation (2) makes sure that an interviewee is interviewed in a slot he is available in. Equation (3) makes sure that an interviewer interviews at most one interviewee in a slot.

$\endgroup$
0
$\begingroup$

Someone with a handlename MBo told me this problem is called Maximum Bipartite Matching problem and there is an algorithm to solve it on my stackoverflow post.

Khun's Algorithm: https://cp-algorithms.com/graph/kuhn_maximum_bipartite_matching.html#proof

I may try implementing one of the variation.

As I commented, I think I can expand this problem for more than one interviewer. In that case, just set the number of total time slots to be equal to the sum of time slots each of iterviewers is available. So that the variables can be represented in 2D array and can be solved in the same manner.

$\endgroup$
1
  • $\begingroup$ To make it scale, one may have to add a step which preconditions the 2D array of candidates and time slots into diagonally dense and elsewise sparce matrix, so that the array can be devided into sub arrays and solved parallelly as well as smaller problems. $\endgroup$
    – iyui
    Jun 20 at 4:35

Your Answer

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

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