[PYTHON] Erstellen Sie ein akademisches Programm mit Kombinationsoptimierung

Erstellen Sie ein akademisches Programm

** Sie **, das Mitglied des Exekutivkomitees der Forschungspräsentation der Gesellschaft, haben beschlossen, ein Programm für die Forschungspräsentation zu erstellen.

  • Es gab Bewerbungen für 60 Präsentationen.
  • Jede Präsentation hat ein oder zwei verwandte ** Schlüsselwörter **. ――Die Präsentationen der vier Personen werden zu einer Sitzung zusammengefasst und insgesamt 15 Sitzungen erstellt.
  • Jede Sitzung hat eine Sitzung ** Thema **. ――Die Präsentation in der Sitzung muss das Thema als Schlüsselwort enthalten. ――Sie müssen das Sitzungsthema für jede Anwendung festlegen und in 15 Sitzungen unterteilen.

Denkweise

  • Jedes Schlüsselwort aller Präsentatoren ist ein Kandidat für die Auswahl. --Stellen Sie für ein Schlüsselwort den Relevanzgrad für die Ansage mit (0-1) [^ 1] ein.
  • ** Wir maximieren die "Summe der Relevanz ausgewählter Kandidaten" **.
  • Jede Präsentation muss einer der Sitzungen zugewiesen werden. ―― Zu diesem Zweck haben einige Kandidaten für jede Präsentation eine beliebige Kategorie als Dummy.
  • Die Relevanz einer Kategorie ist sehr gering (-10).

[^ 1]: Zum Beispiel ist es möglich, mit Word2Vec zu berechnen.

Das obige Problem kann mithilfe von Kombinationsoptimierung gelöst werden. Formulieren wir es.

Maximieren $ \ sum_i {Relevanz_i x_i} $ Summe der Relevanz der zugewiesenen Kandidaten
Variablen $ x_i \ in \ {0, 1 \} $ $ x_i $: $ i $ Wählen Sie den Kandidaten aus Ob
$ y_j \ in Ganzzahl größer oder gleich 0 $ $ y_j $: $ j $ Anzahl der Sitzungen in der dritten Kategorie
Einschränkungen $ \ sum_j {y_j} = 15 $ Die Gesamtzahl der Sitzungen beträgt 15
$ \ sum_ {i \ in F_h} {x_i} = 1 ~ ~ ~ \ forall h \ in H $ Jeder Präsentation wird genau ein Schlüsselwort zugewiesen td>
$ \ sum_ {i \ in G_k} {x_i} \ le 4 y_j ~ ~ ~ \ forall k \ in C $ Die Anzahl der Präsentationen in jeder Kategorie ist geringer als die Anzahl der Frames td>

$ H $ ist jedoch eine Reihe von Präsentatoren, $ F_h $ ist eine Reihe von Kandidaten für den Moderator $ h $, $ C $ ist eine Reihe von Kategorien und $ G_k $ ist eine Reihe von Kandidaten für die Kategorie $ k $.

Wird von Python ausgeführt

Lassen Sie uns die Anwendungstabelle erstellen.

python3


import numpy as np, pandas as pd
from pulp import *
np.random.seed(3)
nu = 4 #Anzahl der Präsentationen pro Sitzung
nr = 60 #Anzahl der Moderatoren
cat = 'Kommunikation Medizinische Logistik Elektrische Energie Bauingenieurwesen Physik Chemie Geometrische Algebra Geographie'.split() #Kategorie
ns = nr / nu #Anzahl der Sitzungen
dat = [(i, j, np.random.rand()) for i in  range(nr)
       for j in np.random.choice(cat, np.random.randint(1, 3), replace=False)]
dat.extend([(i, 'Irgendein', -10) for i in range(nr)]) # Irgendeinカテゴリの追加
a = pd.DataFrame(dat, columns=['Moderator', 'Kategorie', 'Relevanz']) #Kandidat
a['vx'] = [LpVariable('vx%d'%i, cat=LpBinary) for i in a.index] #Welche Zeile soll ich wählen?
print(a[:3])
Moderator Kategorie Relevanz vx
0 0 Physisch 0.207243 vx0
1 1 power 0.492636 vx1
2 1 Organismen 0.913301 vx2

vx ist die Spalte, die der Variablen $ x $ entspricht.

Lassen Sie uns die Kategorien tabellieren.

python3


b = pd.DataFrame(cat, columns=['Name'])
b['vy'] = [LpVariable('vy%d'%j, cat=LpInteger, lowBound=0) for j in b.index] #Anzahl der Sitzungen
print(b[:3])
Name vy
0 Kommunikation vy0
1 Medizin vy1
2 Logistik vy2

vy ist die Spalte, die der Variablen $ y $ entspricht.

Formulieren und lösen Sie, um die Aufgaben zu sehen, die zu beliebigen Kategorien geworden sind.

python3


m = LpProblem(sense=LpMaximize)
m += lpDot(a.Relevanz, a.vx)
m += lpSum(b.vy) == ns #Die Gesamtzahl der Sitzungen ist gleich
for i in range(nr):
    m += lpSum(a.vx[a.Moderator==i]) == 1 # Moderatorは1カテゴリを選ぶ
for _, r in b.iterrows():
    m += lpSum(a.vx[a.Kategorie==r.Name]) <= r.vy * nu #Die Ankündigung ist geringer als die Anzahl der Frames
m.solve()
a['rx'] = a.vx.apply(value) #Zuordnungsergebnis
b['ry'] = b.vy.apply(value) #Anzahl der Sitzungsergebnisse
print(a[(a.rx > 0)&(a.Kategorie=='Irgendein')])
Moderator Kategorie Relevanz vx rx
117 26 optional -10.0 vx117 1.0

rx ist die Spalte, die das Ergebnis der Variablen $ x $ ist. Der Moderator "26" hat es einer beliebigen Kategorie zugewiesen.

Schauen wir uns die Anzahl der Präsentationen für jede Kategorie an.

python3


print(a.Kategorie[(a.rx>0)].value_counts())
Kategorie
Kommunikation 12
power 8
Physisch 8
Biologie 7
Geometrie 4
Tiefbau 4
Logistik 4
Medical 4
Geographie 4
Chemie 4
Optional 1

Da die Biologiekategorie kein Vielfaches von 4 ist, werden die verrückten 26 hier sein.

das ist alles

Recommended Posts