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 ]
 RGVickson@shaw.ca Posts: 1,677 Registered: 12/1/07
Re: disjunctive constraints in integer linear programming
Posted: Apr 13, 2013 11:15 AM

On Saturday, April 13, 2013 8:02:05 AM UTC-7, Ray Vickson wrote:
> On Thursday, April 11, 2013 12:24:57 PM UTC-7, d.inf...@gmail.com wrote:
>

> > I have an integer linear programming problem as follows:
>
> >
>
> >
>
> >
>
> > The constraints are either
>
> >
>
> >
>
> >
>
> >
>
> >
>
> > x >= 0
>
> >
>
> > y = u
>
> >
>
> > z = x + v
>
> >
>
> >
>
> >
>
> >
>
> >
>
> > or
>
> >
>
> >
>
> >
>
> > x < 0
>
> >
>
> > y = u - x
>
> >
>
> > z = v
>
> >
>
> >
>
> >
>
> >
>
> >
>
> > where y, z, u, v range over non-negative integers. There are other unrelated constraints associated with u, v, y, z.
>
> >
>
> >
>
> >
>
> >
>
> >
>
> > What's the most simple way to encode the disjunctive case? Does any linear encoding where all co-efficients are -1, 0, 1 exist?
>
> >
>
> >
>
> >
>
> > Thank you!
>
>
>
> 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,...,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. So, you could have a similar formulation if you had 10 alternatives, which done by brute force would need 1024 separate solving runs.
>
>
>
> For your problem, you can write:
>
> either
>
> {-x <= 0, y-u <= 0, u-y <= 0, z-x-v <= 0, x+v-z <= 0}
>
> or
>
> {x+1 <= 0, y+x-u <= 0, u-y-x <= 0, z-v <= 0, v-z <= 0}
>
> and proceed accordingly.

Sorry: for n groups of alternative constraints, the binary variables y1, y2, ..., yn should be constrained by sum(yi) = n-1 (NOT sum(y) = 1). The constraint sum(y) = n-1 implies that (n-1) of the yi are 1, and so those constraints are inactive; one yi is 0, so that group of constraints is actually imposed.

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