New LP Formulation

Notation

• $P\in\mathcal P$ persons
• $R\in\mathcal R$ rooms
• $A\in\mathcal A$ AKs
• $T\in B\in\mathcal B$, where $T$ is a timeslot within a time block $B$ (usually a day), we write $\mathcal T:=\cup B$

Input/Constants

• $D_A$: duraction of an AK
• $C_R$: capacity of a room
• $P_{A,P}\in{0,1,\mu} $: preference of $P$ (the higher the more important participation at $A$)
• $n$ number of people ( $\mathcal H^0(\mathcal P)$ )

Variables:

• $F_{A,X}$ denotes wether AK $A$ interacts with $X$
• if $X\in\mathcal P$, $F_{A,X}$ iff $X$ participates at $A$
• TODO: other cases

Cost function

We maximize the ratio of preferences fulfilled for each person:

$$\sum_{P\in\mathcal P}\frac{\sum_{A\in\mathcal A}P_{A,P}F_{A,P}}{\mathcal H^0({A\in\mathcal A|P_{A,P}\ne 0})}$$ where $\mathcal H^0$ is the counting measure (given the number of elements in the set).

We normalize the value for each person by the number of positive preferences to encourage people to set few preferences.

Constaints

Conflicting AKs

$$\forall (A,A')\in\binom{\mathcal A}2,X\in\mathcal R\cup\mathcal P,T\in\mathcal T~~~~~~~~ F_{A,T}+F_{A',T}+F_{A,X}+F_{A',X} \le 3$$ For pair of AKs cannot happen at the same time with the same person or in the same room

AK timing

$$\forall A\in\mathcal A ~~~~~~~~ \sum_{T\in\mathcal T}F_{A,T}\ge D_A$$ $$\forall A\in\mathcal A ~~~~~~~~ \sum_{B\in\mathcal B}F_{A,B}\le 1$$ $$\forall A\in\mathcal A,B\in\mathcal B ~~~~~~~~ \sum_{T\in B}F_{A,T}\le D_AF_{A,B}$$ each AK can happen in at most one block $$\forall A\in\mathcal A,B\in\mathcal B,T,T'\in\binom B2, |T-T'|>=D_A~~~~~~~~ F_{A,T}+F_{A,T'}\le 1$$ for each AK the distance of two timeslots where it happens can be at mosts its duration. We only need to check timeslots in the same block because of the previous constraint.

Room capacities

$$\forall A\in\mathcal A,R\in\mathcal R ~~~~~~~~ \sum_{P\in\mathcal P}F_{A,P}+n_AF_{A,R}\le n_A+C_R$$

Here $n_A$ denotes the total number of people with non-zero interest in $A$. For this cost function it is never helpful to let someone participate at some AK if they are not interested. We could also use the global constant $n$ (total number of people), but this way we hope to improve the runtime. To ensure both formulations are equivalent we add the following constraint: $$\forall A\in\mathcal A ~~~~~~~~ \sum_{P\in\mathcal P}F_{A,P}\le n_A$$

Each AK gets exactly one room. $$\forall A\in\mathcal A ~~~~~~~~ \sum_{R\in\mathcal R}F_{A,R}=1$$

Required and uninterested people

$$\forall A\in\mathcal A,P\in\mathcal P~~~~~~~~ F_{A,P}=1\text{ if $P$ is required for $A$}$$

$$\forall A\in\mathcal A,P\in\mathcal P~~~~~~~~ F_{A,P}=0\text{ if $P_{P,A}=0$}$$

RaumZeit constraints

There are some more constraints, eg. some AKs need a beamer and only some rooms offer them

$$\forall X,Y\in\mathcal P\cup\mathcal R\cup\mathcal T,A\in\mathcal A~~~~~~~~ F_{A,X}+F_{A,Y}\le1\text{ if $X$ and $Y$ cannot be combined}$$

$$\forall X\in\mathcal R\cup\mathcal T,A\in\mathcal A~~~~~~~~ F_{A,X}=0\text{ if $A$ cannot happen at $X$}$$

more on how this is implemented can be read in the input specification