Or constraint

[samuel casas dray]

Is it possible with the LPSolver IDE to do some "or"  constraint ?
Like for this program (doesn't have a real utility here)

max: x1 + x2;

C1: x1 + x2 <= 10 "or" x1 + x2 <= 15;

int x1 x2;

[Peter Notebaert]

Well your example indeed doesn't make much sense because 

x1 + x2 <= 10 "or" x1 + x2 <= 15;

can just be translated to 

x1 + x2 <= 15;

Suppose your example is:

x1 + x2 <= 10 "or" x1 + x2 >= 15;

Then the way to solve this is split the two conditions in two constraints and make them active with a binary variable.

So introduce binary variable b1 and consider the two cases

b1=0

b1=1

When b1=0 then the first constraint is active and the second one must become redundant. 

When b1=1 then the first constraint must be redundant and the second one must be active.

In many cases you need to introduce a 'big M' (a big constant) value to accomplish this.

One way to formulate this is:

x1 + x2 - bigM b1 <= 10;

x1 + x2 >= 15 b1;

So lets consider the two cases:

b1=0:

x1 + x2 <= 10;

x1 + x2 >= 0;

This makes the first constraint active. The sum of x1 + x2 must be less than or equal to 10.

The second constraint says that x1+x2 must always be larger than or equal to 0 which is always the case if x1 and x2 are not allowed to become 0

b1=1:

x1 + x2 - bigM <= 10;

x1 + x2 >= 15;

When bigM is large enough, the first constraint will be redundant.

The second constraint is now active saying that x1 + x2 must new be larger than or equal to 15

The value of bigM should be large enough such that when b1=1 that x1 + x2 - bigM is always smaller than 10 but then also not too big to not generate numerical instability.

Suppose you know that x1 + x2 can never be larger than for example 100, then bigM can be 100-10

So again, note that bigM is not a variable but a constant that you must determine depending on your model knowledge.

Peter

--
You received this message because you are subscribed to the Google Groups "lp_solve" group.
To unsubscribe from this group and stop receiving emails from it, send an email to lp_solve+u...@googlegroups.com.
To view this discussion on the web visit https://groups.google.com/d/msgid/lp_solve/ec0254a3-1ee5-4db6-9a85-e9dc52ad0e29n%40googlegroups.com.
For more options, visit https://groups.google.com/d/optout.

[samuel casas dray]

So, my next question is, I have a lot of bags and a lot of weight, and I'm trying to resolve the bin covering problem, and so I had something like that

N0 x_0_0 + N1 x_1_0 + ... + N x_n_0 >= P0 y_0

N0 x_0_1 + N1 x_1_1 + ... + N x_n_1 >= P1 y_1
...

N0 x_0_m + N1 x_1_m + ... + N x_n_m >= Pm y_m

*other constraints*

where N0...N is the weight (it's replace by its actual value in the code), P0...P is the capacity of the bag (same as N), x_i_j a bin to know if the weight i is in the bag j and y_i a bin to know if the bag is filled.

But the problem is that with a big number of weight and bag the solver take too much time to solve it. So I was thinking as there can be no more than 5 weights by bag (according to my approximations) I wanted to do something like this

use weight 0, 1, 2, 3, 4 or 0, 1, 2, 3, 5 or ... for the bag 0 and do the same for every bag.

So as you said, should I write something like that if I have "A or B or C" ?

N0 x_0_0 + N1 x_1_0 + N2 x_2_0 + N3 x_3_0 + N4 x_4_0 + P0 b_0_0 + P0 b_1_0 >= P0 y_0

N0 x_0_0 + N1 x_1_0 + N2 x_2_0 + N3 x_3_0 + N5 x_5_0 + P0 b_0_0 >= P0 y_0 * b_1_0
N0 x_0_0 + N1 x_1_0 + N2 x_2_0 + N3 x_3_0 + N5 x_5_0 >= P0 y_0 * b_0_0 + P0 y_0 * b_1_0