Drexel dragonThe Math ForumDonate to the Math Forum



Search All of the Math Forum:

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


Math Forum » Discussions » sci.math.* » sci.math.independent

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

Advanced Search

Back to Topic List Back to Topic List Jump to Tree View Jump to Tree View   Messages: [ Previous | Next ]
RGVickson@shaw.ca

Posts: 1,649
Registered: 12/1/07
Re: disjunctive constraints in integer linear programming
Posted: Apr 13, 2013 11:02 AM
  Click to see the message monospaced in plain text Plain Text   Click to reply to this topic Reply

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.




Point your RSS reader here for a feed of the latest messages in this topic.

[Privacy Policy] [Terms of Use]

© Drexel University 1994-2014. All Rights Reserved.
The Math Forum is a research and educational enterprise of the Drexel University School of Education.