p. 814, §2.4 — relaxed lifting preserves validity
ProvedCJP83.CoverSeparation.relaxed_lifting_validknapsackliftingp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1
Let be valid for every feasible zero–one solution of the positive-weight row (2.5) supported in , with integer coefficients. For , let be the attained optimum of the LP relaxation of (2.10) and define
Then holds for every feasible zero–one solution supported in . This formalizes the paper's relaxed extension step. Attainment excludes a lifting problem with no feasible point, as in the procedure after variable fixing.
Preamble
import Mathlib import Definitions.Def_CJP83_CoverSeparation_KnapsackRow
Formal statement
namespace CJP83.CoverSeparation
theorem relaxed_lifting_valid {ι : Type*} [Fintype ι] [DecidableEq ι]
(a : ι → ℚ) (a₀ : ℚ) (hpos : ∀ j, 0 < a j)
(S : Finset ι) (f : ι → ℤ) (f₀ : ℤ) (k : ι) (hk : k ∉ S)
(hvalid : IsValidOn a a₀ S f f₀)
(zbar : ℝ) (hzbar : IsGreatest (relaxedLiftValues a a₀ S f k) zbar) :
IsValidOn a a₀ (insert k S)
(Function.update f k (f₀ - Int.floor zbar)) f₀ := by sorry
end CJP83.CoverSeparation
Source
Crowder, Johnson and Padberg, Solving Large-Scale Zero-One Linear Programming Problems, Operations Research 31 (1983), p. 814, Section 2.4, (2.10), relaxed lifting paragraph
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.