Conditional constraint

[Dinna]

Hi,

Does anybody know how to write conditional constraint in mixed integer programming for this case:

if a == 0 then b = 1
else b = 0
-M <= a <= M
b={0,1}

M can be any number. Thanks.

Regards,

Dinna

[Daniel Espinoza]

Dinna,

As far as I know, If a is a continuous variable; then you are out of luck; in essence your condition would be encoding a strict inequality; which would break many theoretical and numerical things.

What I've seen people do is to formulate

 |a| <= epsilon implies b = 1

Still; the formulation would be weak if M is large.

Best regards,

Daniel

[Tobias Achterberg]

Daniel is right: deciding whether a continuous variable is exactly zero or not
is pretty much impossible in a MIP framework due to the feasibility tolerances
involved.

But if a is an integer variable, then you can model your if-then-else statement
as follows:

a - M u <= 0 // a > 0 => u = 1
a - (M+1)u >= -M // u = 1 => a > 0
a + M v >= 0 // a < 0 => v = 1
a + (M+1)v <= M // v = 1 => a < 0
b + u + v == 1 // u == v == 0 <=> b = 1

-M <= a <= M

u, v, b binary
a integer


Best regards,

Tobias

[Dinna]

Thanks Daniel and Tobias!

It's actually possible with a small tolerance (eps). I found an approach to do it by introducing 2 non-negative variables and 1 binary variable:

0 <= aplus <= d * M

0 <= amin <= (1-d) * M

a = aplus - amin

eps * (1-b) <= aplus + amin <= M * b

Regards,

Dinna

[Hanan]

Hi Tobias

I have been able to find a solution to my problem, but I would appreciate to understand why my initial attempt at using your prescribed "conditional constraint" (if a=0 then b=1) does not work.
I've tried to use your suggestion to solve the following problem:
I have a sequence of binary variables (y_i), and I want their sum to be either of two values (v_1, v_2).
Using your suggestion I declared an integer variable a_1 and with a constraint a_1=sum(y_i)-v_1,
and a_2 with the constraint a_2=sum(y_i)-v_2.
From your "conditional constraint" I get b_1=1 when a_1=0, and b_2=1 when a_2=0.
I then use an or contraint b=or(b_1,b_2)
Finally I add a constraint that b==1

When implemented in my problem I started getting IIS problems.

I tested this in a simplified scenario:
integer var:x, lb=0, ub=4
b1=conditional_constraint(x==4)
b2=conditional_constraint(x==0)
b=or(b1,b2)
b==1

trying obj=x, maximize
I get x=4, b=1, b1=1, b2=0 as expected

trying obj=x, minimize
strangely enough i get the same result (x=4.....) and not x=0

when changing the first constraint to b1=conditional_constraint(x==2) I get x=2 (either for maximization or minimization).

What is wrong with this approach?

I ended up using the syntax addConstr(a=[v_1,v_2]) for the (not so well documented) range constraint which works as expected.

However this approach only works for numeric values, how would I implement a similar solution when I want to constraint the variable a to a set of combined numeric and variable values?

Thanks

Hanan


בתאריך יום שני, 13 ביוני 2016 בשעה 16:43:55 UTC+3, מאת Tobias Achterberg:

[Tobias Achterberg]

But the range constraint

addConstr(a=[v_1,v_2])

will only have the desired effect if v_2 = v_1+1. For example, if the range is [3,5], then
the range constraint also allows to set a = 4, which is, as far as I understand, not what
you want.

Your initial try should work. I guess you just made some mistake in the implementation of
the model. You can simplify it a little bit like this:

a = sum(y_i)
b = 0 -> a = v_1
b = 1 -> a = v_2

with an auxiliary integer variable a and an auxiliary binary variable b.

Alternatively, you can just use a single linear constraint:

sum(y_i) + (v_1 - v_2) b = v_1

This should already do the trick: if b == 0, then the constraint says that sum(y_i) should
be equal to v_1. On the other hand, if b == 1, then the constraint reduces to sum(y_i) ==
v_2. Since b is declared to be binary, the solution must end up in one of these two cases.


Regards,

Tobias

[Hanan]

Thanks

I already found out that the range constraint does not solve my problem

your second solution seems very elegant - I'll try that, hopefully that will solve the issue

I'm attaching my implementation of the conditional constraint. Please see if it looks OK

Regards,

Hanan

בתאריך יום שני, 27 בנובמבר 2017 בשעה 10:44:26 UTC+2, מאת Tobias Achterberg:

[Tobias Achterberg]

Your code seems correct, but pretty complicated. You could easily do this with indicator
constraints. You want to model

b = 1 <=> sum(y_i) = v

Thus, you only need the indicator constraints

b = 1 -> sum(y_i) = v
b = 0 -> b1 + b2 = 1
b1 = 1 -> sum(y_i) <= v-1
b2 = 1 -> sum(y_i) >= v+1

The first indicator is just the "=>" direction of your original constraint. The second
introduces two auxiliary binary variables b1 and b2 which model the two cases of the
strict inequality, namely that sum(y_i) is less than or greater than v. This relationship
then has to be enforced by the third and fourth indicator constraint.

The second constraint can also be modeled as equation "b + b1 + b2 = 1", which is probably
a bit better (because it yields the tighter LP relaxation).


Regards,

Tobias