Week 6 Flashcards
1
Q
What is the idea of Langrangean relaxation?
A
Dualize it and include it in the objective
2
Q
How to find the Lagrangean relaxation?
A
L(lambda) = max cTx + lambdaT(b - Ax)
s.t. D x ≤ d
x ≥ 0
x is integer
3
Q
What is a fact about the Lagrangean dual regarding the optimal value?
A
For LP the Lagrangean Dual has the same optimal value as the Primal solution.
