p. 812, §2.3 — violated cover iff separation optimum is below one
ProvedCJP83.CoverSeparation.violated_cover_iff_knapsack_value_lt_onecover-separationknapsackp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1
Let be finite, rational, rational, and for all . Suppose the strict-cover problem (2.12) attains its minimum objective value . Then
This is the paper's constraint identification equivalence: solving (2.12) detects a minimal cover inequality (2.7) that cuts off .
Formalization Note The paper takes to be an LP-relaxation optimum, but this result uses only its unit-cube bounds. Existence of the optimal value is explicit: if no cover exists, (2.12) has no feasible point and no minimum. The strict knapsack constraint remains strict.
Preamble
import Mathlib import Definitions.Def_CJP83_CoverSeparation_KnapsackRow
Formal statement
namespace CJP83.CoverSeparation
theorem violated_cover_iff_knapsack_value_lt_one
{ι : Type*} [Fintype ι] [DecidableEq ι]
(a : ι → ℚ) (a₀ : ℚ) (hpos : ∀ j, 0 < a j)
(xbar : ι → ℝ) (hcube : ∀ j, 0 ≤ xbar j ∧ xbar j ≤ 1)
(z : ℝ) (hz : IsLeast (sepValues a a₀ xbar) z) :
(∃ S : Finset ι, IsMinimalCover a a₀ S ∧
(S.card : ℝ) - 1 < ∑ j ∈ S, xbar j) ↔ z < 1 := by sorry
end CJP83.CoverSeparation
Source
Crowder, Johnson and Padberg, Solving Large-Scale Zero-One Linear Programming Problems, Operations Research 31 (1983), p. 812, Section 2.3, (2.7), (2.12), proof continues p. 813
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.