Optimisation Techniques

QUESTION 1

Consider the integer linear programming problem,

max 𝑥 + 2𝑦
s.t. 𝑥 + 𝑦 ≤ 10
2𝑥 + 5𝑦 ≤ 25 + 𝑧
𝑥, 𝑦 ≥ 0 𝑎𝑛𝑑 𝑖𝑛𝑡𝑒𝑔𝑒𝑟

Here z = 0 if the last digit of your registration number is odd; otherwise, z = 5

(a) Relax the integrality constraint. Assume that it is known that in the optimal solution of the
obtained LP problem both main constraints hold as equalities. Derive the final simplex tableau using
the transformation matrix technique. Is the obtained optimal solution feasible for the original
integer programming problem?

Since my last digit of the registration number is odd, then z=0.

So,
max 𝑥 + 2𝑦
s.t. 𝑥 + 𝑦 ≤ 10
2𝑥 + 5𝑦 ≤ 25
𝑥, 𝑦 ≥ 0 𝑎𝑛𝑑 𝑖𝑛𝑡𝑒𝑔𝑒𝑟

LP Relaxation
max 𝑥 + 2𝑦
s.t. 𝑥 + 𝑦 ≤ 10
2𝑥 + 5𝑦 ≤ 25
𝑥 ≤1
𝑦 ≤1
𝑥, 𝑦 ≥ 0

Thus,


1 1
[ ]
2 5
Finding the inverse,

1 1 1
A= [ ] = 𝑎𝑑𝑗(𝐴)
2 5 det(𝐴)

1 5 −1
= [ ]
(5×1)−(2×1) −2 1

, 1 5 −1
= [ ]
(5)−(2) −2 1
1 5 −1
= [ ]
3 −2 1

Therefore, the inverse matrix is the following,

5 −1
[3 3]
−2 1
3 3
Order of rows: 𝒙, 𝒚

Af = Tf x A0 =

5 −1 5 −1
[3 3 ] [1 1 1 0
] = [
1 0 3 3]
−2 1 2 5 0 1 0 1 −2 1
3 3 3 3

RHSf = Tf x RHS0 =
25
5 −1
3
10
[3 3 ][ ] =
−2 1 25
5
3 3 [3]

,𝑧 − 𝑟𝑜𝑤:

5 −1
1 0 3 3 1 1
[1 2] [ −2 1 ] = [1 2 ]
0 1 3 3
3 3


𝑍 − 𝑟𝑜𝑤 𝑓𝑖𝑛𝑎𝑙 𝑣𝑎𝑙𝑢𝑒:

𝟐𝟓
𝟑 𝟑𝟓
[𝟏 𝟐] =
𝟓 𝟑
[𝟑]
𝒄 − 𝒛:

1 1 1 1
[1 2 0 0] − [1 2 ] = [0 0 − − ]
3 3 3 3
The obtained optimal solution is NOT feasible for the original integer programming problem.
Since this is the integer linear programming problem, the RHS shows a fraction for the final
25 5
tableau, 𝑥 = 3 𝑎𝑛𝑑 𝑦 = 3 and not an integer, therefore it is not feasible for this ILP.




Hence the final simplex tableau using the transformation matrix technique is given by,



Basis x y s1 s2 RHS
CB 1 2 0 0
x 1 1 0 5/3 - 1/3 25/3
y 2 0 1 - 2/3 1/3 5/3
zj 1 2 1/3 1/3 35/3
cj-zj 0 0 - 1/3 - 1/3

, (b) Starting with the tableau found in (a), apply the Gomory fractional algorithm to obtain
two different optimal integer solution. Clearly explain how the cut equations are derived.

The “Gomory Cut” is a computationally efficient method for deriving an optimal solution to an ILP
by adding (a) constraint(s) to enforce integrality. It ONLY works with ILPs – i.e. all coefficients, RHS
elements and decision variables must be integers.

Let the integer part the “floor” function of the number, formally defined as the largest whole
number no larger than the variable and denote it like this:

𝑓𝑙𝑜𝑜𝑟 (𝑥) = |𝑥|

The fractional part of the variable = 𝑥 − |𝑥| , 𝑑𝑒𝑛𝑜𝑡𝑒𝑑 {𝑥}, {𝑥} ≥ 0


The final simplex tableau from part (a) is the following,


Basis x y s1 s2 RHS
CB 1 2 0 0
x 1 1 0 5/3 - 1/3 25/3
y 2 0 1 - 2/3 1/3 5/3
zj 1 2 1/3 1/3 35/3
cj-zj 0 0 - 1/3 - 1/3

Cut 𝑥 since it has a larger fraction part.


G-row derived from the 𝑥 row;

𝟓 𝟏
𝟏 𝟎 −
𝟑 𝟑

𝟓 𝟏 𝟐𝟓
𝒙 + 𝒔𝟏 − 𝒔𝟐 =
𝟑 𝟑 𝟑

Find the fractional parts,
So Constraint becomes:


𝟐 𝟐 𝟏
𝒙 + (1 + )𝒔𝟏 + (−𝟏 + ) 𝒔𝟐 = 𝟖 +
𝟑 𝟑 𝟑