For the following problem, can we say that its linear relaxation is equivalent to the binary problem?
Problem 1 ($y_j$ and $u_j$ are $0-1$ parameters.):
Given that $u_j=0$ the problem becomes (as $z_{ij}$ becomes zero): Problem (2)
Given that $u_j=1$ the problem becomes (as $z_{ij}$ becomes equal to $x_{ij}$ because of constraints 2 and 3): Problem (3)
Can we say that the linear relaxation of the main problem (Problem 1) is equivalent to itself? (Is the integrality gap 0?).
P.S. I will write the questions in the screenshots when I have more time.
Edit: Problem 4
$1 \geq c_{ij} \geq d_{ij} \geq 0$
Since the Problem 1 is maximization type and $d_{ij} \geq 0$ we can further remove constraints (1) and (2) and obtain Problem 4. I think the same rules should apply to it and we should be able to safely use its dual in Benders (as dual subproblem) and it should give the exact same answer. However, according to my computations, it is not the case. It kind of feels strange. It is probably related to the cuts added to the master problem, but could not be exactly sure. Do you see any reason why this could happen, do you have any explanations?
Yes, for fixed $\bar{u}$ and $\bar{y}$, the problem decomposes into a separate problem for each $i$. Each such problem can be solved by inspection, and the optimal objective value is attained by integer $x$.