Skip to main content
deleted 8 characters in body
Source Link
RobPratt
  • 5.4k
  • 1
  • 15
  • 25

You can solve the problem via integer linear programming as follows. Let $P$ be the set of $n$-posets to be covered, and for $(i,j)\in [n] \times [n]$ let $a_{p,i,j}$ indicate whether $i \preceq j$ in poset $p$. We want to find a universal $m$-set if possible. For $(i,j)\in [m] \times [m]$, let binary decision variable $x_{i,j}$ indicate whether $i \preceq j$ in the universal poset. For $p \in P$, $i_1\in [n]$, and $i_2\in [m]$, let binary decision variable $y_{p,i_1,i_2}$ indicate whether element element $i_1$ in poset $p$ is assigned to element $i_2$ in the universal set. A universal $m$-poset exists if and only if the following constraints can be satisfied: \begin{align} \sum_{i_2 \in [m]} y_{p,i_1,i_2} &= 1 &&\text{for $p\in P$ and $i_1 \in [n]$} \tag1 \\ \sum_{i_1 \in [n]} y_{p,i_1,i_2} &\le 1 &&\text{for $p \in P$ and $i_2 \in [m]$} \tag2 \\ y_{p,i_1,i_2} + y_{p,j_1,j_2} - 1 &\le x_{i_2,j_2} &&\text{for $p\in P, (i_1,j_1) \in [n] \times [n], (i_2, j_2) \in [m] \times [m]$ with $a_{p,i_1,j_1}=1$} \tag3 \\ y_{p,i_1,i_2} + y_{p,j_1,j_2} - 1 &\le 1 - x_{i_2,j_2} &&\text{for $p\in P, (i_1,j_1) \in [n] \times [n], (i_2, j_2) \in [m] \times [m]$ with $a_{p,i_1,j_1}=0$} \tag4 \\ x_{i,j} + x_{j,k} - 1 &\le x_{i,k} &&\text{for $i,j,k \in [m]$} \tag5 \\ \\ \end{align} Constraint $(1)$ assigns each element in poset $p$ to exactly one element in the universal poset. Constraint $(2)$ assigns at most one element in poset $p$ to each element in the universal poset. Constraint $(3)$ enforces $$(y_{p,i_1,i_2} \land y_{p,j_1,j_2} \land a_{p,i_1,j_1}) \implies x_{i_2,j_2}.$$ Constraint $(4)$ enforces $$(y_{p,i_1,i_2} \land y_{p,j_1,j_2} \land \lnot a_{p,i_1,j_1}) \implies \lnot x_{i_2,j_2}.$$ Constraint $(5)$ enforces transitivity in the universal poset.

You can solve the problem via integer linear programming as follows. Let $P$ be the set of $n$-posets to be covered, and for $(i,j)\in [n] \times [n]$ let $a_{p,i,j}$ indicate whether $i \preceq j$ in poset $p$. We want to find a universal $m$-set if possible. For $(i,j)\in [m] \times [m]$, let binary decision variable $x_{i,j}$ indicate whether $i \preceq j$ in the universal poset. For $p \in P$, $i_1\in [n]$, and $i_2\in [m]$, let binary decision variable $y_{p,i_1,i_2}$ indicate whether element element $i_1$ in poset $p$ is assigned to $i_2$ in the universal set. A universal $m$-poset exists if and only if the following constraints can be satisfied: \begin{align} \sum_{i_2 \in [m]} y_{p,i_1,i_2} &= 1 &&\text{for $p\in P$ and $i_1 \in [n]$} \tag1 \\ \sum_{i_1 \in [n]} y_{p,i_1,i_2} &\le 1 &&\text{for $p \in P$ and $i_2 \in [m]$} \tag2 \\ y_{p,i_1,i_2} + y_{p,j_1,j_2} - 1 &\le x_{i_2,j_2} &&\text{for $p\in P, (i_1,j_1) \in [n] \times [n], (i_2, j_2) \in [m] \times [m]$ with $a_{p,i_1,j_1}=1$} \tag3 \\ y_{p,i_1,i_2} + y_{p,j_1,j_2} - 1 &\le 1 - x_{i_2,j_2} &&\text{for $p\in P, (i_1,j_1) \in [n] \times [n], (i_2, j_2) \in [m] \times [m]$ with $a_{p,i_1,j_1}=0$} \tag4 \\ x_{i,j} + x_{j,k} - 1 &\le x_{i,k} &&\text{for $i,j,k \in [m]$} \tag5 \\ \\ \end{align} Constraint $(1)$ assigns each element in poset $p$ to exactly one element in the universal poset. Constraint $(2)$ assigns at most one element in poset $p$ to each element in the universal poset. Constraint $(3)$ enforces $$(y_{p,i_1,i_2} \land y_{p,j_1,j_2} \land a_{p,i_1,j_1}) \implies x_{i_2,j_2}.$$ Constraint $(4)$ enforces $$(y_{p,i_1,i_2} \land y_{p,j_1,j_2} \land \lnot a_{p,i_1,j_1}) \implies \lnot x_{i_2,j_2}.$$ Constraint $(5)$ enforces transitivity in the universal poset.

