pp. 812–813, §2.3 — an optimum can be a minimal cover
ProvedCJP83.CoverSeparation.knapsack_optimum_has_minimal_covercover-separationknapsackp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1
Let for every , and suppose the strict-cover problem (2.12) has minimum value . For positive rational row weights, there is a minimal cover of (2.5) whose separation objective equals that minimum:
The claim is the reverse direction's central assertion, which begins on p. 812 and continues on p. 813. Nonnegative objective coefficients allow a cover to be reduced without increasing its objective. The paper calls the resulting inequality a “minimum cover” on p. 813; here minimality has its (2.6) meaning.
Preamble
import Mathlib import Definitions.Def_CJP83_CoverSeparation_KnapsackRow
Formal statement
namespace CJP83.CoverSeparation
theorem knapsack_optimum_has_minimal_cover
{ι : 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 ∧
(∑ j ∈ S, (1 - xbar j)) = z := by sorry
end CJP83.CoverSeparation
Source
Crowder, Johnson and Padberg, Solving Large-Scale Zero-One Linear Programming Problems, Operations Research 31 (1983), pp. 812–813, Section 2.3, (2.12), reverse direction
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.