Proposition 2 — a satellite supply bound θ that needs too many second-level vehicles makes F(M) infeasible
ProvedTwoEchelonCVRP.Config.proposition_2p2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1pruningtwo-echelonvehicle-routing
Let be a configuration and let , , be real numbers such that every feasible solution of supplies at least to satellite :
If
then has no feasible solution, so can be removed from .
This is the second pruning test used to generate .
Formalization Note The ceilings are integer ceilings of real numbers. The paper writes "for some "; is only defined on , so the condition is read for . The bound is a hypothesis; the paper's way of computing it, problem (27)–(32), is not part of this statement.
Preamble
import Mathlib import Definitions.Def_TwoEchelonCVRP_Config_Configuration
Formal statement
namespace TwoEchelonCVRP.Config
/-- Proposition 2, p. 305: let `M ∈ 𝒫` and let `θ(k)`, `k ∈ N_S(M)`, be a lower bound on the
quantity `∑_{r ∈ M_k} q_{kr}` supplied to satellite `k` in every feasible F(M) solution. If
`∑_{k ∈ N_S(M)} ⌈θ(k)/Q_2⌉ > m^2`, or `⌈θ(k)/Q_2⌉ > m_k` for some `k ∈ N_S(M)`, then F(M) has no
feasible solution. -/
theorem proposition_2 (I : Instance) (RS : RouteSystem I) (M : Finset RS.FR) (hMP : InP RS M)
(θ : Fin I.ns → ℝ)
(hθ : ∀ t : SolFM RS, IsFeasibleFM RS M t → ∀ k ∈ NS RS M, θ k ≤ ∑ r ∈ Mk RS M k, t.qd r k)
(htest : (I.m2 : ℤ) < ∑ k ∈ NS RS M, ⌈θ k / (I.Q2 : ℝ)⌉ ∨
∃ k ∈ NS RS M, (I.m k : ℤ) < ⌈θ k / (I.Q2 : ℝ)⌉) :
∀ t : SolFM RS, ¬ IsFeasibleFM RS M t := 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. 305, Proposition 2
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.