Date: Apr 13, 2013 11:02 AM
Author: RGVickson@shaw.ca
Subject: Re: disjunctive constraints in integer linear programming
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.