4
$\begingroup$

The following relationship is part of my optimization model ($W_k$ denotes a binary variable)

$$W_{1} \le \cdots \le W_{k-1} \le W_{k} \le W_{k+1} \le \cdots \le W_{k^{\max}}$$

My question is, do I win anything from adding to the model the following, redundant, constraint?

$$W_{k-2} \le W_{k-1} - W_{k} + 1.0$$

This constraint says that if $W_k = 1$ and $W_{k-1} = 0$ then $W_{k-2} = 0$.

$\endgroup$
  • 2
    $\begingroup$ I do not think you gain anything with the inequality you added here, because if you look at the RHS of the inequality, we already know that $W_{k-1} - W_k \leq 0$, so all you seem to be getting is $W_{k-2} \leq 1$. Anyways, you can also try to solve the LP relaxation, and check if you are getting a stronger lower bound with the inequality you proposed included. Such a test allows you to empirically evaluate the worth of the inequality. $\endgroup$ – batwing Apr 11 at 17:05
  • $\begingroup$ Your second constraint is redundant even in the LP relaxation. Another way to look at it is that your first constraint already enforces "if $W_{k-1}=0$ then $W_{k-2}=0$" and your second implication is weaker because it has a stronger hypothesis with the same conclusion. $\endgroup$ – RobPratt Apr 11 at 18:23
  • $\begingroup$ Hi Rob. What do you mean by "stronger hypothesis"? $\endgroup$ – Clement Apr 11 at 19:28
  • $\begingroup$ By “stronger hypothesis” I mean that the “if” part of your second implication assumes more than the “if” part of your first implication. $\endgroup$ – RobPratt Apr 12 at 1:38
  • $\begingroup$ I see, thank you. $\endgroup$ – Clement Apr 12 at 7:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.