A tighter relaxation of the mix logical constraints

Question

Suppose the following logical form there exists.

$$Iff: (x_{j,m} \land x_{k,m}) \implies ((C_{j} \leq S_{k}) \lor (C_{k} \leq S_{j}))$$

This is well-known as a no_overlap_constraint in the parallel machine scheduling problem. One of the linearization forms that is frequently used in literature is as:

$$C_{j} \leq S_{k} + M*(1-x_{j,m}) + M*(1-x_{k,m}) + M*(\alpha_{j,k}) \quad \forall k,j,m: j<k \tag1$$ $$C_{k} \leq S_{j} + M*(1-x_{j,m}) + M*(1-x_{k,m}) + M*(1-\alpha_{j,k}) \quad \forall k,j,m: j<k \tag2$$

This linearization still leads to a weak linear relaxation that already causes a long time to solve the problem. Hence, I tried to derive another linearization form based on the following CNF transformation:

$$ Iff: (x_{j,m} \land x_{k,m}) \implies ((w_{j,k}^1 \iff C_{j} \leq S_{k}) \lor (w_{j,k}^2 \iff C_{k} \leq S_{j}))$$ $$ Iff: (x_{j,m} \land x_{k,m}) \implies (w_{j,k}^1 \lor w_{j,k}^2) $$ $$ (1-x_{j,m}) + (1-x_{k,m}) + w_{j,k}^1 + w_{j,k}^2 \geq 1 \tag3 $$ $$ C_{j} \leq S_{k} + M*(1-w_{j,k}^1) \tag4 $$ $$ C_{j} \geq S_{k} + \epsilon - (M-\epsilon)*w_{j,k}^1 \tag5 $$ $$ C_{k} \leq S_{j} + M*(1-w_{j,k}^2) \tag6 $$ $$ C_{k} \geq S_{j} + \epsilon - (M-\epsilon)*w_{j,k}^2 \tag7 $$

After solving the model with both formulations, I found that the second one, $\{(3), (4), (5), (6), (7) \}$, can be solved so faster than the first one. The first transformation takes around 28 sec, while the second just takes around 2 sec. (for the same data and environment). In both cases, the optimal solution is the same and the results are reasonable.

1. I would like to know if the second form is a correct derivation of the logical constraint(?) and if I am not lucky to get the optimal solution.
2. Is there any tighter formulation to speed up the solving process?

Answer 1

Yes, (3) through (7) yield a correct linearization of the original implication. But you don’t need to enforce $\iff$ for the $w$ variables, and so you can omit (5) and (7).