Skip to main content
tightened formulation
Source Link
RobPratt
  • 5.4k
  • 1
  • 15
  • 25

Edit: Here's an updated formulation that captures both left ($i=1$) and right ($i=2$) sides and the rule that prevents the same pair $\{j,k\}$ from appearing together on both sides: \begin{align} \sum_{p\in P} x_{i,p} &= 70 &&\text{for $i\in\{1,2\}$} \\ \sum_{p\in P_j} x_{i,p} &= j &&\text{for $i\in\{1,2\}$ and $j \in \{1,\dots,24\}$} \\ x_{i,p} &\le j\ y_{i,j,k} && \text{for $i\in\{1,2\}$ and $p\in P$ and $j<k$ with $\{j,k\}$ together in $p$} \\ y_{1,j,k} + y_{2,j,k} &\le 1 &&\text{for $1 \le j<k \le 24$} \\ x_{i,p} &\in [0,70] \cap \mathbb{Z} && \text{for $i\in\{1,2\}$ and $p\in P$} \\ y_{i,j,k} &\in \{0,1\} && \text{for $i\in\{1,2\}$ and $1 \le j<k \le 24$} \end{align}\begin{align} \sum_{p\in P} x_{i,p} &= 70 &&\text{for $i\in\{1,2\}$} \\ \sum_{p\in P_j} x_{i,p} &= j &&\text{for $i\in\{1,2\}$ and $j \in \{1,\dots,24\}$} \\ \sum_{p\in P_j \cap P_k} x_{i,p} &\le j\ y_{i,j,k} && \text{for $i\in\{1,2\}$ and $1 \le j<k \le 24$} \\ y_{1,j,k} + y_{2,j,k} &\le 1 &&\text{for $1 \le j<k \le 24$} \\ x_{i,p} &\in [0,70] \cap \mathbb{Z} && \text{for $i\in\{1,2\}$ and $p\in P$} \\ y_{i,j,k} &\in \{0,1\} && \text{for $i\in\{1,2\}$ and $1 \le j<k \le 24$} \end{align}

Edit: Here's an updated formulation that captures both left ($i=1$) and right ($i=2$) sides and the rule that prevents the same pair $\{j,k\}$ from appearing together on both sides: \begin{align} \sum_{p\in P} x_{i,p} &= 70 &&\text{for $i\in\{1,2\}$} \\ \sum_{p\in P_j} x_{i,p} &= j &&\text{for $i\in\{1,2\}$ and $j \in \{1,\dots,24\}$} \\ x_{i,p} &\le j\ y_{i,j,k} && \text{for $i\in\{1,2\}$ and $p\in P$ and $j<k$ with $\{j,k\}$ together in $p$} \\ y_{1,j,k} + y_{2,j,k} &\le 1 &&\text{for $1 \le j<k \le 24$} \\ x_{i,p} &\in [0,70] \cap \mathbb{Z} && \text{for $i\in\{1,2\}$ and $p\in P$} \\ y_{i,j,k} &\in \{0,1\} && \text{for $i\in\{1,2\}$ and $1 \le j<k \le 24$} \end{align}

Edit: Here's an updated formulation that captures both left ($i=1$) and right ($i=2$) sides and the rule that prevents the same pair $\{j,k\}$ from appearing together on both sides: \begin{align} \sum_{p\in P} x_{i,p} &= 70 &&\text{for $i\in\{1,2\}$} \\ \sum_{p\in P_j} x_{i,p} &= j &&\text{for $i\in\{1,2\}$ and $j \in \{1,\dots,24\}$} \\ \sum_{p\in P_j \cap P_k} x_{i,p} &\le j\ y_{i,j,k} && \text{for $i\in\{1,2\}$ and $1 \le j<k \le 24$} \\ y_{1,j,k} + y_{2,j,k} &\le 1 &&\text{for $1 \le j<k \le 24$} \\ x_{i,p} &\in [0,70] \cap \mathbb{Z} && \text{for $i\in\{1,2\}$ and $p\in P$} \\ y_{i,j,k} &\in \{0,1\} && \text{for $i\in\{1,2\}$ and $1 \le j<k \le 24$} \end{align}

deleted 1 character in body
Source Link
RobPratt
  • 5.4k
  • 1
  • 15
  • 25

