p. 811, (2.9) — validity of configuration inequalities
ProvedCJP83.CoverSeparation.configuration_inequality_validconfiguration-inequalityknapsackp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1
Let , and form a -configuration for the positive-weight row (2.5): and every -element subset makes a minimal cover. For each integer with and each of size , every feasible zero–one vector satisfies
These are all the inequalities in (2.9), including the cases and .
Preamble
import Mathlib import Definitions.Def_CJP83_CoverSeparation_KnapsackRow
Formal statement
namespace CJP83.CoverSeparation
theorem configuration_inequality_valid {ι : Type*} [Fintype ι] [DecidableEq ι]
(a : ι → ℚ) (a₀ : ℚ) (hpos : ∀ j, 0 < a j)
(Sstar : Finset ι) (t : ι) (k r : ℕ)
(hconfig : IsOneKConfiguration a a₀ Sstar t k)
(hr₁ : k ≤ r) (hr₂ : r ≤ Sstar.card)
(T x : Finset ι) (hT₁ : T ⊆ Sstar) (hT₂ : T.card = r)
(hx : IsRowFeasible a a₀ x) :
((r : ℝ) - (k : ℝ) + 1) * binaryValue x t +
∑ j ∈ T, binaryValue x j ≤ (r : ℝ) := by sorry
end CJP83.CoverSeparation
Source
Crowder, Johnson and Padberg, Solving Large-Scale Zero-One Linear Programming Problems, Operations Research 31 (1983), p. 811, Section 2.2, (2.8)–(2.9)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.