(LP-1): the matching LP is integral, has an optimal dual, and weak duality holds
ProvedTwoStageMatch.lp1_dualitycompetitive-ratioonline-matchingp2o-gran-per-chapterp2o-plan-paperp2o-strengthenedp2o-v1ride-hailingtwo-stage-stochastic-matching
Let , be finite, , , and , . For the maximum supply-weighted fractional matching LP on and its dual (LP-1):
- the LP optimum equals : some fractional matching attains it and every fractional matching has ;
- there is a dual-feasible (that is, and on every edge of ) with
- (weak duality) every dual-feasible has .
The proof of Theorem 1 uses (1) for ("the optimal objective value of the above LP is what obtains for this particular realization"), (2) for the residual graph , and (3) to conclude.
Differences from the source:
- generalization: LP-1 on G[D₁ ∪ D̃₂, S] and the residual LP on G[D̃₂, S \ S₁] → any finite bipartite graph and any X ⊆ U, Y ⊆ S; reason: both uses are instances (X = D₁ ∪ A, Y = S, and X = A, Y = S \ S₁)
- encoding: LP variables x_ij for i ∈ X, j ∈ N(i) → x : U → S → ℝ vanishing off the edges of G[X, Y]; reason: Lean convention; same LP
Preamble
import Mathlib import Definitions.Def_TwoStageMatch_Bipartite
Formal statement
namespace TwoStageMatch
/-- **(LP-1) duality and integrality** (Feng, Niazadeh & Saberi, arXiv:2210.11648v1, proof of
Theorem 1, p.14: "the optimal objective value of the above LP is what OPT_offline obtains for
this particular realization of D̃₂"; "Let {α̂_i}, {β̂_j} be the optimal dual solution of this LP
… as M₂ is an optimal solution for the primal LP, Σ_j w_j 𝟙{j is matched by M₂} = Σ α̂_i + Σ β̂_j").
For a bipartite graph with nonnegative supply weights and any `X ⊆ U`, `Y ⊆ S`, for the maximum
supply-weighted fractional matching LP on `G[X, Y]` and its dual:
1. the LP optimum equals `Max-WeightMatch^w(X, Y)` and is attained;
2. there is a dual-feasible `(α̂, β̂)` (`α̂, β̂ ≥ 0`, `α̂_i + β̂_j ≥ w_j` on the edges of `G[X, Y]`)
with `Σ_{i ∈ X} α̂_i + Σ_{j ∈ Y} β̂_j = Max-WeightMatch^w(X, Y)`;
3. (weak duality) every dual-feasible `(α, β)` has `Σ_{i ∈ X} α_i + Σ_{j ∈ Y} β_j ≥
Max-WeightMatch^w(X, Y)`. -/
theorem lp1_duality {U S : Type*} [Fintype U] [Fintype S] [DecidableEq S]
(E : U → S → Prop) (w : S → ℝ) (hw : ∀ j, 0 ≤ w j) (X : Finset U) (Y : Finset S) :
((∃ x : U → S → ℝ, IsFracMatching E X Y x ∧ fracWeight w x = maxWeightMatch E w X Y) ∧
∀ x : U → S → ℝ, IsFracMatching E X Y x → fracWeight w x ≤ maxWeightMatch E w X Y) ∧
(∃ (α : U → ℝ) (β : S → ℝ), IsDualFeasible E w X Y α β ∧
dualObj X Y α β = maxWeightMatch E w X Y) ∧
(∀ (α : U → ℝ) (β : S → ℝ), IsDualFeasible E w X Y α β →
maxWeightMatch E w X Y ≤ dualObj X Y α β) := by sorry
end TwoStageMatch
Source
Y. Feng, R. Niazadeh, A. Saberi, Two-stage Stochastic Matching and Pricing with Applications to Ride Hailing, arXiv:2210.11648v1 [cs.DS] (preprint, 21 Oct 2022), https://arxiv.org/abs/2210.11648v1, proof of Theorem 1, p.14 (LP-1, the residual LP and its optimal dual)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.