How to specify an unequal constraint with an Integer Linear Programming (ILP) solver

Problem :

    For example:  A != B    (Note that A and B are both integers.)

Answer :

A != B
==> 
          A < B or A > B

==> 
          A < B or B < A

==>
          A < B + M1*BV              .......... (1)
          B < A + M2*(1-BV)        .......... (2)

          Note that BV is a binary variable, that is, BV = {0, 1}. In addition, M1 and M2 are constants whose values should be large enough.
          If BV=0, then A < B and constraint (2) is redundant.
          If BV=1, then B < A and constraint (1) is redundant.

==>
          A - B < M1*BV              .......... (3)
          B - A < M2*(1-BV)        .......... (4)

==>
          A - B <= M1*BV - 1              .......... (5)
          B - A <= M2*(1-BV) - 1        .......... (6)

          Note that "<=" denotes "less than or equal". 

last update: May 29, 2009