§5.2.2 (a) — the capacity constraints (33) are valid for F(M)
ProvedTwoEchelonCVRP.Config.capacity_inequalities_validp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1two-echelonvalid-inequalitiesvehicle-routing
Let be a set of first-level routes and let (with deliveries ) be a feasible solution of . For every set of at least two customers,
These are the capacity constraints (33) with which the LP relaxation of is strengthened; the statement is that they cut off no feasible solution of .
Formalization Note The ceiling is the natural-number ceiling of the rational number (with ).
Preamble
import Mathlib import Definitions.Def_TwoEchelonCVRP_Config_Configuration
Formal statement
namespace TwoEchelonCVRP.Config
/-- §5.2.2 (a), p. 306: the capacity constraints (33) are valid for F(M). For every feasible F(M)
solution and every set `H ⊆ N_C` with `|H| ≥ 2`,
`∑_{k ∈ N_S(M)} ∑_{l ∈ 𝓡_k : R_{kl} ∩ H ≠ ∅} x_{kl} ≥ ⌈∑_{i ∈ H} q_i / Q_2⌉`. -/
theorem capacity_inequalities_valid (I : Instance) (RS : RouteSystem I) (M : Finset RS.FR)
(t : SolFM RS) (ht : IsFeasibleFM RS M t) (H : Finset (Fin I.nc)) (hH : 2 ≤ H.card) :
⌈((∑ i ∈ H, I.q i : ℕ) : ℚ) / (I.Q2 : ℚ)⌉₊
≤ ∑ l ∈ Finset.univ.filter (fun l => RS.sat l ∈ NS RS M ∧ (RS.Rcust l ∩ H).Nonempty),
(t.x l).toNat := by sorry
end TwoEchelonCVRP.Config
Source
Baldacci, Mingozzi, Roberti & Wolfler Calvo, An Exact Algorithm for the Two-Echelon Capacitated Vehicle Routing Problem, Oper. Res. 61(2) (2013), p. 306, §5.2.2 (a), inequalities (33)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.