Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

§2, p. 5 — the Explicit Master describes P₃ = P₁ ∩ P₂

Proved
RobustBCPCVRP.Formulation.P3_eq_P1_inter_P2

by mikedeng1 · Oct 7, 2026 · Mathlib 0df444a (Lean v4.33.1)

column-generationinteger-programmingp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1vehicle-routing

Let G=(V,E)G=(V,E)G=(V,E), demands ddd, KKK vehicles and capacity CCC be a CVRP instance, and let P1P_1P1​, P2P_2P2​ be the polytopes of the paper and P3P_3P3​ the projection onto xxx of the Explicit Master system (1)–(6), x≥0x\ge 0x≥0, λ≥0\lambda\ge 0λ≥0, in which one vector λ\lambdaλ of q-route weights serves both (5) and (6). Then

P3=P1∩P2.P_3=P_1\cap P_2 .P3​=P1​∩P2​.

The paper's new formulation optimizes over the intersection of the cut polytope P1P_1P1​ and the q-route polytope P2P_2P2​; this statement identifies that intersection with the single lifted system the algorithm actually works with.

Formalization Note No hypothesis on the instance is needed. Membership is stated for every function xxx on unordered pairs; each of P1,P2,P3P_1,P_2,P_3P1​,P2​,P3​ requires xxx to vanish off EEE.

Preamble
import Mathlib
import Definitions.Def_LysgaardCVRP_Shrink_cut
import Definitions.Def_LysgaardCVRP_Shrink_roundedCapacityBound
import Definitions.Def_RobustBCPCVRP_Formulation_Setting
import Definitions.Def_RobustBCPCVRP_Formulation_Polytopes
open LysgaardCVRP.Shrink
Formal statement
namespace RobustBCPCVRP.Formulation
theorem P3_eq_P1_inter_P2 {n : ℕ} (E : Finset (Sym2 (Fin (n + 1))))
    (d : Fin (n + 1) → ℕ) (K C : ℕ) (x : Sym2 (Fin (n + 1)) → ℝ) :
    InP3 E d K C x ↔ InP1 E d K C x ∧ InP2 E d K C x := by sorry
end RobustBCPCVRP.Formulation
Source
Fukasawa, Longo, Lysgaard, Poggi de Aragão, Reis, Uchoa & Werneck, Robust branch-and-cut-and-price for the capacitated vehicle routing problem, Math. Program. (DOI 10.1007/s10107-005-0644-x); accepted manuscript, p. 5, §2, display of P₃ (left-hand side P₃ = P₁∩P₂)
Human review
  • Endorsed by Shuze Chen · Oct 7, 2026

    Confirmed by the moderator at approval.

  • Endorsed by mikedeng1 · Oct 7, 2026

    Confirmed by the mission captain (proposal self-audit).

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me