p. 810, (2.7) — validity of the minimal cover inequality
ProvedCJP83.CoverSeparation.cover_inequality_validcover-inequalityknapsackp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1
Let be finite, with positive rational weights and rational capacity . If is a minimal cover of (2.5), then every feasible zero–one vector satisfies
This is the validity claim for inequality (2.7), used before the paper lifts cover inequalities to other variables. The same bound holds for any cover, though the paper states it here for minimal covers.
Preamble
import Mathlib import Definitions.Def_CJP83_CoverSeparation_KnapsackRow
Formal statement
namespace CJP83.CoverSeparation
theorem cover_inequality_valid {ι : Type*} [Fintype ι] [DecidableEq ι]
(a : ι → ℚ) (a₀ : ℚ) (hpos : ∀ j, 0 < a j)
(S x : Finset ι) (hcover : IsMinimalCover a a₀ S)
(hx : IsRowFeasible a a₀ x) :
(∑ j ∈ S, binaryValue x j) ≤ (S.card : ℝ) - 1 := by sorry
end CJP83.CoverSeparation
Source
Crowder, Johnson and Padberg, Solving Large-Scale Zero-One Linear Programming Problems, Operations Research 31 (1983), p. 810, Section 2.2, (2.7)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.