Dantzig-Wolfe Step Lite

Problem

Take one convex-combination update in the Dantzig-Wolfe master.

With current weights x, a new column, and a right-hand side rhs for the single linking constraint, set theta = (rhs - sum(x)) / (sum(column) - sum(x)) clamped to [0, 1]. Return (1 - theta) * x + theta * column; if the denominator is zero return x unchanged.

Hint

The step moves the restricted master toward the new column while restoring the linking constraint.

Test cases

case 1

in: [[0.2,0.2],[0.5,0.5],1]

expected: [0.5,0.5]

case 2

in: [[0.4,0.4],[0.6,0.2],1]

expected: [0.4,0.4]

case 3

in: [[0.1,0.1],[0.4,0.6],0.5]

expected: [0.2125,0.2875]

Starter codePython

def dantzig_wolfe_step(x, column, rhs):
    # Your code here
    pass

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