If-Then-Else with multiple assignment in Integer Linear Programming (ILP)

Question

I have an ILP problem in which I expressed some constraint to implement A OR B, where A and B are results of logical AND (let's say that A = A1 AND A2, B = B1 AND B2 AND B3). At this point of my problem, one between A and B is said to be equal to 1. Both A and B are binary variables.

I want to express, with If-Then-Else, this assertion:

if (A == true)
   /* Choose one between C and D */
   C_OR_D >= C;
   C_OR_D >= D;
   C_OR_D <= C + D;
   C_OR_D = 1; 
else                                     /* or if (B == true), that's the same */
   /* Choose one between E and F */
   E_OR_F >= E;
   E_OR_F >= F;
   E_OR_F <= E + F;
   E_OR_F = 1;

I know how to write simple If-Condition, like

/* if (x == true) then y = true */
y >= x;

but I don't know how to write a set of constraints in order to express a "complex" if.

Does someone of you know how to resolve this in LPSolve?

Christian · Accepted Answer · 2014-07-19 19:45:40Z

3

To answer the first part:

The AND can be modeled as

A >= A1 + A2 -1
A <= A1
A <= A2

The OR can be modeled as

B >= B1
B >= B2
B <= B1 + B2

To model the if-else constraint you can use the "big M" technique .

Let M be a sufficiently large number.

You can "disable" an inequality by adding M to one side of it. Then the inequality holds regardless of the variable values.

For instance

if (A == 1)
   C_OR_D >= C;
else
   E_OR_F >= E;

can be modeled as

(1-A) * M + C_OR_D >= C
A * M + E_OR_F >= E

answered Jul 19, 2014 at 19:45

Christian

1,4903 gold badges16 silver badges27 bronze badges

Sign up to request clarification or add additional context in comments.

Comments

TenzingMike · Accepted Answer · 2017-05-04 20:40:43Z

1

A special case is the equivalent to "if X=N then SAME=true". A solution to this for integer values in X is:

SAME + BIGGER + SMALLER = 1
X - M1 * BIGGER + SMALLER <= N
X + M2 * SMALLER - BIGGER >= N

for binary variables SAME, BIGGER, SMALLER and sufficiently big numbers M1, M2 (depending of the possible range for X).

If X=N, BIGGER and SMALLER have to be 0, else one of the latter two equations is violated. In consequence, SAME has to be 1 (equation 1).

If X > N then BIGGER = 1 disables equation 2, and since X >= N+1 equation 3 still holds. SAME = SMALLER = 0 (equation 1).

If X < N then SMALLER = 1 disables equation 3, since X <= N-1 equation 2 still holds. SAME = BIGGER = 0 (equation 1).

answered May 4, 2017 at 20:40

TenzingMike

111 bronze badge

Collectives™ on Stack Overflow

If-Then-Else with multiple assignment in Integer Linear Programming (ILP)

2 Answers 2

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related