Lagrangian Relaxation Bound

Problem

Evaluate the Lagrangian relaxation bound for a set of candidate solutions.

For candidate i with objective f_values[i] and constraint values g_values[i], compute f_i + dot(lam, g_i) and return the minimum over all candidates. This is the Lagrangian dual value for the fixed multipliers.

Hint

Relaxing constraints turns the problem into an unconstrained minimum over candidates.

Test cases

case 1

in: [[1,2],[[1],[0]],[0.5]]

expected: 1.5

case 2

in: [[3,1,2],[[2,1],[0,2],[1,-1]],[0.5,0.5]]

expected: 2

case 3

in: [[1],[[-1]],[2]]

expected: -1

Starter codePython

def lagrangian_relaxation_bound(f_values, g_values, lam):
    # Your code here
    pass

3 test cases · run your code against them in the editor