Problems with bounds on parameters
Lax434175.Bounded · concepts/Lax434175/Bounded.lean · lax-434175
No public endorsements yet.
Loading review…
Sign in with ORCIDNatural 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, , 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 ", "window at most " and "" 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 in that maps every instance within the bounds of to an instance within the bounds of makes the bounded problem of a special case of the bounded problem of . If it maps every instance of within the bounds of , then itself is a special case of the bounded problem of .
On one machine with release dates and due dates, the due-date slack of a job is , truncated at , and the parameter is its largest value over the jobs. Bounding it by gives the problem in which no job has room to move: for every job, so a job is on time exactly when it starts at its release date and completes at its due date , or it cannot be on time at all.
Theorem. is a special case of with due-date slack : the encoding with release dates produces only instances of slack .
Concept map
Evidence
Lean source view on GitHub
| 1 | import Lax434175.Encodings |
| 2 | import Lax434175.Results |
| 3 | |
| 4 | /-! |
| 5 | --- |
| 6 | title: Problems with bounds on parameters |
| 7 | type: theorem |
| 8 | --- |
| 9 | Some special cases of a problem are not a choice of one value per field: they |
| 10 | bound a quantity that reads several fields at once. Zero slack, , |
| 11 | reads 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 |
| 14 | are at most given numbers. A parameter is any function of the instance into the |
| 15 | naturals, so "slack at most ", "window at most " and |
| 16 | "" are all bounds. |
| 17 | |
| 18 | A bounded problem is a restriction of its problem, so it is a special case of |
| 19 | it by the inclusion of instances, and a reading of the problem is a reading of |
| 20 | the 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 in that maps every instance within the |
| 25 | bounds of to an instance within the bounds of makes the bounded problem |
| 26 | of a special case of the bounded problem of . If it maps every instance |
| 27 | of within the bounds of , then itself is a special case of the |
| 28 | bounded problem of . |
| 29 | |
| 30 | On one machine with release dates and due dates, the *due-date slack* of a job |
| 31 | is , truncated at , and the parameter is its largest value |
| 32 | over the jobs. Bounding it by gives the problem in which no job has room to |
| 33 | move: for every job, so a job is on time exactly when it |
| 34 | starts at its release date and completes at its due date , or it |
| 35 | cannot be on time at all. |
| 36 | |
| 37 | **Theorem.** is a special case of |
| 38 | with due-date slack : the encoding with release |
| 39 | dates produces only instances of slack . |
| 40 | -/ |
| 41 | |
| 42 | namespace Lax434175.Bounded |
| 43 | open Lax434175 Lax434175.Problems Lax434175.Parameters Lax434175.Assembly |
| 44 | open Lax434175.ParallelMachines Lax434175.ParallelProblems Lax434175.Encodings |
| 45 | |
| 46 | /-- A bound `κ ≤ k` on a parameter of a problem. -/ |
| 47 | structure 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. -/ |
| 54 | def 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`. -/ |
| 58 | def 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 |
| 62 | words. -/ |
| 63 | def 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 | |
| 69 | axiom bounded_specialCase (P : Problem) (bs : List (Bound P)) : SpecialCase (bounded P bs) P |
| 70 | |
| 71 | axiom 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 | |
| 75 | axiom 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 |
| 79 | machines; `p_j` is the time of the job on all its machines together, which on |
| 80 | one machine is its processing time. A due date is `0` when the objective has |
| 81 | none. -/ |
| 82 | def 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 |
| 88 | late jobs, and due-date slack `0`. -/ |
| 89 | def zeroSlackWeightedLate : Problem := |
| 90 | bounded (problem nonpreemptive (singleRelease .sumWU)) [⟨dueSlack (singleRelease .sumWU), 0⟩] |
| 91 | |
| 92 | axiom weightedJustInTime_zeroSlack : |
| 93 | SpecialCase (problem nonpreemptive (single .sumWZ)) zeroSlackWeightedLate |
| 94 | |
| 95 | end Lax434175.Bounded |
| 96 |
Discussion
Ask a question or add context. Endorsements and structured flags are kept in the review panel above.
0 comments