Lemma 2, p. 19 — a route whose reduced cost exceeds ub − φ(RF1) is in no optimal solution of SF1
ProvedOnDemandDelivery.RouteElim.lemma_2Consider the single-period routing subproblem SF1 of the Benders decomposition of Liu and Luo: in period , choose a set of routes from the finite route set (binary ) of minimum total cost , so that every current location is served exactly once (), at most routes are used, and in every future period at most chosen routes are still running. Here . Let RF1 be its LP relaxation (, covering rows ).
Let be an upper bound of SF1 (at least the cost of every optimal solution), let be the optimal cost of RF1, let be a dual optimal solution of RF1 (dual variables , , of the rows (25), (19), (26)), and let . If
then in every optimal solution of SF1.
In words: once RF1 is solved, every route whose reduced cost exceeds the gap can be discarded before SF1 is solved exactly. This is the pruning rule of the paper's route enumeration algorithm.
Formalization Note is the attained minimum of RF1 (an IsLeast hypothesis); "dual optimal" is maximality of the dual objective over the dual feasible set, with the standard sign convention , , (the paper does not print it). "An upper bound of SF1" is read in its weakest form, the cost of every optimal solution. The standing assumptions also include and ((17), (21)). Routes, locations and future periods are arbitrary finite types.
import Mathlib import Definitions.Def_OnDemandDelivery_RouteElim_Setting
namespace OnDemandDelivery.RouteElim
theorem lemma_2 {R I P : Type} [Fintype R] [Fintype I] [Fintype P]
(D : Data R I P) (hD : D.Standing)
(ub : ℝ) (hub : ∀ θ, D.SF1Optimal θ → D.cost θ ≤ ub)
(φ : ℝ) (hφ : IsLeast (D.cost '' {θ | D.RF1Feasible θ}) φ)
(μ : P → ℝ) (μn : ℝ) (ν : I → ℝ) (hdual : D.DualOptimal μ μn ν)
(r : R) (h33 : ub - φ < D.reducedCost μ μn ν r) :
∀ θ, D.SF1Optimal θ → θ r = 0 := by sorry
end OnDemandDelivery.RouteElim
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.