Linear programs and duals

References

• Wikipedia;

• Edmonds1995;

• Lecture notes for linear programming;

---

“the constraints specify a convex polytope”

---

variables
(A : ℕ → ℕ → ℝ) -- Row (node) i: (A i j) = 1 then edge j is incident on node i.
(b : ℕ → ℝ)
(c : ℕ → ℝ)  -- (c i) is the weight of edge i

variables
(x        : ℕ → ℝ)  -- (x i) = 1 means edge i is matched.
(x_nonneg : ∀ i, x i ≥ 0)
(cond_1   : ∀ i, ∑ j, (a i j) * (x j) ≤ (b i) )

variables
(y        : ℕ → ℝ)
(y_nonneg : ∀ i, y i ≥ 0)
(cond_2   : ∀ j, ∑ i, (a i j) * (y i) ≥ (c j) )

theorem LP_duality :
max ∑ i, (c i) * (x i) = min ∑ i, (b i) * (y i) := sorry

"The dual problem provides an upper bound
on the optimal value of the primal problem."

“a slack variable in an optimization problem is a variable added to an inequality to transform it to an equality”

the slack correspond to cond_2:

for a given edge j

(e j).v1.y + (e j).v2.y = (e j).w + slack(e j)

slack(e j) = (e j).v1.y + (e j).v2.y - (e j).w

---

Example application in Weighted perfect matching:

-- ∀ n ∈ V, ∑ e incident on n, e.matched ≤ 1
∀ i, ∑ j, (a i j) * (x j) ≤ 1

Then the dual program is:

min ∑ i, (y i)

The y’s can be called weights or bones or clams or whatever you want to call them.