[PYTHON] Linear combination optimization (timetable)

objective optimization Abstract I tried the hourly task allocation combination optimization problem using python and pulp. Referenced code [^ pakuri_moto]

Motivation Suppose you receive the following email.

Mr. ○○ ... For the event the day after tomorrow, $ I $ people have applied for the company $ J $. Since it is $ T $ per person ($ I <J $), I think there will be some free time in the allocation. ...

I thought about it for a moment, but it seems to be interesting as a general problem. On the shoulders of giants, it seems that there is a combination optimization problem. So, let's consider a three-dimensional (linear) combinatorial optimization problem that places $ J $ on the $ I, T $ plane [^ footnote1]. The 2D version is in [^ pakuri_moto], so let's consider the 3D version based on this. The point is, just increase the variable by one. Put the full code on github [^ github], and only explain the important points.

Model A 3D linear combination optimization problem with $ c_ {ijk} $ as the cost

\begin{align}
Min\left(\sum_{i\in I}\sum_{j\in J}\sum_{t\in T} c_{ijt}x_{ijt}\right)
\end{align}

Here, $ I $ is a person, $ J $ is a company, and $ T $ is a time ($ I> J $ is assumed in the story, but it is not necessary). $ x_ {ijt} $ is a variable that takes $ 0 $ or $ 1 $. $ 0 $ does not match, $ 1 $ matches and assigns. Since it is a cohesive schedule, we assume that it is time-independent (no time zones are inconvenient for each other). That is, $ c_ {ijt} $ does not depend on $ t $ [^ footnote2]. I feel like $ c_ {ijt} $, but I want to minimize it, so if $ c_ {ijk} $ is negative, it will be easier to match $ I $ and $ J $, and if $ c_ {ijk} $ is positive, It will be difficult to match. If the company appoints a person by drawing lots, all $ c_ {ijk} $ to be combined should be the same constant. Alternatively, it may be interesting for a high-level gathering to have a point system in which the company gives priority to how much priority it wants to talk to people. The implementation is as follows [^ footnote_iter].

x = {}
for i in I:
    for j in J:
        for t in T:
            x[i, j, t] = pulp.LpVariable("x({:},{:},{:})".format(i,j,t), 0, 1, pulp.LpInteger)

problem += sum(c[i,j,t] * x[i,j,t] for i in I for j in J for t in T)

Let's add constraint to this.

1. I think it can be unfortunate for each other to hit one company many times a day.
2. Humans cannot be separated, so they cannot match multiple companies at the same time.
3. Companies can't split up, so they won't match more than one person at the same time [^ footnote3].
4. It's sad if there is too much bias depending on the person, so let's hit the company with the expected value [^ footnote_expec]. The implementation is as follows.

for i in I:
  for j in J:
    problem += sum(x[i,j,t] for t in T) <= 1

for t in T:
  for i in I:
    problem += sum(x[i,j,t] for j in J) <= 1

for t in T:
  for j in J:
    problem += sum(x[i,j,t] for i in I) <= 1

for i in I:
  problem += sum(x[i,j,t] for j in J for t in T) >= min(int(expec), len(J))

I will do the above

solver = pulp.solvers.PULP_CBC_CMD()

result

For example, consider the case of $ I = (P1, .., P9), J = (C1, ..., C6), T = (T1, ..., T7) $. The cost function was decided appropriately as follows. Since it is set for $ (I, J) $ and says that it does not depend on time, there is no time bar. It is better to do it than not to match, so when it matches, it is infinitesimal (here $ (here, $ ( -1) I'm giving you a profit of $) [^ footnote4].

cc = np.array([
      [-1,  -1,  -1,  -11, -11, -11],
      [-1,  -1,  -11, -1,  -11, -11],
      [-1,  -1,  -11, -11, -1,  -11],
      [-1,  -1,  -11, -11, -11, -11],
      [-1,  -1,  -11, -11, -11, -1],
      [-1,  -11, -11, -11, -11, -1],
      [-11, -11, -1,  -11, -11, -1],
      [-11, -11, -11, -1,  -11, -1],
      [-11, -11, -11, -11, -1,  -1],
     ])

At this time, it ends immediately and the following results are obtained. I think it's probably there.

Conclusion I tried a 3D combinatorial optimization problem. Initially we assumed $ J <I <T $, but the code as a whole is going to be about any case. To be honest, there are no particularly interesting results, but I think it would be interesting if the following non-linear effects could be incorporated into the objective function.

1. Give people free time. $ \ Sum_ {j} x_ {i, j, t} \ sum_ {j} x_ {i, j, t \ pm1} $
2. Eliminate injustice a little more firmly $ (\ sum_ {j, t} x_ {i, j, t}-\ sum_ {j, t} x_ {i', j, t}) ^ {2} $. Can this be implemented as linear?
3. I want to chat with other people in my spare time, but it is better to eliminate chat with the same person May be good. $ \ Sum_ {j, t} x_ {i, j, t} \ sum_ {j, t} x_ {i', j, t} (i \ neq i') $ I would be grateful if you could let me know if you have a fatal misunderstanding in the implementation of constraint etc.

references

[^ footnote1]: In addition to work, there are likely to be various applications such as talk arrangements for meetings and timetables for marriage activities (actually there were talk arrangements [^ pycon16], [^ pycon18].).