Assignment Dual Check

Problem

Check feasibility of a dual solution for the assignment problem.

The dual maximizes sum(pi) + sum(v) subject to pi[i] + v[j] <= costs[i][j] for all pairs. Return [feasible, objective], where objective is 0.0 when the dual is infeasible.

Hint

Every dual constraint is pi_i + v_j <= c_ij.

Test cases

case 1

in: [[[4,1],[2,3]],[2,1],[2,0],1e-9]

expected: [false,0]

case 2

in: [[[4,1],[2,3]],[0,0],[2,1],1e-9]

expected: [true,3]

case 3

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

expected: [true,1]

Starter codePython

def assignment_dual_check(costs, pi, v, tol):
    # Returns [feasible, objective]
    # Your code here
    pass

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