Autumn 2021 Paper (Short Questions)

Question 1

Which of the following statements is true?
(i) A linear programme is always a convex optimisation problem
(ii) A linear programme always has a unique optimal solution
(iii) In the feasible polytope of a linear program, at least one vertex corresponds to an optimal
solution (if an optimal solution exists)

Answer 1

(i) A linear programme is always a convex optimisation problem: TRUE
(ii) A linear programme always has a unique optimal solution: FALSE
(iii) In the feasible polytope of a linear program, at least one vertex corresponds to an optimal
solution (if an optimal solution exists):TRUE

Question 2

How many 2-change neighborhoods of a given travelling salesperson tour are there in a graph with n nodes ?

Answer 2

n(n-3)/2

Question 3

Which of the following are NP-Hard ?
(i) Travelling Salesperson
(ii) Linear Programming
(iii) Integer-Linear Programming

Answer 3

(i) Travelling Salesperson: NOT NP-HARD
(ii) Linear Programming: NOT NP-HARD
(iii) Integer-Linear Programming: NP-HARD

Question 4

Consider an integer-linear program P and its standard LP relaxation P˜. Assume we know
that P˜ has an optimal solution x. Then x is an optimal solution of P if
(i) x is integral
(ii) P is unbounded
(iii) x is infeasible for P

Answer 4

(i) x is integral

If the LP relaxation of P˜ yields a solution x where all variables are integral, the x satisfies all the integer constraints of P as well as the linear constraints.

Question 5

Is the LP given by ….

Maximize x1+x2
subject to x1-x3 ≤ 4
x1+x2 ≥ 2
x1+x3 ≤ -3
x1,x2,x3 ≥ 0

(i) infeasible, or
(ii) unbounded, or
(iii) has an optimal solution?

Answer 5

(i) infeasible

x1+x3 ≤ -3 (contradiction => infeasible)

Question 6

Consider a primal problem P and its dual problem D. If D is unbounded, what can we say about P?

(i) P is infeasible
(ii) P is unbounded
(iii) P has an optimal solution
(iv) P can be either infeasible, unbounded or optimal; unbounded D doesn’t limit P in anyway

Answer 6

(i) P is infeasible

According to duality theory in LP, if dual problem D can be made arbitrarily large (unbounded), then no feasible solution can satisfy the primal constraint.

The rationale is that the unbounded solution un the dual indicates that there is no upper bound to restrict the primals feasible region effectively, usually leading to the primal being infeasible.

Question 7

Consider an integer-linear program P and its standard relaxation P~. Assume we know that P has an optimal solution. Is P~ …

(i) P is infeasible
(ii) P is unbounded
(iii) P has an optimal solution

Answer 7

(iii) P has an optimal solution

If P~ has an optimal solution, P has an optimal solution.

Question 8

Set S is convex if for any two points, x1, x2 ∈ S
(i) Θx1 + Θx2 ∈ S, for all Θ ≥ 0
(ii) Θx1 + Θx2 ∈ S, for all 1 ≥ Θ ≥ 0
(iii) Θx1 + (1 − Θ)x2 ∈ S, for all 1 ≥ Θ ≥ 0
(iv) Θx1 + (1 − Θ)x2 ∈ S, for all Θ ≥ 0

Answer 8

(iv) Θx1 + (1 − Θ)x2 ∈ S, for all Θ ≥ 0

Question 9

Is the LP given by…

Minimise 2x1 + x2 + 2x4
s.t. x1 + 3x3 ≤ 5
x1 + 3x2 ≥ 3
x1−2x4 ≥ 4
x1, x2, x3, x4 ≥ 0

(i) infeasible, or
(ii) unbounded, or
(iii) has an optimal solution?

Answer 9

(iii) has an optimal solution

Has an optimal solution, where
𝑥1, 𝑥2, and 𝑥4 can be adjusted within their constraints to minimize 2𝑥1 + 𝑥2 + 2𝑥4
​
.

Question 10

Convert the following LP into canonical form…

Maximize x2-x1
s.t. x1+2x2 ≤ 1
2x1+x2 ≥ 1
x1, x2 ≥ 0

Answer 10

Canonical Form:

Maximize x2-x1
s.t. x1 + 2x2 + s1 = 1
2x1 + x2 - s2 = 1
x1,x2,s1,s2 ≥ 0