Floor-rounding certificate for a feasible configuration LP
ProvedKKBinPacking.GeometricGrouping.lp_floor_rounding_certificateLet be a finite bin-packing instance with real item sizes in , and let be any nonnegative feasible vector of the configuration LP. For each configuration , take copies as principal bins. Write
Let contain the items left after filling all available principal slots by type, with no original item used more than once. Thus its multiplicity at each size is
where is the multiplicity of size in configuration . There is a packing of the removed items satisfying
This certificate separates the combinatorial floor-and-delete operation from sparsity and LP optimality. Together with the elementary packing bound on , it supplies the rounding ingredient of Lemma 2.
Formalization Note Multiset subtraction truncates negative counts to zero. Principal configurations may over-cover the input; contains the retained original items, with excess configuration slots removed. Empty bins are allowed. The certificate covers every feasible , not only basic or optimal solutions.
import Definitions.Def_KKBinPacking_GeometricGrouping_Algorithm2 open KKBinPacking.Shared
namespace KKBinPacking.GeometricGrouping
theorem lp_floor_rounding_certificate
(I : Multiset ℝ) (hI : IsInstance I)
(x : Multiset ℝ →₀ ℝ) (hx : IsLPFeasible I x) :
let R := I - (principalConfigs x).join
∃ P : Multiset (Multiset ℝ),
IsPacking (I - R) P ∧
P.card ≤ principalCount x ∧
SIZE R ≤ lpCost x - (principalCount x : ℝ) ∧
(OPT R : ℝ) ≤ (x.support.card : ℝ) := by sorry
end KKBinPacking.GeometricGrouping