"Greater than" condition in integer linear program with a binary variable

Question

How can one model the following condition in an integer linear program?

$$A = \begin{cases} 1 & \text{if } B > C\\ 0 & \text{otherwise}\end{cases}$$

where $A \in \{0,1\}$ and $B, C \in \mathbb N$. We have upper and lower bounds on both $B$ and $C$.

• adrianN: Possible duplicate of Converting If-else condition to Linear Programming
• Salah: It's a completely different question. I've already searched for linked questions before posting.
• Yuval Filmus: There is no "conversion to binary". An equation A=B-C means just that - that A equals B-C.
• D.W.: 1. Do you know an upper bound on $|B-C|$? If you do, you can use the techniques at cs.stackexchange.com/q/12102/755 ("cast to boolean"). If you don't, it's much harder (and neither of the existing answers works). Can you edit the question to clarify? 2. When you say "binary integer", do you possibly mean that its value is either 0 or 1? When you say "non-binary integer", do you mean that its value is not limited to 0 or 1? If so, you should probably include that definition in the question, as it probably won't be obvious (it's easy to assume you mean "in binary representation").
• gnasher729: You say that B and C are positive integers. In that case B > C is equivalent to B ≥ C + 1, which makes it a lot easier.

Answer 1

I think I found the answer here! It is sufficient to use the big-M method by introducing the following constraints:

B>= C + 1 - M*(1-A);

C>= B + 1 - M*A

• D.W.: This only works if we know an upper bound on $|B-C|,ドル and pick $M$ to be larger than that bound. If $B,C$ are unbounded, then this doesn't work -- there's no finite $M$ that will necessarily work.
• Salah: Absolutely, there are upper and lower bounds on B and C and thus on |B - C|.
• D.W.: Please edit the question to state that fact. Thank you!
• AlexGuevara: @D.W. I think the second inequality does not hold if B=C. Am I missing something (because you said it works?) You would end up with B>=B+1 , since A would be 0.
• D.W.: @AlexGuevara, good point. I don't think you're missing anything -- it looks to me like it doesn't work when $B=C$.

Answer 2

The second inequality of the answer of Salah doesn't hold if $B=C$. I think the correct answer is the following two inequalities:

$$ B \geq C + 1 - M (1-A) $$ $$ B \leq C + M A $$

where $M$ is an upperbound on $|B-C| + 1$.

The first inequality restricts $A$ to 0ドル$ if $B \leq C$.

For example, if $B=0$ and $C=0$, then

$$ 0 \geq 0 + 1 - M(1-A) \rightarrow A = 0 $$

The second inequality restricts $A$ to 1ドル$ if $B > C$.

For example, if $B=1$ and $C=0$, then

$$ 1 \leq 0 + M A \rightarrow A = 1 $$

Answer 3

Is it possible to enforce this through your objective function? For instance, if your objective function was $$\max A,$$ the constraint $$A\leq (B-C) M,$$ where $M$ is a "big-$M$" (large value) will work provided B is larger than C by some tolerance. The tolerance will be $\frac{1}{M},ドル i.e. $B-C \geq \frac{1}{M}$ before the constraint is properly enforced.

• Salah: Maybe I need to work around my formulation to incorporate your solution but as for now I don't see how this could be done given that variable A doesn't figure directly in the objective and also I have many constraints of this form.
• Dylan Black: It would be interesting to see more of the formulation.
• Salah: I have the variables Xi, Si, Ei and constants Ci where i=1, ...,n and a binary constant matrix A(i,j) where i,j=1, ...,n. Now Xi are computed by a set of constraints but the important for my question are following: Si>=Ej if A(j,i)==1 AND Xi>Xj (this is the one I am stuck with) Ei=Si+Ci y=max(Ei) The objective is min (y)
• D.W.: This only works if we know an upper bound on $|B-C|,ドル and pick $M$ to be larger than that bound. If $B,C$ are unbounded, then this doesn't work -- there's no finite $M$ that will necessarily work.

Answer 4

If you are in a MILP setting, then I think the following should work. Assume $\underline{B},\underline{C}$ and $\overline{B},\overline{C}$ are your respective lower/upper bounds. Then the constraint $$A \geq \frac{B-C}{\overline{B}-\underline{C}}$$ ensures that $A=1$ if $B-C$ is positive, since the RHS of the equation is between 0 and 1 in this case. When $B-C$ is negative, then the constraint is useless. The constraint $$\frac{\underline{C}-\overline{B}}{C-B}\geq A$$ ensures that $A=0$ if $B-C$ is negative, for similar reasons.

Answer 5

This is another possibility for the "greater or equal" and "lower or equal" version. For the pure greater and pure lower version you must remove the +1 resp. -1 from first constraint. You must also add a +1 to the second constraint "... >= yM+1".

enter image description here