I want to solve the following problem with GAMS software:
$ \min y+\frac{1}{0.05} \sum_s p^s u^s $
$s.t$
$\sum_{j \in V}\delta_j=b$
$\sum_{j\in W^s} x_j^s +q^s=1 \ \ \forall s\in S$
$ x_j^s \le \delta_j \ \ \forall s\in S , j\in W^s$
$u^s \ge \sum_{j\in W^s} d_j^s x_j^s +M^sq^s-y \ \ \forall s\in S$
$\delta_j \in \{0,1\} \ \ \forall j$
$q^s \in \{0,1\} \ \ \forall s\in S$
$x_j^s \in \{0,1\} \ \ \forall j ,s\in S$
$y \ge 0 ,u^s \ge 0 \ \ \forall s\in S$
that $\delta_j , q^s , x_j^s , y,u^s $ are variables. $p^s , M^s , d_j^s, b $ are parameter,(The parameters ($M^s , d_j^s, b$) are all positive and integer and $p^s=\frac{1}{|S|}$).$M^s$ is properly big penalty.$V$ is e set of nodes with index $j $ . and $W^s$ are subset of $V$. Also $s$ is index of set $S$ scenario.
When the problem is solved with binary variables ($\delta_j , x _j^s$), the answer obtained is the same as the answer of the problem when the variable $x_j^s$ is relaxed.
I made this comparison with various parameters $d_j^s, b$ and different size $S$, and each time the answers are identical.
Can it be proved that the answer to the original problem (when $\delta_j , x _j^s$ are binary) is always the same as the relaxed problem (when $ x _j^s$ are non negative)?
Or is this just an accident?
Thanks in advance!
I believe that if you relax $x_j^s \in \{0,1\}$ to $x_j^s \ge 0$, there will always be an optimal solution in which $x_j^s \in \{0,1\}$. Here's why.
First, if $q^s=1$, then clearly $x_j^s=0$ for all $j$. Suppose $q^s=0$. Then the fourth constraint becomes $$u^s \ge \sum_{j\in W^s} d_j^sx_j^s - y \quad \forall s\in S.$$ Suppose that $0< x_1^s,x_2^s < 1$, and that $x_1^s+x_2^s=1$. (If there are more than 2 fractional $x_j^s$ values, the logic is similar.) Assume WLOG that $d_1^s \le d_2^s$. By the third constraint, we know that $\delta_1 = \delta_2 = 1$.
So, suppose we set $x_1^2=1$ and $x_2^s=0$. The first constraint is not affected. The second and third constraints are still satisfied. The fourth constraint is still satisfied too, but it's also possible that we can make $u^s$ smaller, in which case the objective function improves.
Therefore, there is always an optimal solution in which the $x_j^s$ are binary.