Benders Cut Lite

Problem

Evaluate an optimality cut generated by Benders decomposition.

Given the subproblem value at the trial solution y_hat and its dual multipliers, the cut at a candidate y is sub_value + dot(duals, y - y_hat). Return that value, which lower-bounds the recourse cost in the master problem.

Hint

The cut is the first-order Taylor expansion of the recourse function at y_hat.

Test cases

case 1

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

expected: 12.5

case 2

in: [5,[1],[0],[3]]

expected: 8

case 3

in: [2,[],[],[]]

expected: 2

Starter codePython

def benders_cut(sub_value, duals, y_hat, y):
    # Your code here
    pass

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