Definition 2 and §1.2 — encoded FL-MI instances with non-uniform opening costs, and partition matroids
DefinitionFacilityIncompatibilities_UniformMatroid_Supplement_NonUniformAn encoded FL-MI instance with non-uniform opening costs consists of a number of clients , a number of facilities , a rational distance for every pair of points , and a rational opening cost for every facility . Together with a matroid on the clients it determines an FL-MI instance in the sense of the mission's model (Definition 1). Its input word is the binary string consisting of the self-delimiting codes of and , the distances in row-major order, and then the costs ; its length is the input size of the polynomial-time claims. The matroid is not part of the input: algorithms query it through an independence oracle.
A matroid on the clients is a partition matroid (Definition 2: FL-MI with group constraints) if the clients are partitioned into groups , each with a bound , and a client set is independent exactly when
These are the inputs of Theorem 4. A single group is capacitated facility location with uniform capacities.
Formalization Note The groups are given by a label map from the clients to (a partition of clients has at most nonempty parts) and natural-number bounds. Being a partition matroid is a property of ; the partition is not given to the algorithm. The binary encodings (natCode, ratCode) and the independence oracle are those of the published encoding module.
import Mathlib
import Definitions.Def_FacilityIncompatibilities_UniformMatroid_Encoding
namespace FacilityIncompatibilities.UniformMatroid.Supplement
/-- **A rationally encoded FL-MI instance with non-uniform opening costs** (§1, printed p.2, and
§1.2, printed pp.3–4: "rational distances and opening costs"): `n` clients `Fin n`, `m`
facilities `Fin m`, the full rational distance table on `Fin n ⊕ Fin m`, and an opening cost
`f i` for every facility `i`. The client matroid is not part of the input: it is accessed through
the independence oracle `indepOracle` of the published encoding. -/
structure NUEncodedInstance where
/-- number of clients -/
n : ℕ
/-- number of facilities -/
m : ℕ
/-- rational distance table on clients ⊕ facilities -/
d : Fin n ⊕ Fin m → Fin n ⊕ Fin m → ℚ
/-- the opening cost of each facility -/
f : Fin m → ℚ
namespace NUEncodedInstance
/-- The real FL-MI instance of an encoded instance together with a client matroid `M`:
distances and opening costs cast to `ℝ`. -/
def toInstance (E : NUEncodedInstance) (M : Matroid (Fin E.n)) :
Instance (Fin E.n) (Fin E.m) where
d x y := (E.d x y : ℝ)
f i := (E.f i : ℝ)
M := M
/-- **The input word** of an encoded instance: `n` and `m` in self-delimiting binary, the
`(n + m)²` entries of the distance table in row-major order (points numbered by
`finSumFinEquiv`: clients `0, …, n−1`, then facilities `n, …, n+m−1`), then the opening costs
`f_0, …, f_{m−1}`, every rational written with `ratCode`. Its length is the binary input length
of the polynomial-time claims. -/
def encode (E : NUEncodedInstance) : List Bool :=
QuantumHMMR.natCode E.n ++ QuantumHMMR.natCode E.m ++
((List.finRange (E.n + E.m)).flatMap fun a => (List.finRange (E.n + E.m)).flatMap fun b =>
ratCode (E.d (finSumFinEquiv.symm a) (finSumFinEquiv.symm b))) ++
(List.finRange E.m).flatMap fun i => ratCode (E.f i)
end NUEncodedInstance
/-- **Partition matroid** (Definition 2, printed p.2 / PDF p.3: "FL-MI with group constraints"):
the clients `Fin n` are partitioned into groups by a group label `grp j`, each group `g` has a
bound `b g ≥ 0`, and a client set `X` is independent iff it contains at most `b g` clients of
every group `g`.
**Formalization Note** Groups are labelled by `Fin n`: a partition of `n` clients has at most `n`
nonempty parts, and an empty part constrains nothing, so every partition matroid is covered.
The partition is a property of `M`, not part of any algorithm's input. -/
def IsPartitionMatroid {n : ℕ} (M : Matroid (Fin n)) : Prop :=
∃ (grp : Fin n → Fin n) (b : Fin n → ℕ), ∀ X : Set (Fin n),
M.Indep X ↔ ∀ g, (X ∩ grp ⁻¹' {g}).ncard ≤ b g
end FacilityIncompatibilities.UniformMatroid.Supplement