Edit: Here's an updated formulation that captures both left ($i=1$) and right ($i=2$) sides and the rule that prevents the same pair $\{j,k\}$ from appearing together on both sides: \begin{align} \sum_{p\in P} x_{i,p} &= 70 &&\text{for $i\in\{1,2\}$} \\ \sum_{p\in P_j} x_{i,p} &= j &&\text{for $i\in\{1,2\}$ and $j \in \{1,\dots,24\}$} \\ x_{i,p} &\le 70 y_{i,j,k} && \text{for $i\in\{1,2\}$ and $p\in P$ and $j<k$ with $\{j,k\}$ together in $p$} \\ y_{1,j,k} + y_{2,j,k} &\le 1 &&\text{for $1 \le j<k \le 24$} \\ x_{i,p} &\in [0,70] \cap \mathbb{Z} && \text{for $i\in\{1,2\}$ and $p\in P$} \\ y_{i,j,k} &\in \{0,1\} && \text{for $i\in\{1,2\}$ and $1 \le j<k \le 24$} \end{align}\begin{align} \sum_{p\in P} x_{i,p} &= 70 &&\text{for $i\in\{1,2\}$} \\ \sum_{p\in P_j} x_{i,p} &= j &&\text{for $i\in\{1,2\}$ and $j \in \{1,\dots,24\}$} \\ x_{i,p} &\le j\ y_{i,j,k} && \text{for $i\in\{1,2\}$ and $p\in P$ and $j<k$ with $\{j,k\}$ together in $p$} \\ y_{1,j,k} + y_{2,j,k} &\le 1 &&\text{for $1 \le j<k \le 24$} \\ x_{i,p} &\in [0,70] \cap \mathbb{Z} && \text{for $i\in\{1,2\}$ and $p\in P$} \\ y_{i,j,k} &\in \{0,1\} && \text{for $i\in\{1,2\}$ and $1 \le j<k \le 24$} \end{align}

Edit: Here's an updated formulation that captures both left ($i=1$) and right ($i=2$) sides and the rule that prevents the same pair $\{j,k\}$ from appearing together on both sides: \begin{align} \sum_{p\in P} x_{i,p} &= 70 &&\text{for $i\in\{1,2\}$} \\ \sum_{p\in P_j} x_{i,p} &= j &&\text{for $i\in\{1,2\}$ and $j \in \{1,\dots,24\}$} \\ x_{i,p} &\le 70 y_{i,j,k} && \text{for $i\in\{1,2\}$ and $p\in P$ and $j<k$ with $\{j,k\}$ together in $p$} \\ y_{1,j,k} + y_{2,j,k} &\le 1 &&\text{for $1 \le j<k \le 24$} \\ x_{i,p} &\in [0,70] \cap \mathbb{Z} && \text{for $i\in\{1,2\}$ and $p\in P$} \\ y_{i,j,k} &\in \{0,1\} && \text{for $i\in\{1,2\}$ and $1 \le j<k \le 24$} \end{align}

Edit: Here's an updated formulation that captures both left ($i=1$) and right ($i=2$) sides and the rule that prevents the same pair $\{j,k\}$ from appearing together on both sides: \begin{align} \sum_{p\in P} x_{i,p} &= 70 &&\text{for $i\in\{1,2\}$} \\ \sum_{p\in P_j} x_{i,p} &= j &&\text{for $i\in\{1,2\}$ and $j \in \{1,\dots,24\}$} \\ x_{i,p} &\le j\ y_{i,j,k} && \text{for $i\in\{1,2\}$ and $p\in P$ and $j<k$ with $\{j,k\}$ together in $p$} \\ y_{1,j,k} + y_{2,j,k} &\le 1 &&\text{for $1 \le j<k \le 24$} \\ x_{i,p} &\in [0,70] \cap \mathbb{Z} && \text{for $i\in\{1,2\}$ and $p\in P$} \\ y_{i,j,k} &\in \{0,1\} && \text{for $i\in\{1,2\}$ and $1 \le j<k \le 24$} \end{align}

deleted 215 characters in body
Source Link
RobPratt
  • 5.4k
  • 1
  • 15
  • 25

