quasi
Posts:
10,305
Registered:
7/15/05


Re: disjunctive constraints in integer linear programming
Posted:
Apr 14, 2013 2:43 AM


Ray Vickson wrote: > >There is a general method for modelling alternative constraint >groups of the form either >{f1(x) <= 0 and f2(x) <= 0 and ... and fr(x) <=0} >or >{g1(x) <= 0 and g2(x) <= 0 and ... and gs(x) <=0}. > >Let F1,F2,...,Fr > 0 be known upper bounds on f1(x),..., fr(x) >and let G1,...,Gs be defined similarly for the gi(x). Usually >there is enough auxiliary information about the problem to >allow reasonable values of Fi and Gj to be determined. (Often >books will say to just let these be some very large numbers, >but that is not a good idea; if F = 100 works, you can probably >also use F = 200 without serious difficulties, but using >F = 10^10 would NOT be good, just because of roundoff errors, >etc., introduced in the solving procedure.) > >Anyway, let y1 and y2 be binary variables and write >f1(x) <= F1*y1, f2(x) <= F2*y1, ..., fr(x) <= Fr*y1, >g1(x) <= G1*y2, g2(x) <= G2(y2, ..., gs(x) <= Gs*y2, >and y1 + y2 = 1. > >Of course, in this case we can write y2 = 1y1, and it really >is the case that solving the problem twice (once with y1 = 0 >and once with y1 = 1) is the easiest way to go. However, the >method given here generalizes to more than two alternatives: >just have a binary variable y for each separate group of >constraints, then impose the constraint sum(y) = 1.
In your followup reply, you corrected sum(y) = 1 to sum(y) = n1, but that would be for n groups connected with _exclusive_ or. For ordinary or, the appropriate constraint is sum(y) <= n1. Of course if the constraint regions are pairwise disjoint (as is the case for the OP's posted example), then sum(y) = n1 is fine.
>So, you could have a similar formulation if you had 10 >alternatives, which done by brute force would need 1024 >separate solving runs.
Assuming the constraint regions are pairwise disjoint, I don't see 1024 runs, I see only 10, one for each alternative group of constraints. Even if the constraint regions are not disjoint, I still see only 10, provided "or" is "inclusive or". Simply optimize each group separately and take the best of the optimum values.
quasi

