I am trying to prove that $P_{FL} \subset P_{AFL}$ where \begin{align}P_{FL}&=\left\{({\bf x},{\bf y})\,\,\middle\vert\,\,\forall i,j:\sum_{j=1}^nx_{ij}=1,x_{ij}\le y_j,0\le x_{ij},y_j\le1\right\}\\P_{AFL}&=\left\{({\bf x},{\bf y})\,\,\middle\vert\,\,\forall i,j:\sum_{j=1}^nx_{ij}=1,\sum_{i=1}^mx_{ij}\le my_j,0\le x_{ij},y_j\le1\right\}.\end{align} I could get to a point that given $x_{ij} \leq y_j$ from $P_{FL}$ summing over $m$ to get $\sum\limits_{i=1}^m x_{ij} \leq my_j$. Hence, $P_{FL}$ is at least as strong as $P_{AFL}$. However, I couldn't provide a point where $P_{FL} \setminus P_{AFL}$ to prove the inclusion is strict. How can I prove it?
$\begingroup$
$\endgroup$
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
1
Without loss of generality take $m=2$. Then
$$x_i \leq y\implies\sum_{i=1}^m x_i \leq my$$
is proven by direct summation as in the OP.
On the other hand $$ \sum_{i=1}^m x_i \leq my\quad\not\!\!\!\!\implies x_i \leq y $$ is proven by carefully choosing a counterexample. I shall take $x_1 = y+\frac{\epsilon}{2}> y , x_2 = y-\epsilon$. The FL constraint is clearly violated for $i=1$, and yet the AFL constraint is satisfied:
$$ \sum_i x_i = 2y - \frac{\epsilon}{2} < 2y.$$
