2
$\begingroup$

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?
$\endgroup$
4
  • $\begingroup$ 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. $\endgroup$
    – RobPratt
    Apr 13, 2023 at 12:35
  • $\begingroup$ @RobPratt, thanks, and sorry for my typo. I just edited it. Actually, $\alpha_{j,k}$ is an auxiliary binary variable. $\endgroup$
    – A.Omidi
    Apr 13, 2023 at 13:04
  • $\begingroup$ Any reason why is the 2nd formulation faster? There you have two more variables and 1 additional constraint. $\endgroup$ Apr 13, 2023 at 13:32
  • $\begingroup$ @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. $\endgroup$
    – A.Omidi
    Apr 13, 2023 at 13:41

1 Answer 1

1
$\begingroup$

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).

$\endgroup$
1
  • $\begingroup$ 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? $\endgroup$
    – A.Omidi
    Apr 13, 2023 at 13:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.