§2, p.7 — LP (1) is a relaxation
ProvedAndOrSched.section_2_lp1_relaxationand-or-precedenceapproximation-algorithmslinear-programmingmin-sum-set-coverp2o-gran-per-chapterp2o-plan-paperp2o-v1scheduling
Let be a normalized instance with acyclic AND-precedences and for all . Then LP (1) has an optimal solution , and for every optimal and every feasible schedule ,
So the LP value is a lower bound on the optimal value of the scheduling problem.
Differences from the source:
- encoding: a precedence digraph E∧ → hypothesis
Acyclic I; reason: a precedence graph is acyclic; the paper's transitive-closure and redundancy assumptions presuppose it - reading: the page presupposes an optimal fractional solution x̄ → existence of an optimal solution is a clause of the statement; reason: the algorithm needs it, and the bound alone would be vacuous without it
- encoding: lower bound on the optimal objective value → bound against the cost of every feasible schedule (idle time and non-integer completion times allowed); reason: equivalent, and avoids an infimum
Preamble
import Mathlib import Definitions.Def_AndOrSched_Instance import Definitions.Def_AndOrSched_Acyclic import Definitions.Def_AndOrSched_IsFeasible import Definitions.Def_AndOrSched_cost import Definitions.Def_AndOrSched_IsNormalized import Definitions.Def_AndOrSched_LP1Obj import Definitions.Def_AndOrSched_LP1Optimal open scoped Classical NNReal
Formal statement
namespace AndOrSched
/-- §2, p.7 (Happach, Schulz, arXiv:2001.07011v1): "Note that Σj wjC̄j is a lower bound on the objective value of an optimal integer
solution, which corresponds to an optimal schedule."
For a normalized instance with acyclic AND-precedences and processing times at most `1`, LP (1) has
an optimal solution, and the objective value `Σ_b w_b C̄_b` of every optimal solution is at most the
cost of every feasible schedule.
**Formalization Note** The cost of a normalized instance counts `B`-jobs only, since `w_a = 0` on
`A`. Feasible schedules may have idle time and non-integer completion times. -/
theorem section_2_lp1_relaxation (I : Instance) (hI : Acyclic I) (hN : IsNormalized I)
(hp : ∀ j, I.p j ≤ 1) :
(∃ x, LP1Optimal I x) ∧
∀ x, LP1Optimal I x → ∀ C : I.N → ℝ, IsFeasible I C → LP1Obj I x ≤ cost I C := by sorry
end AndOrSched
Source
F. Happach, A. S. Schulz, Approximation Algorithms and LP Relaxations for Scheduling Problems Related to Min-Sum Set Cover, arXiv:2001.07011v1, §2, p.7, "Note that Σj wjC̄j is a lower bound on the objective value of an optimal integer solution, which corresponds to an optimal schedule."
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.