Search All of the Math Forum:

Views expressed in these public forums are not endorsed by NCTM or The Math Forum.

Notice: We are no longer accepting new posts, but the forums will continue to be readable.

Topic: disjunctive constraints in integer linear programming
Replies: 9   Last Post: Apr 14, 2013 2:43 AM

 Messages: [ Previous | Next ]
 quasi Posts: 12,067 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 = 1-y1, 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) = n-1, but that would be for n groups connected with
_exclusive_ or. For ordinary or, the appropriate constraint
is sum(y) <= n-1. Of course if the constraint regions are
pairwise disjoint (as is the case for the OP's posted example),
then sum(y) = n-1 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

Date Subject Author
4/11/13 d.info.sign@gmail.com
4/11/13 quasi
4/11/13 d.info.sign@gmail.com
4/12/13 quasi
4/11/13 William Elliot
4/12/13 RGVickson@shaw.ca
4/12/13 quasi
4/13/13 RGVickson@shaw.ca
4/13/13 RGVickson@shaw.ca
4/14/13 quasi