LP Duality Gap

Problem

Compute the LP duality gap between a primal and dual solution.

Return c dot x - b dot y, which is zero at optimality for a correctly paired primal and dual.

Hint

The gap is the difference between primal and dual objective values.

case 1

in: [[1,2],[3,1],[4],[11]]

expected: -39

case 2

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

expected: -2

case 3

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

expected: 0

Starter codePython

def duality_gap(c, x, b, y):
    # Your code here
    pass

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