p. 411 — bounds with the same ranking make the branch-and-bound procedure follow the same path
ProvedIgnallSchrage.Invariance.run_eq_of_strictMonoLet and be two bound functions on nodes, and let be strictly increasing. Suppose that
for every node ( distinct jobs) with . Then the branch-and-bound procedure of p. 402 follows the same path with as with : for every , the list of nodes after steps is the same,
This is the paper's "the ranking of the lower bounds is unaffected …, implying that the path taken by the branch-and-bound procedure is also unaffected", stated for any order-preserving change of the bounds. The shift () and the scale () are special cases.
Formalization Note The procedure is the deterministic one of the definition Procedure, ties included. Since is strictly increasing, exactly when , so every comparison, ties included, comes out the same. The hypothesis concerns only nodes with , the only nodes the procedure compares: the root is alone on the initial list.
import Mathlib import Definitions.Def_IgnallSchrage_Makespan_Procedure
namespace IgnallSchrage.Invariance
/-- p. 411: if two bound functions rank the nodes the procedure compares in the same way —
`LB' J = φ (LB J)` for a strictly increasing `φ` at every node `J_r` with `1 ≤ r ≤ n - 1` —
then the branch-and-bound procedure follows the same path with both: the lists agree after
every number of steps. -/
theorem run_eq_of_strictMono {n : ℕ} (LB LB' : List (Fin n) → ℝ) (φ : ℝ → ℝ)
(hφ : StrictMono φ)
(h : ∀ J : List (Fin n), J.Nodup → 1 ≤ J.length → J.length + 1 ≤ n → LB' J = φ (LB J)) :
∀ k : ℕ, IgnallSchrage.Makespan.run LB' k = IgnallSchrage.Makespan.run LB k := by sorry
end IgnallSchrage.Invariance
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.