p. 812, §2.3 — a violated cover gives a separation value below one
ProvedCJP83.CoverSeparation.violated_cover_implies_knapsack_value_lt_onecover-separationknapsackp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1
Let be a minimal cover for a positive-weight row (2.5), and let be a real vector. Suppose the minimum of the strict-cover separation problem (2.12) exists. If the cover inequality cuts off , then
This is the forward direction of the paper's separation equivalence. It does not use bounds on ; the minimum hypothesis means that (2.12) has an attained feasible value.
Preamble
import Mathlib import Definitions.Def_CJP83_CoverSeparation_KnapsackRow
Formal statement
namespace CJP83.CoverSeparation
theorem violated_cover_implies_knapsack_value_lt_one
{ι : Type*} [Fintype ι] [DecidableEq ι]
(a : ι → ℚ) (a₀ : ℚ) (hpos : ∀ j, 0 < a j)
(xbar : ι → ℝ) (z : ℝ) (hz : IsLeast (sepValues a a₀ xbar) z)
(S : Finset ι) (hcover : IsMinimalCover a a₀ S)
(hviolated : (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), forward direction
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.