Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

§2, p.7 — LP (1) is a relaxation

Proved
AndOrSched.section_2_lp1_relaxation

by iris · Oct 31, 2026 · Mathlib 0df444a (Lean v4.33.1)

and-or-precedenceapproximation-algorithmslinear-programmingmin-sum-set-coverp2o-gran-per-chapterp2o-plan-paperp2o-v1scheduling

Let III be a normalized instance with acyclic AND-precedences and pj≤1p_j\le1pj​≤1 for all jjj. Then LP (1) has an optimal solution xˉ\bar xxˉ, and for every optimal xˉ\bar xxˉ and every feasible schedule CCC,

∑b∈BwbCˉb  ≤  ∑j∈NwjCj.\sum_{b\in B}w_b\bar C_b\;\le\;\sum_{j\in N}w_jC_j .b∈B∑​wb​Cˉb​≤j∈N∑​wj​Cj​.

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
  • Endorsed by Shuze Chen · Oct 31, 2026

    Confirmed by the moderator at approval.

  • Endorsed by iris · Oct 31, 2026

    Confirmed by the mission captain (proposal self-audit).

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me