-
Notifications
You must be signed in to change notification settings - Fork 0
LP formulation
Optimierungs Ideen
- Oft haben wir so Constraints wie:
$\forall R,P: Y_{A,Z,R,P} = 0$ - Es könnte besser sein, stattdessen nur eine Constraint
$$\sum_{R,P} Y_{A,Z,R,P} = 0$$ hinzuzufügen
Notation:
-
$P$ ohne Index ist immer eine Person, auch eine Dummy-Person außer es wurde explizit ausgeschlossen. -
$Z=Z_{(B,T)}$ ist ein Zeitslot, der definiert ist durch den Block$B$ , in dem der Zeitslot steht und dem Zeitpunkt$T$ innerhalb des Blocks. -
$R$ ist immer ein Raum. -
$A$ ist immer ein AK. -
$P_A$ ist eine Dummy-Person, die nur zu AK$A$ will.
Constants
-
$S_A\in\mathbb{N}$ ist die Anzahl Zeitslots, die AK$A$ braucht -
$K_R\in\mathbb{N}$ ist die Anzahl Personen, die in den Raum$R$ passt. -
$P_{P,A}\in{0,1,\mu}$ ist die Präferenz von Person$P$ in Bezug auf AK$A$ . Hier steht$0$ dafür, dass die Person nicht am AK teilnehmen will,$1$ steht dafür, dass die Person eventuell an dem AK teilnehmen will und$\mu$ steht dafür, dass sie sehr gerne an dem AK teilnehmen will. Das$\mu$ ist sozusagen die$2$ und der exakte Wert soll empirisch ermittelt werden.
Variables:
-
$Y_{A,Z,R, P}\in{0,1}$ ist$1$ , wenn Person$P$ an AK$A$ zum Zeitslot$Z$ in Raum$R$ teilnimmt und$0$ sonst.
Equations:
-
[MaxOneAKPerPersonAndTime] Jede Person wird pro Zeitslot höchstens einem AK zu geteilt:
$$\forall Z,P\neq P_A : \sum_{R,A} Y_{A,Z,R,P}\leq 1$$ -
[AKLength] Jeder AK nutzt genau die Anzahl seiner benötigten Slots:
$$\forall A : \sum_{Z,R} Y_{A,Z,R,P_A} = S_A$$ -
[NoPartialParticipation] Für jede Person müssen wir schauen, dass sie die ganze Zeit in einem AK ist und nicht nur auf Teilen des AKs:
$$\forall A,P\neq P_A: \sum_{Z,R}\frac{1}{S_A}Y_{A,Z,R,P}\leq1$$ -
TODO FIXME BUG: NoPartialParticipation muss =1 oder =0 sein!
-
[FixedAKRooms] Ein AK wechselt nicht den Raum:
$$\forall A,R : \sum_Z \frac{1}{S_A}Y_{A,Z,R,P_A} \leq1$$ -
TODO FIXME BUG: FixedAKRooms muss =1 oder =0 sein! Idee: Variable
$X_{A,R}$ einfühern AK$A$ ist in Raum$R$ genau eine ungleich 0 und dann abgleichen. -
[AKConsecutive] Ein AK findet konsekutiv statt:
$$\forall A,R,Z_{(a, b)},Z_{(c,d)} \text{ s.t. } (a \neq c \vee |b-d| \ge S_A ) : Y_{A,Z_{(a,b)},R,P_A} + Y_{A,Z_{(c,d)},R,P_A} \leq 1$$ -
[PersonVisitingAKAtRightTimeAndRoom] Ein AK findet für Person P nur zu dem Zeitpunkt und in dem Raum statt, wann und wo er auch für die Dummy-Person stattfindet:
$$\forall A,Z,R,P\neq P_A: 0\leq Y_{A,Z,R,P_A}-Y_{A,Z,R,P}$$ -
[Roomsizes] Raumgrößen werden eingehalten:
$$\forall R, Z : \sum_{A,P\neq P_A} Y_{A,Z,R,P} \le K_R$$ -
[DummyPersonOneAk] Die Dummy-Person
$P_A$ nimmt nur an dem AK$A$ teil:$$\forall Z,R, A'\neq A: Y_{A',Z,R,P_A}=0$$
Zusatzconstraints erfüllen:
-
[PersonNotInterestedInAK] Wenn
$P_{P,A}=0$ , also echte Person$P$ ist nicht an AK$A$ interessiert:$$\forall Z,R: Y_{A,Z,R,P}=0$$ -
[PersonNeededForAK] Wenn echte Person
$P$ für AK$A$ essentiell ist (note: mit Ungleichung oben kombinieren):$$\sum_{Z,R}Y_{A,Z,R,P}=S_A$$ -
[TimeImpossibleForPerson] Echte Person
$P$ kann zu Zeit$Z$ nicht:$$\forall A,R: Y_{A,Z,R,P}=0$$ -
[RoomImpossibleForPerson] Echte Person
$P$ kann nicht in Raum$R$ :$$\forall A,Z: Y_{A,Z,R,P}=0$$ -
[RoomImpossibleForAK]AK
$A$ kann nicht in Raum$R$ stattfinden:$$\forall Z,P: Y_{A,Z,R,P}=0$$ -
[TimeImpossibleForAK] AK
$A$ kann nicht zum Zeitpunkt$Z$ stattfinden:$$\forall R,P: Y_{A,Z,R,P} = 0$$ -
[TimeImpossibleForRoom] Raum
$R$ steht zu Zeitraum$Z$ nicht zur Verfügung:$$\forall A,P: Y_{A,Z,R,P}=0$$ -
AKs
$A$ und$A'$ finden nicht gleichzeitig statt:$$\forall Z : \sum_{R} Y_{A,Z,R,P_A} + Y_{A',Z, R, P_{A'}} \le 2$$ -
TODO müsste das nicht kleiner gleich 1 sein?
-
AK
$A$ findet vor AK$A'$ statt dann können sie nicht Gleichzeitig stattfinden und folgende Ungleichung muss gelten:$$\forall Z :\sum_{Z' \le Z, R} Y_{A', Z, R, P_{A'}} - Y_{A,Z,R,P_A} < S_{A'}$$
Zielfunktion:
äquivalent minimieren wir