Edit: Here's an updated formulation that captures both left ($i=1$) and right ($i=2$) sides and the rule that prevents the same pair $\{j,k\}$ from appearing together on both sides: \begin{align} \sum_{p\in P} x_{i,p} &= 70 &&\text{for $i\in\{1,2\}$} \\ \sum_{p\in P_j} x_{i,p} &= j &&\text{for $i\in\{1,2\}$ and $j \in \{1,\dots,24\}$} \\ x_{i,p} &\le y_{i,j,k} && \text{for $i\in\{1,2\}$ and $p\in P$ and $j<k$ with $\{j,k\}$ together in $p$} \\ y_{1,j,k} + y_{2,j,k} &\le 1 &&\text{for $1 \le j<k \le 24$} \\ x_{i,p} &\in \{0,1\} && \text{for $i\in\{1,2\}$ and $p\in P$} \\ y_{i,j,k} &\in \{0,1\} && \text{for $i\in\{1,2\}$ and $1 \le j<k \le 24$} \end{align}

Update: This latest integer linear programming problem is infeasible, so the original problem has no solution. That is, there is no way to decompose $K_{70,70}$ into 24 complete bipartite subgraphs $K_{i,i}$, $i=1,\dots,24$.\begin{align} \sum_{p\in P} x_{i,p} &= 70 &&\text{for $i\in\{1,2\}$} \\ \sum_{p\in P_j} x_{i,p} &= j &&\text{for $i\in\{1,2\}$ and $j \in \{1,\dots,24\}$} \\ x_{i,p} &\le 70 y_{i,j,k} && \text{for $i\in\{1,2\}$ and $p\in P$ and $j<k$ with $\{j,k\}$ together in $p$} \\ y_{1,j,k} + y_{2,j,k} &\le 1 &&\text{for $1 \le j<k \le 24$} \\ x_{i,p} &\in [0,70] \cap \mathbb{Z} && \text{for $i\in\{1,2\}$ and $p\in P$} \\ y_{i,j,k} &\in \{0,1\} && \text{for $i\in\{1,2\}$ and $1 \le j<k \le 24$} \end{align}

Edit: Here's an updated formulation that captures both left ($i=1$) and right ($i=2$) sides and the rule that prevents the same pair $\{j,k\}$ from appearing together on both sides: \begin{align} \sum_{p\in P} x_{i,p} &= 70 &&\text{for $i\in\{1,2\}$} \\ \sum_{p\in P_j} x_{i,p} &= j &&\text{for $i\in\{1,2\}$ and $j \in \{1,\dots,24\}$} \\ x_{i,p} &\le y_{i,j,k} && \text{for $i\in\{1,2\}$ and $p\in P$ and $j<k$ with $\{j,k\}$ together in $p$} \\ y_{1,j,k} + y_{2,j,k} &\le 1 &&\text{for $1 \le j<k \le 24$} \\ x_{i,p} &\in \{0,1\} && \text{for $i\in\{1,2\}$ and $p\in P$} \\ y_{i,j,k} &\in \{0,1\} && \text{for $i\in\{1,2\}$ and $1 \le j<k \le 24$} \end{align}

Update: This latest integer linear programming problem is infeasible, so the original problem has no solution. That is, there is no way to decompose $K_{70,70}$ into 24 complete bipartite subgraphs $K_{i,i}$, $i=1,\dots,24$.

Edit: Here's an updated formulation that captures both left ($i=1$) and right ($i=2$) sides and the rule that prevents the same pair $\{j,k\}$ from appearing together on both sides: \begin{align} \sum_{p\in P} x_{i,p} &= 70 &&\text{for $i\in\{1,2\}$} \\ \sum_{p\in P_j} x_{i,p} &= j &&\text{for $i\in\{1,2\}$ and $j \in \{1,\dots,24\}$} \\ x_{i,p} &\le 70 y_{i,j,k} && \text{for $i\in\{1,2\}$ and $p\in P$ and $j<k$ with $\{j,k\}$ together in $p$} \\ y_{1,j,k} + y_{2,j,k} &\le 1 &&\text{for $1 \le j<k \le 24$} \\ x_{i,p} &\in [0,70] \cap \mathbb{Z} && \text{for $i\in\{1,2\}$ and $p\in P$} \\ y_{i,j,k} &\in \{0,1\} && \text{for $i\in\{1,2\}$ and $1 \le j<k \le 24$} \end{align}

added 233 characters in body
Source Link
RobPratt
  • 5.4k
  • 1
  • 15
  • 25
Loading
added 674 characters in body
Source Link
RobPratt
  • 5.4k
  • 1
  • 15
  • 25
Loading
Source Link
RobPratt
  • 5.4k
  • 1
  • 15
  • 25
Loading