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$.
$\begingroup$
$\endgroup$
5
-
$\begingroup$ Possible duplicate of Converting If-else condition to Linear Programming $\endgroup$– adrianNCommented Jan 30, 2017 at 11:08
-
$\begingroup$ It's a completely different question. I've already searched for linked questions before posting. $\endgroup$– SalahCommented Jan 30, 2017 at 11:16
-
$\begingroup$ There is no "conversion to binary". An equation A=B-C means just that - that A equals B-C. $\endgroup$– Yuval FilmusCommented Jan 30, 2017 at 13:18
-
$\begingroup$ 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"). $\endgroup$– D.W. ♦Commented Jan 30, 2017 at 17:30
-
$\begingroup$ 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. $\endgroup$– gnasher729Commented Jan 30, 2017 at 20:20
Add a comment
|
5 Answers
$\begingroup$
$\endgroup$
5
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
-
1$\begingroup$ 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. $\endgroup$– D.W. ♦Commented Jan 30, 2017 at 17:30
-
$\begingroup$ Absolutely, there are upper and lower bounds on B and C and thus on |B - C|. $\endgroup$– SalahCommented Jan 31, 2017 at 8:51
-
1$\begingroup$ Please edit the question to state that fact. Thank you! $\endgroup$– D.W. ♦Commented Jan 31, 2017 at 14:35
-
1$\begingroup$ @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. $\endgroup$ Commented Sep 23, 2019 at 8:22
-
1$\begingroup$ @AlexGuevara, good point. I don't think you're missing anything -- it looks to me like it doesn't work when $B=C$. $\endgroup$– D.W. ♦Commented Sep 23, 2019 at 15:20
$\begingroup$
$\endgroup$
0
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 $$
$\begingroup$
$\endgroup$
4
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.
-
$\begingroup$ 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. $\endgroup$– SalahCommented Jan 30, 2017 at 12:37
-
$\begingroup$ It would be interesting to see more of the formulation. $\endgroup$ Commented Jan 30, 2017 at 13:10
-
$\begingroup$ 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) $\endgroup$– SalahCommented Jan 30, 2017 at 13:37
-
1$\begingroup$ 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. $\endgroup$– D.W. ♦Commented Jan 30, 2017 at 17:31
$\begingroup$
$\endgroup$
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.
$\begingroup$
$\endgroup$
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".
