p. 814, §2.4 — integer lifting optimum is at most the rounded LP optimum
ProvedCJP83.CoverSeparation.integer_lift_boundknapsackliftingp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1
For a positive-weight row, let be the attained maximum of the zero–one lifting problem (2.10), with integer objective coefficients on . Let be the attained maximum of its linear relaxation, in which for . For ,
This bounds the integer optimum by the integer part of the relaxation optimum, the value denoted in the paper. The two maximum hypotheses exclude the infeasible case; is explicit because the floor step requires integrality.
Preamble
import Mathlib import Definitions.Def_CJP83_CoverSeparation_KnapsackRow
Formal statement
namespace CJP83.CoverSeparation
theorem integer_lift_bound {ι : Type*} [Fintype ι] [DecidableEq ι]
(a : ι → ℚ) (a₀ : ℚ) (hpos : ∀ j, 0 < a j)
(S : Finset ι) (f : ι → ℤ) (k : ι) (hk : k ∉ S)
(z : ℤ) (hz : IsGreatest (liftValues a a₀ S f k) z)
(zbar : ℝ) (hzbar : IsGreatest (relaxedLiftValues a a₀ S f k) zbar) :
z ≤ Int.floor zbar := by sorry
end CJP83.CoverSeparation
Source
Crowder, Johnson and Padberg, Solving Large-Scale Zero-One Linear Programming Problems, Operations Research 31 (1983), p. 814, Section 2.4, (2.10), relaxed lifting paragraph
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.