p. 1014 — the standard linearization (8) is a relaxation: MP_G ⊆ MP^LP_G
ProvedRunIntersect.Strict.MP_subset_MPLPmultilinear-polytopep2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1standard-linearization
Let be a hypergraph. The standard linearization of (8), obtained by replacing each multilinear equation by its convex hull over the unit hypercube, contains the multilinear polytope:
Together with Proposition 1 this gives the inclusion for every hypergraph.
Preamble
import Mathlib import Definitions.Def_RunIntersect_Strict_Setting
Formal statement
namespace RunIntersect.Strict
/-- p. 1014: the standard linearization (8) is a relaxation of the multilinear set:
`MP_G ⊆ MP^LP_G`. -/
theorem MP_subset_MPLP {α : Type*} [Fintype α] [DecidableEq α] (G : Hypergraph α) :
MP G ⊆ MPLP G := by sorry
end RunIntersect.Strict
Source
Del Pia and Khajavirad, The running intersection relaxation of the multilinear polytope, Math. Oper. Res. 46 (2021), p. 1014, (8) and the sentence before it
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.