You can solve the problem via integer linear programming as follows. Let $P$ be the set of $n$-posets to be covered, and for $(i,j)\in [n] \times [n]$ let $a_{p,i,j}$ indicate whether $i \preceq j$ in poset $p$. We want to find a universal $m$-set if possible. For $(i,j)\in [m] \times [m]$, let binary decision variable $x_{i,j}$ indicate whether $i \preceq j$ in the universal poset. For $p \in P$, $i_1\in [n]$, and $i_2\in [m]$, let binary decision variable $y_{p,i_1,i_2}$ indicate whether element $i_1$ in poset $p$ is assigned to element $i_2$ in the universal set. A universal $m$-poset exists if and only if the following constraints can be satisfied: \begin{align} \sum_{i_2 \in [m]} y_{p,i_1,i_2} &= 1 &&\text{for $p\in P$ and $i_1 \in [n]$} \tag1 \\ \sum_{i_1 \in [n]} y_{p,i_1,i_2} &\le 1 &&\text{for $p \in P$ and $i_2 \in [m]$} \tag2 \\ y_{p,i_1,i_2} + y_{p,j_1,j_2} - 1 &\le x_{i_2,j_2} &&\text{for $p\in P, (i_1,j_1) \in [n] \times [n], (i_2, j_2) \in [m] \times [m]$ with $a_{p,i_1,j_1}=1$} \tag3 \\ y_{p,i_1,i_2} + y_{p,j_1,j_2} - 1 &\le 1 - x_{i_2,j_2} &&\text{for $p\in P, (i_1,j_1) \in [n] \times [n], (i_2, j_2) \in [m] \times [m]$ with $a_{p,i_1,j_1}=0$} \tag4 \\ x_{i,j} + x_{j,k} - 1 &\le x_{i,k} &&\text{for $i,j,k \in [m]$} \tag5 \\ \\ \end{align} Constraint $(1)$ assigns each element in poset $p$ to exactly one element in the universal poset. Constraint $(2)$ assigns at most one element in poset $p$ to each element in the universal poset. Constraint $(3)$ enforces $$(y_{p,i_1,i_2} \land y_{p,j_1,j_2} \land a_{p,i_1,j_1}) \implies x_{i_2,j_2}.$$ Constraint $(4)$ enforces $$(y_{p,i_1,i_2} \land y_{p,j_1,j_2} \land \lnot a_{p,i_1,j_1}) \implies \lnot x_{i_2,j_2}.$$ Constraint $(5)$ enforces transitivity in the universal poset.

Source Link
RobPratt
  • 5.4k
  • 1
  • 15
  • 25

You can solve the problem via integer linear programming as follows. Let $P$ be the set of $n$-posets to be covered, and for $(i,j)\in [n] \times [n]$ let $a_{p,i,j}$ indicate whether $i \preceq j$ in poset $p$. We want to find a universal $m$-set if possible. For $(i,j)\in [m] \times [m]$, let binary decision variable $x_{i,j}$ indicate whether $i \preceq j$ in the universal poset. For $p \in P$, $i_1\in [n]$, and $i_2\in [m]$, let binary decision variable $y_{p,i_1,i_2}$ indicate whether element element $i_1$ in poset $p$ is assigned to $i_2$ in the universal set. A universal $m$-poset exists if and only if the following constraints can be satisfied: \begin{align} \sum_{i_2 \in [m]} y_{p,i_1,i_2} &= 1 &&\text{for $p\in P$ and $i_1 \in [n]$} \tag1 \\ \sum_{i_1 \in [n]} y_{p,i_1,i_2} &\le 1 &&\text{for $p \in P$ and $i_2 \in [m]$} \tag2 \\ y_{p,i_1,i_2} + y_{p,j_1,j_2} - 1 &\le x_{i_2,j_2} &&\text{for $p\in P, (i_1,j_1) \in [n] \times [n], (i_2, j_2) \in [m] \times [m]$ with $a_{p,i_1,j_1}=1$} \tag3 \\ y_{p,i_1,i_2} + y_{p,j_1,j_2} - 1 &\le 1 - x_{i_2,j_2} &&\text{for $p\in P, (i_1,j_1) \in [n] \times [n], (i_2, j_2) \in [m] \times [m]$ with $a_{p,i_1,j_1}=0$} \tag4 \\ x_{i,j} + x_{j,k} - 1 &\le x_{i,k} &&\text{for $i,j,k \in [m]$} \tag5 \\ \\ \end{align} Constraint $(1)$ assigns each element in poset $p$ to exactly one element in the universal poset. Constraint $(2)$ assigns at most one element in poset $p$ to each element in the universal poset. Constraint $(3)$ enforces $$(y_{p,i_1,i_2} \land y_{p,j_1,j_2} \land a_{p,i_1,j_1}) \implies x_{i_2,j_2}.$$ Constraint $(4)$ enforces $$(y_{p,i_1,i_2} \land y_{p,j_1,j_2} \land \lnot a_{p,i_1,j_1}) \implies \lnot x_{i_2,j_2}.$$ Constraint $(5)$ enforces transitivity in the universal poset.