Gomory Cut Example [1/19]

Consider the following problem:

max y = 3x1 + 4x2

subject to
2
x1 + x2 ≤ 3
5
2 2
x1 − x2 ≤ 1
5 5
x1 , x2 ≥ 0
x1 , x2 ∈ N0 .

17/40
Gomory Cut Example [2/19]

Step 1. Convert maximisation objective into minimisation.

min z = −3x1 − 4x2

subject to
2
x1 + x2 ≤ 3
5
2 2
x1 − x2 ≤ 1
5 5
x1 , x2 ≥ 0
x1 , x2 ∈ N0 .

18/40
Gomory Cut Example [3/19]

Step 1. Scale the equations of the problem.

min z = −3x1 − 4x2

subject to
2
x1 + x2 ≤ 3 (∗5)
5
2 2
x1 − x2 ≤ 1 (∗5)
5 5
x1 , x2 ≥ 0
x 1 , x 2 ∈ N0 .

19/40
Gomory Cut Example [4/19]

Step 1. Scale the equations of the problem.

min z = −3x1 − 4x2

subject to

2x1 + 5x2 ≤ 15
2x1 − 2x2 ≤ 5
x1 , x2 ≥ 0
x1 , x2 ∈ N0 .

20/40
Gomory Cut Example [5/19]

Step 1. Insert integer slack variables.

min z = −3x1 − 4x2

subject to

2x1 + 5x2 + x3 = 15
2x1 − 2x2 + x4 = 5
x1 , x2 , x3 , x4 ≥ 0
x1 , x2 , x3 , x4 ∈ N0 .

21/40
Gomory Cut Example [6/19]

Step 1. Solve LP relaxation of problem.

BV x1 x2 x3 x4 RHS
z 3 4 0
x3 2 5 1 15
x4 2 −2 1 5

22/40
Gomory Cut Example [7/19]

Step 1. Solve LP relaxation of problem.

BV x1 x2 x3 x4 RHS
z 3 4 0
x3 2 5 1 15
x4 2 −2 1 5
The optimal solution has the tableau:
BV x1 x2 x3 x4 RHS
z −1 − 21 - 35
2
1
x2 1 7 − 71 10
7
1 5 55
x1 1 7 14 14

Step 2. Solution is not integer, go to Step 3.

23/40
Gomory Cut Example [8/19]

Step 3. Generate cut based, e.g., on x1 row.

1 5 55
x1 + x3 + x4 =
7 14 14

I f1 = 1 − b1c = 0 (basic, does not appear in GC)

I f3 = 17 (non-basic)
5
I f4 = 14 (non-basic)
55
I f = 14 − b 55
14 c =
13
14
Gomory Cut (GC1):

1 5 13
x3 + x4 ≥ .
7 14 14

24/40
Gomory Cut Example [9/19]

Step 4. Add cut to the LP relaxation and go back to Step 1.

Standardise (GC1) introducing excess x5 ≥ 0:

1 5 13
x3 + x4 − x5 = .
7 14 14
LP relaxation solution is x3∗ = x4∗ = 0 ⇒ (GC1) is infeasible!

We need to solve a problem similar to Simplex Phase 1 to find an

initial BFS for Step 1, thus we add the artificial variable ξ1 :
1 5 13
x3 + x4 − x5 + ξ1 = .
7 14 14
Sanity Check. The LP relaxation solution is now infeasible. Is this
typical?

25/40
Gomory Cut Example [10/19]

Step 1.
13 1 5
ζ = ξ1 = − x3 − x4 + x5
14 7 14
BV x1 x2 x3 x4 x5 ξ1 RHS
1 5 13
ζ 7 14 −1 14
1
x2 1 7 − 71 10
7
1 5 55
x1 1 7 14 14
1 5 13
ξ1 7 14 −1 1 14

Pivot on (x4 , ξ1 ) based on reduced costs of ζ.

26/40
Gomory Cut Example [11/19]

BV x1 x2 x3 x4 x5 ξ1 RHS
ζ −1 0
1
x2 1 5 − 25 9
5
x1 1 1 3
2
x4 5 1 − 14
5
13
5

Objective ζ = 0 and we can remove both ζ and ξ1 .

27/40
Gomory Cut Example [12/19]

Step 1. After adding back z to the basic representation, solve LP

relaxation of problem (Simplex Phase 2).

BV x1 x2 x3 x4 x5 RHS
z − 54 − 75 − 81
5
1
x2 1 5 − 25 9
5
x1 1 1 3
2
x4 5 1 − 14
5
13
5

Solution optimal; Simplex stops.

Step 2. Solution is not integer, go to Step 3.

28/40
Gomory Cut Example [13/19]

Step 3. Generate cut based, e.g., on x2 row.

1 2 9
x2 + x3 − x5 =
5 5 5

I f2 = 0 (basic, does not appear in GC)

I f3 = 15 (non-basic)
I f5 = − 52 − b− 25 c = − 25 + 1 = 35 (non-basic)
I f = 95 − b 95 c = 59 − 1 = 45
Gomory Cut (GC2):
1 3 4
x3 + x5 ≥ .
5 5 5

29/40
Gomory Cut Example [14/19]

Step 4. Add cut to the LP relaxation and go back to Step 1.

Standardise (GC2) introducing excess x6 ≥ 0:

1 3 4
x3 + x5 − x6 = .
5 5 5
Current LP solution is x3∗ = 0, x5∗ = 0 ⇒ (GC2) is infeasible!

We need to solve a problem similar to Simplex Phase 1 to find an

initial BFS for Step 1, thus we add the artificial variable ξ1 :
1 3 4
x3 + x5 − x6 + ξ1 = .
5 5 5

30/40
Gomory Cut Example [15/19]

4
Step 1. ζ = ξ1 = 5 − 15 x3 − 35 x5 + x6

BV x1 x2 x3 x4 x5 x6 ξ1 RHS
1 3 4
ζ 5 5 −1 5
1
x2 1 5 − 52 9
5
x1 1 1 3
2
x4 5 1 − 14
5
13
5
1 3 4
ξ1 5 5 −1 1 5

Pivot on (x5 , ξ1 ) based on reduced costs of ζ. ζ will go to 0.

31/40
Gomory Cut Example [16/19]

Step 1. Solve LP relaxation of problem (Simplex Phase 2).

BV x1 x2 x3 x4 x5 x6 RHS
z − 31 − 73 − 43
3
1
x2 1 3 − 23 7
3
x1 1 − 31 5
3
5
3
4
x4 3 1 − 14
3
19
3
1
x5 3 1 − 53 4
3

Solution optimal; Simplex stops.

Step 2. Solution is not integer, go to Step 3.

32/40
Gomory Cut Example [17/19]

Step 3. Generate cut based on x2 row.

Applying the same procedure as before, we get (GC3):

1 1 1
x3 + x6 − x7 =
3 3 3
We add it to the tableau for Phase 1 as
1 1 1
x3 + x6 − x7 + ξ1 =
3 3 3

33/40
Gomory Cut Example [18/19]

1
Step 1. ζ = ξ1 = 3 − 13 x3 − 13 x6 + x7

BV x1 x2 x3 x4 x5 x6 x7 ξ1 RHS
1 1 1
ζ 3 3 −1 3
1
x2 1 3 − 32 7
3
x1 1 − 13 5
3
5
3
4
x4 3 1 − 14
3
19
3
1
x5 3 1 − 35 4
3
1 1 1
ξ1 3 3 −1 1 3

Pivot on (x3 , ξ1 ) based on reduced costs of ζ. ζ will go to 0.

34/40