Algorithm: Bisection Method for Shadow Price a
Input:
M: Minimum profit constraint
U: Set of user-coupon pairs (i,j) with (p_ij, c_ij, r_ij)
ε: Convergence threshold (default 1e-5)
Output:
Shadow price a
1: Initialize:
a_low ← 0
a_high ← max(p_ij / c_ij for all (i,j) in U)
2: While (a_high - a_low > ε):
a_mid ← (a_low + a_high) / 2
S ← ∅ // Selected pairs set
total_profit ← 0
// Step 1: Filter valid pairs
For each (i,j) in U:
If p_ij - a_mid * c_ij > 0:
S ← S ∪ {(i,j)}
total_profit ← total_profit + (r_ij - c_ij)
End If
End For
// Step 2: Update search interval
If total_profit ≥ M:
a_low ← a_mid // Tighten constraint
Else:
a_high ← a_mid // Loosen constraint
End If
End While
3: Return a_low