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$ – adrianN Jan 30 '17 at 11:08
-
$\begingroup$ It's a completely different question. I've already searched for linked questions before posting. $\endgroup$ – Salah Jan 30 '17 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 Filmus Jan 30 '17 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.♦ Jan 30 '17 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$ – gnasher729 Jan 30 '17 at 20:20
Add a comment
|
$\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.♦ Jan 30 '17 at 17:30
-
$\begingroup$ Absolutely, there are upper and lower bounds on B and C and thus on |B - C|. $\endgroup$ – Salah Jan 31 '17 at 8:51
-
1$\begingroup$ Please edit the question to state that fact. Thank you! $\endgroup$ – D.W.♦ Jan 31 '17 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$ – AlexGuevara Sep 23 '19 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.♦ Sep 23 '19 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$ – Salah Jan 30 '17 at 12:37
-
$\begingroup$ It would be interesting to see more of the formulation. $\endgroup$ – Dylan Black Jan 30 '17 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$ – Salah Jan 30 '17 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.♦ Jan 30 '17 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.
