The Integer Programs of the Clients' Reduction Are Fixed-Parameter Tractable

Lax117284.IlpClients · concepts/Lax117284/IlpClients.lean · lax-117284

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

    Definition

    An integer program here is a system of MM linear equality constraints over NN non-negative integer variables, with non-negative integer coefficients and right-hand sides: find x:FinN→Nx : Fin N → ℕ with ∑iaji∗xi=bj∑ᵢ a j i * x i = b j for every constraint jj. It is feasible if such an xx exists.

    The integer programs that the paper solves with Lenstra's algorithm (Heeger–Hermelin–Itzhaki–Molter–Shabtay, proof of Theorem 4's third bullet, via the integer program of Theorem4ILP.leanTheorem4ILP.lean's HasILPSolutionHasILPSolution) form one explicit family, one constraint matrix AnA_n for each number nn of clients: 2(n∗n)2 ^ (n * n) types of day (a type is a conflict relation on the clients), 2n2 ^ n subsets of clients, one variable for every pair of a type and a subset and one slack variable for every client, and one constraint for each type and one for each client. This module states, for exactly this family, that feasibility is fixed-parameter tractable in the number of variables: ilpClientsfptilpClients_fpt. The matrix is fixed by nn; only the right-hand side (the number cnttcnt t of days of each type tt and the number BB of days a client may go unserved) is free. The reduction of the problem of the clients to this problem is Theorem4.byClientsfptReducesilpTheorem4.byClients_fptReduces_ilp, and ilpClientsfptilpClients_fpt is proved in the proofs package, by a certificate-enumeration algorithm specific to these matrices. The search space depends only on the number of clients; each certificate is decoded using the right-hand sides, and the resulting assignment is checked.

    Concept map
    9 concepts; 1 descendant hidden
    100%
    Proven claimDefinitionThis conceptRelated conceptA → B: B builds on A
    Evidence

    Each proof establishes this claim relative to its assumptions.

    In the paper

    • page 6 of this submission's paper

    Lean source view on GitHub

    1import Mathlib.Algebra.BigOperators.Group.Finset.Basic
    2import Mathlib.Data.Fintype.Fin
    3import Mathlib.Data.Nat.Bitwise
    4import Lax117284.ParameterizedComplexity
    5
    6/-!
    7---
    8title: The Integer Programs of the Clients' Reduction Are Fixed-Parameter Tractable
    9type: definition
    10---
    11An *integer program* here is a system of `M` linear equality constraints over `N`
    12non-negative integer variables, with non-negative integer coefficients and right-hand
    13sides: find `x : Fin N → ℕ` with `∑ᵢ a j i * x i = b j` for every constraint `j`. It is
    14*feasible* if such an `x` exists.
    15
    16The integer programs that the paper solves with Lenstra's algorithm (Heeger–Hermelin–Itzhaki–Molter–Shabtay,
    17proof of Theorem 4's third bullet, via the integer program of `Theorem4ILP.lean`'s `HasILPSolution`) form
    18one explicit family, one constraint matrix `A_n` for each number `n` of clients: `2 ^ (n * n)` *types* of day
    19(a type is a conflict relation on the clients), `2 ^ n` subsets of clients, one variable for every
    20pair of a type and a subset and one slack variable for every client, and one constraint for each
    21type and one for each client. This module states, for exactly this family, that feasibility is
    22fixed-parameter tractable in the number of variables: `ilpClients_fpt`. The matrix is fixed by `n`;
    23only the right-hand side (the number `cnt t` of days of each type `t` and the number `B` of days a
    24client may go unserved) is free. The reduction of the problem of the clients to this problem is
    25`Theorem4.byClients_fptReduces_ilp`, and `ilpClients_fpt` is proved in the proofs package, by a
    26certificate-enumeration algorithm specific to these matrices. The search space depends
    27only on the number of clients; each certificate is decoded using the right-hand sides,
    28and the resulting assignment is checked.
    29
    30# Formalization Notes
    31
    32The family is written out here, the coefficient formula included, because this module cannot import the
    33proofs; the proofs identify it, definition by definition, with the construction of the reduction. Column
    34`t * 2^n + s` (`t` a type, `s` a subset of clients, both as numbers) has the coefficient `1` in the row of type
    35`t` and in the row of client `j` for every client `j` not in `s`, when `s` contains no two clients that `t` makes
    36conflict (`indepB`), and is the zero column otherwise; the column `2 ^ (n * n) * 2 ^ n + j` is the slack of client `j` and
    37has a single `1`, in the row of client `j`. The right-hand side is `cnt t` in the row of type `t` and `B` in
    38every client row.
    39
    40The domain is the words of this family, which are the words of the integer programs that the reduction
    41outputs, and, in addition, the fixed word `[1, 1, 0, 1]` of the infeasible program `0 · x = 1`. It is
    42needed: for `n ≤ 1` every member of the family is feasible, whatever the right-hand side, so for a fairness
    43parameter above the number of days the reduction has no infeasible word of the family to output. The
    44word of an integer program is its two counts, then the `M * N` coefficients of the constraint matrix row
    45by row, then the `M` right-hand sides (the layout convention of `InstSem.lean`'s `instToks`); reading it back
    46is total, missing entries being read as `0`.
    47
    48The decision theorem uses the archive's shared fixed-parameter time definition, with a
    49computable function of the number of variables and a polynomial in binary input size.
    50The verified solver enumerates certificates in a parameter-bounded box and checks the
    51reconstructed solutions. Its explicit bound is larger than the bound of the general
    52integer-programming algorithm cited in the source.
    53
    54-/
    55
    56namespace Lax117284.IlpClients
    57
    58open Lax117284.ParameterizedComplexity
    59
    60/-- **An integer program**: `M` linear equality constraints over `N` non-negative integer
    61variables, with non-negative integer coefficients `a` and right-hand sides `b`. -/
    62structure ILP where
    63 /-- The number of variables. -/
    64 N : ℕ
    65 /-- The number of constraints. -/
    66 M : ℕ
    67 /-- The coefficient of variable `i` in constraint `j`. -/
    68 a : Fin M → Fin N → ℕ
    69 /-- The right-hand side of constraint `j`. -/
    70 b : Fin M → ℕ
    71
    72/-- **`E` is feasible**: some assignment of its variables satisfies every constraint. -/
    73def ILP.Feasible (E : ILP) : Prop := ∃ x : Fin E.N → ℕ, ∀ j, ∑ i, E.a j i * x i = E.b j
    74
    75/-- The numbers of an integer program: the two counts, then the coefficients row by row,
    76then the right-hand sides. Total and well-defined on every list, reading absent entries as
    77`0`, exactly like `Instance.pAt`/`Instance.dAt`. -/
    78def decodeILP (w : List ℕ) : ILP where
    79 N := w.getD 0 0
    80 M := w.getD 1 0
    81 a := fun j i => w.getD (2 + j.val * w.getD 0 0 + i.val) 0
    82 b := fun j => w.getD (2 + w.getD 1 0 * w.getD 0 0 + j.val) 0
    83
    84/-- The number of types of day for `n` clients: `2 ^ (n * n)` (bit `a * n + b` of a type says
    85that clients `a` and `b` conflict on the days of that type). -/
    86def nT (n : ℕ) : ℕ := 2 ^ (n * n)
    87
    88/-- The number of subsets of the `n` clients, `2 ^ n` (bit `j` of a subset says that client `j` is served). -/
    89def nZ (n : ℕ) : ℕ := 2 ^ n
    90
    91/-- The number of pairs of a type and a subset, `2 ^ (n * n) * 2 ^ n`. -/
    92def nV (n : ℕ) : ℕ := nT n * nZ n
    93
    94/-- The number of variables, `2 ^ (n * n) * 2 ^ n + n`: one for every pair of a type and a
    95subset, and one slack for every client. -/
    96def nN (n : ℕ) : ℕ := nV n + n
    97
    98/-- The number of constraints, `2 ^ (n * n) + n`: one for every type and one for every client. -/
    99def nM (n : ℕ) : ℕ := nT n + n
    100
    101/-- The subset `S` (a number) is independent for the type `t` (a number): it contains no two distinct
    102clients `a`, `b` that the type makes conflict (bit `a * n + b` of `t`). -/
    103def indepB (n t S : ℕ) : Bool :=
    104 decide (∀ a < n, ∀ b < n, a ≠ b → S.testBit a = true → S.testBit b = true →
    105 t.testBit (a * n + b) = false)
    106
    107/-- The coefficient of variable `c` in constraint `r`: the variable `c < nV n` is the pair
    108of the type `c / 2 ^ n` and the subset `c % 2 ^ n`, whose column has a `1` in the row of its type and in the row
    109of every client outside the subset, unless the subset is not independent for the type, when the column is
    110zero; the other variables are the slacks, `1` in the row of their client. -/
    111def coef (n r c : ℕ) : ℕ :=
    112 if c < nV n then
    113 (if indepB n (c / nZ n) (c % nZ n) then
    114 (if r < nT n then (if c / nZ n = r then 1 else 0)
    115 else (if (c % nZ n).testBit (r - nT n) = false then 1 else 0))
    116 else 0)
    117 else (if nT n ≤ r ∧ c - nV n = r - nT n then 1 else 0)
    118
    119/-- **The word of the integer program** of `n` clients with `cnt t` days of type `t` and `B` days that a
    120client may go unserved: the two counts, the coefficients row by row, and the right-hand sides, `cnt r` in the row
    121of type `r` and `B` in each client row. -/
    122def ilpWord (n : ℕ) (cnt : ℕ → ℕ) (B : ℕ) : List ℕ :=
    123 [nN n, nM n] ++ (List.range (nM n * nN n)).map (fun i => coef n (i / nN n) (i % nN n))
    124 ++ (List.range (nM n)).map (fun r => if r < nT n then cnt r else B)
    125
    126/-- **The integer programs of the clients' reduction, as a parameterized problem**: the domain is the words
    127`ilpWord n cnt B` of the family and the fixed word `[1, 1, 0, 1]` of the program `0 · x = 1`; a yes-instance
    128is a word whose integer program is feasible; the parameter is the number of variables. -/
    129def ilpClients : Problem where
    130 Domain := {z | (∃ n cnt B, z = ilpWord n cnt B) ∨ z = [1, 1, 0, 1]}
    131 Yes z := (decodeILP z).Feasible
    132 param z := (decodeILP z).N
    133
    134/-- **Integer programs of the clients' family are fixed-parameter tractable** in the number of variables. -/
    135axiom ilpClients_fpt : FptDecision ilpClients
    136
    137end Lax117284.IlpClients
    138
    Show Proof
    Formalization Notes

    The family is written out here, the coefficient formula included, because this module cannot import the proofs; the proofs identify it, definition by definition, with the construction of the reduction. Column t∗2n+st * 2^n + s (tt a type, ss a subset of clients, both as numbers) has the coefficient 11 in the row of type tt and in the row of client jj for every client jj not in ss, when ss contains no two clients that tt makes conflict (indepBindepB), and is the zero column otherwise; the column 2(n∗n)∗2n+j2 ^ (n * n) * 2 ^ n + j is the slack of client jj and has a single 11, in the row of client jj. The right-hand side is cnttcnt t in the row of type tt and BB in every client row.

    The domain is the words of this family, which are the words of the integer programs that the reduction outputs, and, in addition, the fixed word [1,1,0,1][1, 1, 0, 1] of the infeasible program 0⋅x=10 · x = 1. It is needed: for n≤1n ≤ 1 every member of the family is feasible, whatever the right-hand side, so for a fairness parameter above the number of days the reduction has no infeasible word of the family to output. The word of an integer program is its two counts, then the M∗NM * N coefficients of the constraint matrix row by row, then the MM right-hand sides (the layout convention of InstSem.leanInstSem.lean's instToksinstToks); reading it back is total, missing entries being read as 00.

    The decision theorem uses the archive's shared fixed-parameter time definition, with a computable function of the number of variables and a polynomial in binary input size. The verified solver enumerates certificates in a parameter-bounded box and checks the reconstructed solutions. Its explicit bound is larger than the bound of the general integer-programming algorithm cited in the source.

    Discussion

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

    Loading discussion…