Column Generation Reduced Cost

Problem

Compute the reduced cost of a new column in column generation.

Return c_j - dot(y, a_j), where c_j is the column cost, y the current dual prices, and a_j the column coefficients. A negative reduced cost means the column can improve the master.

Hint

Price out the column against the current dual solution.

Test cases

case 1

in: [5,[1,2],[1,1]]

expected: 2

case 2

in: [3,[0.5,0.5],[2,4]]

expected: 0

case 3

in: [-1,[1],[0]]

expected: -1

Starter codePython

def reduced_cost(c_j, y, a_j):
    # Your code here
    pass

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