This page contains various transformations I have found useful for producing MIP formulations. Many of these can be found spread on other websites as well. I will try to be consistent about notation: a, b, c, … will to refer to binary variables while x, y, z, … will refer to integer variables unless otherwise specified. Syntax follows the CPLEX LP file format.

Contents

1. Boolean Operations
2. At Most One is True
3. Product of Binary and (Bounded) Integer Variables
4. (Bounded) Integer Comparison Result
5. (Bounded) Integer Comparison Bound
6. Rounded Up Division by Constant
7. Rounded Down Division by Constant

Transformations

Boolean Operations

To make c = a AND b

a + b - 2c <= 1
a + b - 2c >= 0

Proof:

a	b	c	Reason
0	0	0	(1 would violate second constraint)
0	1	0	(1 would violate second constraint)
1	0	0	(1 would violate second constraint)
1	1	1	(0 would violate first constraint)

To make c = a OR b

2c - a - b <= 1
2c - a - b >= 0

Proof:

a	b	c	Reason
0	0	0	(1 would violate first constraint)
0	1	1	(0 would violate second constraint)
1	0	1	(0 would violate second constraint)
1	1	1	(0 would violate second constraint)

Source: https://cs.stackexchange.com/a/43884

At Most One is True

To make at most one of a1, a2, …, aN be true:

    a1 + a2 + ... + aN <= 1

Proof: Assume any ai, aj true where i != j, then the sum is 2. Hence, at most one can be true. If on the other hand, at most one ai is true, the inequality is also true.

Product of Binary and (Bounded) Integer Variables

We will assume that 0 <= x <= K (any upper bound will do). To make y = a * x

y - Ka <= 0
y - x <= 0
y - x - Ka >= -K
y >= 0

A generalized version that uses a non-zero lower bound can be found at the source.

Source: https://www.leandro-coelho.com/linearization-product-variables/

(Bounded) Integer Comparison Result

We will assume that 0 <= x <= K and that 0 <= y <= K (any upper bound will do). To make a = 1 iff (x >= y)

y - x + Ka <= K
y - x + Ka >= 1

Proof:

• Case x >= y then y - x <= 0
  • if a = 0 then
    • y - x <= K (true)
    • y - x >= 1 (false, violation)
  • if a = 1 then
    • y - x + K <= K (true)
    • y - x + K >= 1 (true since 0 <= x,y <= K)
• Case x < y, then y - x >= 1
  • if a = 0 then
    • y - x <= K (true since 0 <= x,y <= K)
    • y - x >= 1 (true)
  • if a = 1 then
    • y - x + K <= K (false, violation)
    • y - x + K >= 1 (true)

Based on https://blog.adamfurmanek.pl/2015/09/12/ilp-part-4/

(Bounded) Integer Comparison Bound

We will assume that 0 <= x <= K and that 0 <= y <= K (any upper bound will do). To make a ≤ 1 if (x >= y) and a = 0 otherwise

y - x + Ka <= K

Proof:

• Case x >= y then y - x <= 0
  • if a = 0 then
    • y - x <= K (true)
  • if a = 1 then
    • y - x + K <= K (true)
• Case x < y then y - x >= 1
  • if a = 0 then
    • y - x <= K (true)
  • if a = 1 then
    • y - x + K <= K (false, violation)

Rounded Up Division by Constant

We will assume that x and z are integers and that K >= 2. To make z = ceil(x/K)

x - Kz <= 0
Kz - x <= K - 1/K

Proof:

Combining the two constraints yields

  x <= Kz <= x + (K - 1/K)
x/K <=  z <= x/K + (1 - 1/K^2)

The lower bound is obviously correct since z >= ceil(x/K) by definition requires that z >= x/K.

The open question is whether the right hand side is correct. For this to work, we need that our upper bound is >= ceil(x/K) and < ceil(x+K) + 1 (strict inequality).

For the upper bound of the upper bound, we have that

ceil(x/K) + 1 > ceil(x/K) + (1 - 1/K^2)
              > x/K + (1 - 1/K^2)

To compute the lower bound of the upper bound, we first define x = Km + r where 0 <= r < K. Then we have

x/K + (1 - 1/K^2) = (m + r/K) + (1 - 1/K^2)
                  = (m + 1) + r/K - 1/K^2

Case 1: r = 0

Then ceil(x/K) = m and

x/K + (1 - 1/K^2) = m + 1 + 0/K - 1/K^2
                  = ceil(x/K) + 1 - 1/K^2
                  >= ceil(x/K)

Case 2: r >= 1

Then ceil(x/K) = m + 1 and

x/K + (1 - 1/K^2) = (m + 1) + r/K - 1/K^2
                  = ceil(x/K) + r/K - 1/K^2
                  >= ceil(x/K) + 1/K - 1/K^2
                  >= ceil(x/K)

Rounded Down Division by Constant

We will assume that x and z are integers and that K >= 2. To make z = floor(x/K)

Kz - x <= 0
x - Kz <= K - 1/K

Proof:

Combining the two constraints yields

    x - K + 1/K <= Kz <= x
x/K - 1 + 1/K^2 <=  z <= x/K

The upper bound is obviously correct since z <= floor(x/K) by definition requires that z <= x/K.

The open question is whether the left hand size is correct. For this to work, we need that our lower bound is <= floor(x/K) and > floor(x/K) - 1 (strict inequality).

For the lower bound of the lower bound, we have that

floor(x/K) - 1 < floor(x/K) - (1 - 1/K^2)
               < x/K - 1 + 1/K^2

To compute the upper bound of the lower bound, we first define x = Km + r where 0 <= r < K. Then we have that floor(x/K) = m and

x/K - 1 + 1/K^2 = (m + r/K) - 1 + 1/K^2
                = m - 1 + r/K + 1/K^2
                = floor(x/K) - 1 + r/K + 1/K^2
                <= floor(x/K) - 1 + (K-1)/K + 1/K^2
                <= floor(x/K) - 1 + 1 - 1/K + 1/K^2
                <= floor(x/K) - (1/K - 1/K^2)
                <= floor(x/K)