[PYTHON] Lineare Kombinationsoptimierung (Fahrplan)

objective optimization Abstract Ich habe das Problem der Optimierung der stündlichen Aufgabenzuordnungskombination mit Python und Pulp ausprobiert. Referenzierter Code [^ pakuri_moto]

Motivation Angenommen, Sie erhalten die folgende E-Mail.

Herr ○○ ... Für die Veranstaltung morgen bewerben sich $ I $ Leute für die Firma $ J $. Da es sich um $ T $ pro Person handelt ($ I <J $), denke ich, dass die Zuteilung etwas Freizeit bietet. ...

Ich habe einen Moment darüber nachgedacht, aber es scheint als allgemeines Problem interessant zu sein. Wenn ich es dem Riesen auf die Schulter lege, scheint es ein Problem mit der Kombinationsoptimierung zu geben. Betrachten wir also ein dreidimensionales (lineares) Kombinationsoptimierungsproblem, bei dem $ J $ auf der Ebene $ I, T $ liegt [^ Fußnote1]. Die 2D-Version befindet sich in [^ pakuri_moto]. Betrachten wir also die darauf basierende 3D-Version. Der Punkt ist, erhöhen Sie einfach die Variable um eins. Setzen Sie den vollständigen Code auf github [^ github] und erklären Sie nur die wichtigen Punkte.

Model Ein dreidimensionales Problem der linearen Kombinationsoptimierung mit $ c_ {ijk} $ als Kosten

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

Hier ist $ I $ eine Person, $ J $ eine Firma und $ T $ eine Stunde ($ I> J $ wird in der Geschichte angenommen, ist aber nicht notwendig). $ x_ {ijt} $ ist eine Variable, die $ 0 $ oder $ 1 $ annimmt. $ 0 $ stimmt nicht überein, $ 1 $ stimmt überein. Da es sich um einen zusammenhängenden Zeitplan handelt, gehen wir davon aus, dass er zeitunabhängig ist (keine Zeitzonen sind für einander unpraktisch). Das heißt, $ c_ {ijt} $ hängt nicht von $ t $ [^ footnote2] ab. Ich fühle mich wie $ c_ {ijt} $, aber ich möchte es minimieren. Wenn also $ c_ {ijk} $ negativ ist, ist es einfacher, $ I $ und $ J $ zu finden, und wenn $ c_ {ijk} $ positiv ist, Es wird schwierig sein zu passen. Wenn das Unternehmen eine Person per Lotterie ernennt, sollten alle zu kombinierenden $ c_ {ijk} $ dieselbe Konstante sein. Alternativ kann es für hochrangige Versammlungen interessant sein, ein Punktesystem zu haben, in dem Unternehmen der Priorität, mit der sie mit Menschen sprechen möchten, Vorrang einräumen. Die Implementierung ist wie folgt [^ 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)

Fügen wir dem eine Einschränkung hinzu.

1. Ich denke, es kann für einander unglücklich sein, ein Unternehmen mehrmals am Tag zu treffen.
2. Menschen können nicht getrennt werden, so dass sie nicht gleichzeitig mit mehreren Unternehmen übereinstimmen können.
3. Unternehmen können sich nicht aufteilen, sodass sie nicht mehr als einer Person gleichzeitig entsprechen [^ Fußnote 3].
4. Es ist traurig, wenn es je nach Person zu viele Vorurteile gibt. Lassen Sie uns also das Unternehmen mit dem erwarteten Wert [^ footnote_expec] treffen. Die Implementierung ist wie folgt.

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))

Ich werde das oben genannte tun

solver = pulp.solvers.PULP_CBC_CMD()

Ergebnis

Betrachten Sie zum Beispiel den Fall von $ I = (P1, .., P9), J = (C1, ..., C6), T = (T1, ..., T7) $. Die Kostenfunktion wurde wie folgt angemessen festgelegt. Da es auf $ (I, J) $ gesetzt ist und sagt, dass es nicht von der Zeit abhängt, gibt es keinen Zeitrahmen. Es ist besser, es zu tun als nicht zu passen. Wenn es also passt, ist es unendlich klein (hier $ (hier $ (hier)) -1) Ich gebe Ihnen einen Gewinn von $) [^ Fußnote4].

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],
     ])

Zu diesem Zeitpunkt endet es sofort und die folgenden Ergebnisse werden erhalten. Ich denke es ist wahrscheinlich da.

Conclusion Ich habe ein Problem mit der Optimierung der 3D-Kombination versucht. Anfangs haben wir $ J <I <T $ angenommen, aber der Code als Ganzes wird auf jeden Fall sein. Um ehrlich zu sein, gibt es keine besonders interessanten Ergebnisse, aber ich denke, es wäre interessant, wenn die folgenden nichtlinearen Effekte in die Zielfunktion einbezogen werden könnten.

1. Ich werde den Leuten Freizeit geben. $ \ Sum_ {j} x_ {i, j, t} \ sum_ {j} x_ {i, j, t \ pm1} $
2. Beseitigen Sie die Ungerechtigkeit etwas fester $ (\ sum_ {j, t} x_ {i, j, t} - \ sum_ {j, t} x_ {i ', j, t}) ^ {2} $. Kann dies linear implementiert werden?
3. Ich möchte in meiner Freizeit mit anderen Personen chatten, aber es ist besser, nicht mit derselben Person zu chatten Vielleicht. $ \ Sum_ {j, t} x_ {i, j, t} \ sum_ {j, t} x_ {i ', j, t} (i \ neq i') $ Ich wäre Ihnen dankbar, wenn Sie mich wissen lassen könnten, wenn Sie aufgrund der Implementierung von Einschränkungen usw. ein schwerwiegendes Missverständnis haben.

references

[^ Fußnote 1]: Zusätzlich zur Arbeit gibt es wahrscheinlich verschiedene Anwendungen, wie z. B. Besprechungsgespräche und Zeitpläne für Heiratsaktivitäten (tatsächlich gab es Gesprächsvereinbarungen [^ pycon16], [^ pycon18]).