While this submission is a draft, it cannot be used by other submissions.

Problems with bounds on parameters

Lax434175.Bounded · concepts/Lax434175/Bounded.lean · lax-434175

proven

Loading review…

Sign in with ORCID

Community review

Flags

Each flag is tied to a public ORCID identity and explains why this concept may be incorrect.

No flags have been submitted.

    Community review

    Flag this concept

    State precisely what appears incorrect. This explanation will be public under your ORCID name.

    No source line selected.

    Natural Language Statement

    Theorem

    Some special cases of a problem are not a choice of one value per field: they bound a quantity that reads several fields at once. Zero slack, dj=rj+pjd_j = r_j + p_j, reads the release date (kernel), the processing time (kernel) and the due date (objective), so no single field can express it. Such a special case is a bounded problem: the instances of a problem on which finitely many parameters are at most given numbers. A parameter is any function of the instance into the naturals, so "slack at most σ\sigma", "window at most kk" and "pmax⁡≤kp_{\max} \le k" are all bounds.

    A bounded problem is a restriction of its problem, so it is a special case of it by the inclusion of instances, and a reading of the problem is a reading of the bounded problem on the same words.

    Theorem. A bounded problem is a special case of its problem.

    Theorem. A sound embedding of AA in BB that maps every instance within the bounds of AA to an instance within the bounds of BB makes the bounded problem of AA a special case of the bounded problem of BB. If it maps every instance of AA within the bounds of BB, then AA itself is a special case of the bounded problem of BB.

    On one machine with release dates and due dates, the due-date slack of a job is dj−rj−pjd_j - r_j - p_j, truncated at 00, and the parameter is its largest value over the jobs. Bounding it by 00 gives the problem in which no job has room to move: dj≤rj+pjd_j \le r_j + p_j for every job, so a job is on time exactly when it starts at its release date and completes at its due date dj=rj+pjd_j = r_j + p_j, or it cannot be on time at all.

    Theorem. 1∣∣∑wjZj1 \mid\mid \sum w_j Z_j is a special case of 1∣rj∣∑wjUj1 \mid r_j \mid \sum w_j U_j with due-date slack 00: the encoding with release dates rj=dj−pjr_j = d_j - p_j produces only instances of slack 00.

    Concept map
    46 concepts
    100%
    Conjunctive normal formAssembling problems from fieldsProblems with bounds on parametersCommunication delaysBounds on the number of machines and jobsDeadlinesRelations of the Scheduling Zoo that need anencodingForbidden times and input encodingsScheduling kernelsMachine sets and multiprocessor tasksConstraint modules and objectivesNon-preemptive scheduling on parallelmachinesCompletion-time objectivesOnline scheduling as a gameParallel machinesProblems on parallel machines in three-fieldnotationParameters along embeddingsPrecedence constraints and time lagsPreemptive scheduling on parallel machinesOptimization problems and embeddingsRelease datesPreemption with restarts on parallelmachinesThe kinds of results on scheduling problemsA single server with setup timesNo-idle shops and batch setup timesShop problems in three-field notationShop schedulingThreshold reductions between objectivesTransportation delays and a transport robotScheduling problems as parameterizedproblems on wordsBinary encoding of an input and a certificateThe complexity class NPThe complexity class PFixed-Parameter Time on the Word RAMFPT-Reductions, FPT, Hardness andCompletenessFinite Relational StructuresFirst-Order Formulas and the Classes Σ_tand Π_tModel Checking and Weighted FaginDefinabilityThe W-Hierarchy and the A-HierarchyNP-Hardness of a Problem on Words ofNumbersBinary encoding of finite wordsPolynomial-time computation by a wordRAMPolynomial-time computation by a TuringmachineThe word RAMComputing a function within a time boundParameterized Problems andFPT-Reductions on a Word RAM
    Proven claimDefinitionThis conceptRelated conceptA → B: B builds on A
    Evidence

    This concept declares 4 statements. Each proof establishes one of them relative to its assumptions.

    1 bounded_mono proven

    2 bounded_specialCase proven

    3 specialCase_bounded proven

    4 weightedJustInTime_zeroSlack proven

    Lean source view on GitHub

    1import Lax434175.Encodings
    2import Lax434175.Results
    3
    4/-!
    5---
    6title: Problems with bounds on parameters
    7type: theorem
    8---
    9Some special cases of a problem are not a choice of one value per field: they
    10bound a quantity that reads several fields at once. Zero slack, dj=rj+pjd_j = r_j + p_j,
    11reads the release date (kernel), the processing time (kernel) and the due date
    12(objective), so no single field can express it. Such a special case is a
    13*bounded problem*: the instances of a problem on which finitely many parameters
    14are at most given numbers. A parameter is any function of the instance into the
    15naturals, so "slack at most σ\sigma", "window at most kk" and
    16"pmax⁡≤kp_{\max} \le k" are all bounds.
    17
    18A bounded problem is a restriction of its problem, so it is a special case of
    19it by the inclusion of instances, and a reading of the problem is a reading of
    20the bounded problem on the same words.
    21
    22**Theorem.** A bounded problem is a special case of its problem.
    23
    24**Theorem.** A sound embedding of AA in BB that maps every instance within the
    25bounds of AA to an instance within the bounds of BB makes the bounded problem
    26of AA a special case of the bounded problem of BB. If it maps every instance
    27of AA within the bounds of BB, then AA itself is a special case of the
    28bounded problem of BB.
    29
    30On one machine with release dates and due dates, the *due-date slack* of a job
    31is dj−rj−pjd_j - r_j - p_j, truncated at 00, and the parameter is its largest value
    32over the jobs. Bounding it by 00 gives the problem in which no job has room to
    33move: dj≤rj+pjd_j \le r_j + p_j for every job, so a job is on time exactly when it
    34starts at its release date and completes at its due date dj=rj+pjd_j = r_j + p_j, or it
    35cannot be on time at all.
    36
    37**Theorem.** 1∣∣∑wjZj1 \mid\mid \sum w_j Z_j is a special case of
    381∣rj∣∑wjUj1 \mid r_j \mid \sum w_j U_j with due-date slack 00: the encoding with release
    39dates rj=dj−pjr_j = d_j - p_j produces only instances of slack 00.
    40-/
    41
    42namespace Lax434175.Bounded
    43open Lax434175 Lax434175.Problems Lax434175.Parameters Lax434175.Assembly
    44open Lax434175.ParallelMachines Lax434175.ParallelProblems Lax434175.Encodings
    45
    46/-- A bound `κ ≤ k` on a parameter of a problem. -/
    47structure Bound (P : Problem) where
    48 /-- The parameter. -/
    49 param : Parameter P
    50 /-- Its largest admitted value. -/
    51 value : ℕ
    52
    53/-- The instance is within every bound of the list. -/
    54def holds {P : Problem} (bs : List (Bound P)) (x : P.Inst) : Prop :=
    55 ∀ b ∈ bs, b.param x ≤ b.value
    56
    57/-- The bounded problem: the instances of `P` within the bounds `bs`. -/
    58def bounded (P : Problem) (bs : List (Bound P)) : Problem :=
    59 P.restrict (holds bs)
    60
    61/-- A reading of a problem read on the instances of a bounded problem: the same
    62words. -/
    63def reading {P : Problem} (R : Results.PReading P) (bs : List (Bound P)) :
    64 Results.PReading (bounded P bs) where
    65 Encodes w x := R.Encodes w x.1
    66 Decodes x w σ := R.Decodes x.1 w σ
    67 reveal := ⟨fun x y t => R.reveal.same x.1 y.1 t, fun x y σ τ t => R.reveal.agree x.1 y.1 σ τ t⟩
    68
    69axiom bounded_specialCase (P : Problem) (bs : List (Bound P)) : SpecialCase (bounded P bs) P
    70
    71axiom bounded_mono {A B : Problem} (e : Embedding A B) (he : e.Sound)
    72 (bs : List (Bound A)) (cs : List (Bound B)) (h : ∀ x, holds bs x → holds cs (e.map x)) :
    73 SpecialCase (bounded A bs) (bounded B cs)
    74
    75axiom specialCase_bounded {A B : Problem} (e : Embedding A B) (he : e.Sound)
    76 (cs : List (Bound B)) (h : ∀ x, holds cs (e.map x)) : SpecialCase A (bounded B cs)
    77
    78/-- The largest due-date slack `d_j - r_j - p_j`, truncated at `0`, on parallel
    79machines; `p_j` is the time of the job on all its machines together, which on
    80one machine is its processing time. A due date is `0` when the objective has
    81none. -/
    82def dueSlack (s : Spec nonpreemptive) : Parameter (problem nonpreemptive s) := fun x =>
    83 Finset.univ.sup fun j =>
    84 Objectives.dueDate (K := Nonpreemptive.model.kernel) s.objective x.objectiveData j
    85 - x.base.r j - duration x.base j Finset.univ
    86
    87/-- `1 | r_j, d_j ≤ r_j + p_j | Σ w_j U_j`: one machine, release dates, weighted
    88late jobs, and due-date slack `0`. -/
    89def zeroSlackWeightedLate : Problem :=
    90 bounded (problem nonpreemptive (singleRelease .sumWU)) [⟨dueSlack (singleRelease .sumWU), 0⟩]
    91
    92axiom weightedJustInTime_zeroSlack :
    93 SpecialCase (problem nonpreemptive (single .sumWZ)) zeroSlackWeightedLate
    94
    95end Lax434175.Bounded
    96
    Show ProofShow ProofShow ProofShow Proof
    Builds on
    Used by

    none

    From Mathlib

    none

    Discussion

    Ask a question or add context. Endorsements and structured flags are kept in the review panel above.

    Loading discussion…