# A tighter relaxation of the mix logical constraints

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 $$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

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?
• What does Iff mean here? What is $\alpha_{ij}$? Your (1) and (2) use an unspecified $i$ index. Also, (1) and (2) mistakenly use $x_{jm}$ twice each. Apr 13 at 12:35
• @RobPratt, thanks, and sorry for my typo. I just edited it. Actually, $\alpha_{j,k}$ is an auxiliary binary variable. Apr 13 at 13:04
• Any reason why is the 2nd formulation faster? There you have two more variables and 1 additional constraint. Apr 13 at 13:32
• @Sutanu, The second formulation in practice, yields more constraints and variables. Maybe this is one of the cases. I really would like to find a tighter formulation. I have not tried yet any analysis of how the second formulation may be near to the convex hull, but I am interested to see other formulations. Apr 13 at 13:41

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).
• Many thanks for your hint. In some cases, I have seen they used $\iff$ to couple the variables. Would you please, say do you already have any suggestions for a tighter form? Apr 13 at 13:08