Word encoding of a scheduling instance
Lax470956.InstanceEncoding · concepts/Lax470956/InstanceEncoding.lean · lax-470956
No public endorsements yet.
Loading review…
Sign in with ORCIDNatural Language Statement
Definition
A scheduling instance is handed to a word random access machine as a word of numbers: the number of jobs, the number of machines, then the processing times, the deadlines, the weights, then offsets and a target array listing, for each job in turn, the machines eligible to run it. The offsets say where each job's block of eligible machines begins, the first being and the last the length of the target array. A decision instance appends the threshold as a final entry.
Concept map
Lean source view on GitHub
| 1 | import Lax470956.Scheduling |
| 2 | |
| 3 | /-! |
| 4 | --- |
| 5 | title: Word encoding of a scheduling instance |
| 6 | type: definition |
| 7 | --- |
| 8 | A scheduling instance is handed to a word random access machine as a word of numbers: |
| 9 | the number of jobs, the number of machines, then the processing times, the |
| 10 | deadlines, the weights, then offsets and a target array listing, for each |
| 11 | job in turn, the machines eligible to run it. The offsets say where each job's block of |
| 12 | eligible machines begins, the first being and the last the length of the target |
| 13 | array. A decision instance appends the threshold as a final entry. |
| 14 | |
| 15 | # Formalization notes |
| 16 | |
| 17 | The eligible sets are in the same compressed sparse row form that presents a graph to a |
| 18 | machine elsewhere in the archive, for the same reason: it is the adjacency-array format |
| 19 | an algorithm would actually be handed, with nothing precomputed. The blocks are not |
| 20 | required to be sorted and repetitions are not forbidden. Leaving those conditions out |
| 21 | admits more words and therefore strengthens, rather than weakens, every claim about |
| 22 | programs reading the format. |
| 23 | |
| 24 | Here magnitudes stop being free. The processing times, deadlines |
| 25 | and weights are entries of the word, so a claim about a program reading it has to say |
| 26 | that they are words — which the fitting conditions of `ParameterizedComplexity` do, |
| 27 | once, as an explicit inequality against `2 ^ w`. A size measure that counted only the |
| 28 | number of jobs and machines would make the weights of a reduction's output invisible, |
| 29 | and a running time stated against it would not be a claim about anything a machine does. |
| 30 | |
| 31 | Cells are read with `List.getD`, which returns `0` outside the word; the length |
| 32 | condition pins the word down completely, so the default is never reached at a position |
| 33 | the other conditions constrain. Unlike a graph encoding, the length is not determined by |
| 34 | the header alone — the target array is as long as the last offset says — so |
| 35 | `length_eq` reads that offset rather than a declared edge count. |
| 36 | |
| 37 | The threshold is appended last, so that the instance block sits at the same offsets |
| 38 | whether or not a threshold follows it, and the split of the word into the two parts is |
| 39 | determined by the word rather than chosen. |
| 40 | -/ |
| 41 | |
| 42 | namespace Lax470956.InstanceEncoding |
| 43 | |
| 44 | open Lax470956.Scheduling |
| 45 | |
| 46 | /-- The number of jobs declared by a word: its first entry. -/ |
| 47 | def jobCount (x : List ℕ) : ℕ := x.getD 0 0 |
| 48 | |
| 49 | /-- The number of machines declared by a word: its second entry. -/ |
| 50 | def machineCount (x : List ℕ) : ℕ := x.getD 1 0 |
| 51 | |
| 52 | /-- The processing time of job `j`: the processing times follow the two header |
| 53 | entries. -/ |
| 54 | def proc (x : List ℕ) (j : ℕ) : ℕ := x.getD (2 + j) 0 |
| 55 | |
| 56 | /-- The deadline of job `j`: the deadlines follow the processing times. -/ |
| 57 | def due (x : List ℕ) (j : ℕ) : ℕ := x.getD (2 + jobCount x + j) 0 |
| 58 | |
| 59 | /-- The weight of job `j`: the weights follow the deadlines. -/ |
| 60 | def wt (x : List ℕ) (j : ℕ) : ℕ := x.getD (2 + 2 * jobCount x + j) 0 |
| 61 | |
| 62 | /-- The `i`-th offset: the `n+1` offsets follow the weights. -/ |
| 63 | def offset (x : List ℕ) (i : ℕ) : ℕ := x.getD (2 + 3 * jobCount x + i) 0 |
| 64 | |
| 65 | /-- The `t`-th entry of the target array, which follows the offsets. -/ |
| 66 | def target (x : List ℕ) (t : ℕ) : ℕ := x.getD (3 + 4 * jobCount x + t) 0 |
| 67 | |
| 68 | /-- The word `x` encodes the instance `I`. -/ |
| 69 | structure EncodesInstance (x : List ℕ) (I : Instance) : Prop where |
| 70 | /-- The word declares `I`'s jobs. -/ |
| 71 | jobCount_eq : jobCount x = I.jobs |
| 72 | /-- The word declares `I`'s machines. -/ |
| 73 | machineCount_eq : machineCount x = I.machines |
| 74 | /-- The word consists of the two header entries, the three arrays of one number per |
| 75 | job, the `n+1` offsets, and a target array as long as the last offset says. -/ |
| 76 | length_eq : x.length = 3 + 4 * I.jobs + offset x I.jobs |
| 77 | /-- The processing times are `I`'s. -/ |
| 78 | proc_eq : ∀ j : Fin I.jobs, proc x j = I.p j |
| 79 | /-- The deadlines are `I`'s. -/ |
| 80 | due_eq : ∀ j : Fin I.jobs, due x j = I.d j |
| 81 | /-- The weights are `I`'s. -/ |
| 82 | wt_eq : ∀ j : Fin I.jobs, wt x j = I.w j |
| 83 | /-- The block of the first job begins at the start of the target array. -/ |
| 84 | offset_zero : offset x 0 = 0 |
| 85 | /-- The offsets are nondecreasing, so they cut the target array into one block per |
| 86 | job. -/ |
| 87 | offset_mono : ∀ j < I.jobs, offset x j ≤ offset x (j + 1) |
| 88 | /-- Every entry of the target array is a machine. -/ |
| 89 | target_lt : ∀ t < offset x I.jobs, target x t < I.machines |
| 90 | /-- The block of a job lists exactly its eligible machines. -/ |
| 91 | eligible_iff : ∀ (j : Fin I.jobs) (i : Fin I.machines), |
| 92 | i ∈ I.eligible j ↔ ∃ t, offset x j ≤ t ∧ t < offset x (j + 1) ∧ target x t = i |
| 93 | |
| 94 | /-- The word `x` presents the instance `I` together with the threshold `W`: an instance |
| 95 | block followed by the single entry `W`. -/ |
| 96 | def EncodesDecisionInstance (x : List ℕ) (I : Instance) (W : ℕ) : Prop := |
| 97 | ∃ y, x = y ++ [W] ∧ EncodesInstance y I |
| 98 | |
| 99 | /-- The words that encode a decision instance. -/ |
| 100 | def DecisionInstances : Set (List ℕ) := |
| 101 | {x | ∃ I W, EncodesDecisionInstance x I W} |
| 102 | |
| 103 | /-- The words that encode an instance, with no threshold. -/ |
| 104 | def Instances : Set (List ℕ) := {x | ∃ I, EncodesInstance x I} |
| 105 | |
| 106 | end Lax470956.InstanceEncoding |
| 107 |
Formalization notes
The eligible sets are in the same compressed sparse row form that presents a graph to a machine elsewhere in the archive, for the same reason: it is the adjacency-array format an algorithm would actually be handed, with nothing precomputed. The blocks are not required to be sorted and repetitions are not forbidden. Leaving those conditions out admits more words and therefore strengthens, rather than weakens, every claim about programs reading the format.
Here magnitudes stop being free. The processing times, deadlines and weights are entries of the word, so a claim about a program reading it has to say that they are words — which the fitting conditions of do, once, as an explicit inequality against . A size measure that counted only the number of jobs and machines would make the weights of a reduction's output invisible, and a running time stated against it would not be a claim about anything a machine does.
Cells are read with , which returns outside the word; the length condition pins the word down completely, so the default is never reached at a position the other conditions constrain. Unlike a graph encoding, the length is not determined by the header alone — the target array is as long as the last offset says — so reads that offset rather than a declared edge count.
The threshold is appended last, so that the instance block sits at the same offsets whether or not a threshold follows it, and the split of the word into the two parts is determined by the word rather than chosen.
Builds on
From Mathlib
none
Discussion
Ask a question or add context. Endorsements and structured flags are kept in the review panel above.
0 comments