Discrete Optimization 1, 5 ECTS Exam 2025-02-24

• Subject: Discrete Optimization 5 ECTS, WS 24/25
• Date: 2025-02-24
• Type of Exam: written exam
• Examiner: Kevin-Martin Aigner
• Time: 60 minutes
• Doing the exercises is highly recommended. Some of them are more difficult than exam questions but the exercises where you have to calculate something (like the dimension) are similar in difficulty.
• you only have 60 minutes so you need to be very fast and can't think about questions very long
• it was similar to the holiday sheet, which is basically the practice exam
• it is structured into 4 parts which each gives 10 points: Multiple Choice, Calculate 1, Calculate 2, Proof
• the calculate excercises are for example branch and bound / dimension of polyhedra
• I am pretty sure you need less than 50% to pass

I tried my best to remember everything but this braindump is still incomplete and likely partially faulty.

Which of the following statements are correct?

1.

☐ not sure, something about Branch and Bound runs in polynomial time

☐ Some IPs with unbounded integer variable do not in run in polynomial time for Branch and Bound

☐ P = NP means Branch and Bound runs in polynomial times

2.

☐ not sure

☐ Either a polytope or its inclusion wise minimal face have dim(X) >= 1

☐ not sure

3. For a projection Q of Polyhedron P on full dimensional Polyhedron S

☐ Q is orthogonal

☐ if Q is full dimensional then P is full dimensional

☐ if P is full dimensional then Q is full dimensional

☐ if P ∩ Q != {} then Q is full dimensional

4. For P = conv(x in R^4 | 2⋅x1 + 2⋅x2 + 5⋅x3 + 8⋅x4 ≤ 8 }

☐ 2⋅x1 + 4⋅x2 ≤ 3 defines a facet

☐ 3 other such conditions that maybe define facets (not sure about the numbers for any on this question, but I think the only facet would be the condition in the question definition)

5. For 2⋅x1 + x2 ≤ 1, x1+2⋅x2 ≤ 1, max x1 + x2 and x1,x2 in Z, which of these are valid cutting planes that cut off (0.5, 0.5)

☐ something with 2/3

☐ x1+x2 ≤ 1

☐ x1 >= 1

☐ none of the above

a) Determine graphically a solution to the relaxed problem of this Integer Program: 2⋅x1 + 2⋅x2 ≤ 3 -2⋅x1 + 2⋅x2 ≤ -3 max x1 + 2⋅x2

b) Draw branch and bound tree with nodes

n1: zIP = …, dNode = …, x=(0, 1.5) … description of nodes 2-8

c) Why can we stop after these nodes were processed?

We have polyhedron

(1) 2⋅x1 - x2 - x3 ≤ 0

(2) -x1 + 2⋅x1 - x3 ≤ 0

(3) -x1 - x2 + 2⋅x3 ≤ 0

(4) x1 + x2 + x3 ≤ 3

a) Determine rkAeq(P), use eq(P) = {1,2,3}

b) Give an interior point and reason why P does not have any topologically interior points

c) Give an inner description of P

d) Reason why 2⋅x1 + 2⋅x2 ≤ 4 is valid for P

e) Reason why 2⋅x1 + 2⋅x2 ≤ 4 induces the same facet as (4)

A single theorem you are asked to show for the 10 points. I messed up during the drawing part of Branch and Bound and thus did not have enough time to even try the proof.