Finite + high precision example: Error correcting codes
A constant weight error correcting code of length N
, distance D
and weight W
is a set of binary words of length N
, each of which has exactly W
ones, where every pair of words differs in at least D
coordinates. Here we bound the maximum cardinality of such a code, and solve the SDP to a high precision.
using FlagSOS
Setting up the model
N = 11 # length
W = 3 # weight
D = 4; # distance
The type ConstantWeightCode{W,D} models all codes with constant weight W
and minimum distance D
, independent of its length N
.
const WDCode = ConstantWeightCode{W,D}
ConstantWeightCode{3, 4}
We start by creating an empty FlagModel
for WDCode
s of length N
. Since N
is finite, we need Rational{Int}
coefficients.
m = FlagModel{WDCode,N,Rational{Int}}();
We want to maximize the cardinality of the code, i.e. the density of the subcode containing just one word of weight W
.
e = WDCode(ones(Bool, 1, W))
m.objective = -1 * e
-1 ConstantWeightCode{3, 4}(Bool[1 1 1])
Initializing the Razborov hierarchy
We chose to work with the Razborov hierarchy at level 6
, which is based on densities of subcodes fully contained in lvl
vertices of the code. This is the same hierarchy Flagmatic uses.
lvl = 6
rM = addRazborovBlock!(m, lvl)
modelBlockSizes(rM)
Dict{ConstantWeightCode{3, 4}, Int64} with 10 entries:
ConstantWeightCode{3, 4}(0×6 BitMatrix) => 1
ConstantWeightCode{3, 4}(Bool[0 0 … 0 1; 1 1 … 0 1]) => 1
ConstantWeightCode{3, 4}(Bool[0 0 … 1 1; 1 1 … 0 0]) => 1
ConstantWeightCode{3, 4}(0×4 BitMatrix) => 10
ConstantWeightCode{3, 4}(0×0 BitMatrix) => 2
ConstantWeightCode{3, 4}(Bool[1 1 … 0 0]) => 1
ConstantWeightCode{3, 4}(Bool[0 1 … 1 0; 0 1 … 0 1; 1 0 … 0 1; 1 0 … 1 … => 1
ConstantWeightCode{3, 4}(0×2 BitMatrix) => 4
ConstantWeightCode{3, 4}(Bool[1 1 1 0]) => 4
ConstantWeightCode{3, 4}(Bool[0 0 … 1 0; 0 1 … 0 1; 1 0 … 1 1]) => 1
We still need to compute the coefficients of the actual optimization problem
computeSDP!(m)
1-element Vector{Dict{ConstantWeightCode{3, 4}, Dict{ConstantWeightCode{3, 4}, SparseArrays.SparseMatrixCSC{Rational{Int64}, Int64}}}}:
Dict(ConstantWeightCode{3, 4}(Bool[0 0 … 1 1; 1 1 … 0 0]) => Dict(ConstantWeightCode{3, 4}(0×6 BitMatrix) => sparse([1], [1], Rational{Int64}[10], 1, 1), ConstantWeightCode{3, 4}(Bool[0 0 … 1 1; 1 1 … 0 0]) => sparse([1], [1], Rational{Int64}[1], 1, 1), ConstantWeightCode{3, 4}(0×4 BitMatrix) => sparse([4, 3, 6, 5, 9, 8], [3, 4, 5, 6, 8, 9], Rational{Int64}[6//7, 6//7, 6//7, 6//7, 6//7, 6//7], 10, 10), ConstantWeightCode{3, 4}(0×0 BitMatrix) => sparse([2], [2], Rational{Int64}[56//165], 2, 2), ConstantWeightCode{3, 4}(Bool[1 1 … 0 0]) => sparse([1], [1], Rational{Int64}[-1], 1, 1), ConstantWeightCode{3, 4}(0×2 BitMatrix) => sparse([3, 2], [2, 3], Rational{Int64}[7//12, 7//12], 4, 4)), ConstantWeightCode{3, 4}(Bool[1 1 1]) => Dict(ConstantWeightCode{3, 4}(0×6 BitMatrix) => sparse([1], [1], Rational{Int64}[-20], 1, 1), ConstantWeightCode{3, 4}(0×4 BitMatrix) => sparse([3, 7, 4, 7, 5, 7, 6, 7, 3, 4, 5, 6, 7, 8, 9, 7, 8, 7, 9], [3, 3, 4, 4, 5, 5, 6, 6, 7, 7, 7, 7, 7, 7, 7, 8, 8, 9, 9], Rational{Int64}[1//7, 1, 1//7, 1, 1//7, 1, 1//7, 1, 1, 1, 1, 1, -4, 1, 1, 1, 1//7, 1, 1//7], 10, 10), ConstantWeightCode{3, 4}(0×0 BitMatrix) => sparse([2, 1, 2], [1, 2, 2], Rational{Int64}[1, 1, 1//165], 2, 2), ConstantWeightCode{3, 4}(Bool[1 1 … 0 0]) => sparse([1], [1], Rational{Int64}[1], 1, 1), ConstantWeightCode{3, 4}(0×2 BitMatrix) => sparse([1, 4, 2, 4, 3, 4, 1, 2, 3], [1, 1, 2, 2, 3, 3, 4, 4, 4], Rational{Int64}[1//9, 1, 1//36, 1, 1//36, 1, 1, 1, 1], 4, 4), ConstantWeightCode{3, 4}(Bool[1 1 1 0]) => sparse([3], [3], Rational{Int64}[1], 4, 4)), ConstantWeightCode{3, 4}(0×0 BitMatrix) => Dict(ConstantWeightCode{3, 4}(0×6 BitMatrix) => sparse([1], [1], Rational{Int64}[1], 1, 1), ConstantWeightCode{3, 4}(0×4 BitMatrix) => sparse([7], [7], Rational{Int64}[1], 10, 10), ConstantWeightCode{3, 4}(0×0 BitMatrix) => sparse([1], [1], Rational{Int64}[1], 2, 2), ConstantWeightCode{3, 4}(0×2 BitMatrix) => sparse([4], [4], Rational{Int64}[1], 4, 4)), ConstantWeightCode{3, 4}(Bool[0 0 … 1 1; 1 1 … 0 1]) => Dict(ConstantWeightCode{3, 4}(0×6 BitMatrix) => sparse([1], [1], Rational{Int64}[90], 1, 1), ConstantWeightCode{3, 4}(Bool[0 0 … 0 1; 1 1 … 0 1]) => sparse([1], [1], Rational{Int64}[1], 1, 1), ConstantWeightCode{3, 4}(0×4 BitMatrix) => sparse([1, 7, 8, 9, 2, 5, 6, 7, 3, 4 … 4, 5, 6, 7, 8, 9, 3, 4, 7, 10], [1, 1, 1, 1, 2, 2, 2, 2, 3, 3 … 9, 9, 9, 9, 9, 9, 10, 10, 10, 10], Rational{Int64}[1//7, 1, 1//7, 1//7, 1//7, 1//7, 1//7, 1, -2//7, 1//7 … 6//7, 6//7, 6//7, -2, 1//7, -2//7, 1//7, 1//7, 1, 1//7], 10, 10), ConstantWeightCode{3, 4}(0×0 BitMatrix) => sparse([2], [2], Rational{Int64}[28//55], 2, 2), ConstantWeightCode{3, 4}(Bool[1 1 … 0 0]) => sparse([1], [1], Rational{Int64}[-9], 1, 1), ConstantWeightCode{3, 4}(0×2 BitMatrix) => sparse([2, 3, 1, 2, 3, 1, 2, 3], [1, 1, 2, 2, 2, 3, 3, 3], Rational{Int64}[7//9, 7//9, 7//9, 7//12, 7//18, 7//9, 7//18, 7//12], 4, 4), ConstantWeightCode{3, 4}(Bool[1 1 1 0]) => sparse([1, 3, 2, 3, 1, 2, 4, 3, 4], [1, 1, 2, 2, 3, 3, 3, 4, 4], Rational{Int64}[1//7, 1, 1//7, 1, 1, 1, 1, 1, 1//7], 4, 4)), ConstantWeightCode{3, 4}(Bool[0 1 … 1 0; 0 1 … 0 1; 1 0 … 0 1; 1 0 … 1 0]) => Dict(ConstantWeightCode{3, 4}(0×6 BitMatrix) => sparse([1], [1], Rational{Int64}[30], 1, 1), ConstantWeightCode{3, 4}(Bool[0 0 … 0 1; 1 1 … 0 1]) => sparse([1], [1], Rational{Int64}[2], 1, 1), ConstantWeightCode{3, 4}(0×4 BitMatrix) => sparse([2, 10, 1, 10, 1, 2], [1, 1, 2, 2, 10, 10], Rational{Int64}[6//7, 6//7, 6//7, 6//7, 6//7, 6//7], 10, 10), ConstantWeightCode{3, 4}(Bool[1 1 … 0 0]) => sparse([1], [1], Rational{Int64}[-6], 1, 1), ConstantWeightCode{3, 4}(Bool[0 1 … 1 0; 0 1 … 0 1; 1 0 … 0 1; 1 0 … 1 0]) => sparse([1], [1], Rational{Int64}[1], 1, 1), ConstantWeightCode{3, 4}(Bool[0 0 … 1 0; 0 1 … 0 1; 1 0 … 1 1]) => sparse([1], [1], Rational{Int64}[-1], 1, 1)), ConstantWeightCode{3, 4}(Bool[0 0 … 1 0; 0 1 … 0 1; 1 0 … 1 1]) => Dict(ConstantWeightCode{3, 4}(0×6 BitMatrix) => sparse([1], [1], Rational{Int64}[-120], 1, 1), ConstantWeightCode{3, 4}(Bool[0 0 … 0 1; 1 1 … 0 1]) => sparse([1], [1], Rational{Int64}[-4], 1, 1), ConstantWeightCode{3, 4}(0×4 BitMatrix) => sparse([3, 4, 5, 6, 3, 4, 8, 9, 1, 2 … 2, 3, 4, 5, 6, 10, 5, 6, 8, 9], [1, 1, 1, 1, 2, 2, 2, 2, 3, 3 … 9, 9, 9, 9, 9, 9, 10, 10, 10, 10], Rational{Int64}[6//7, 6//7, 6//7, 6//7, 6//7, 6//7, 6//7, 6//7, 6//7, 6//7 … 6//7, -6//7, -6//7, -6//7, -6//7, 6//7, 6//7, 6//7, 6//7, 6//7], 10, 10), ConstantWeightCode{3, 4}(Bool[1 1 … 0 0]) => sparse([1], [1], Rational{Int64}[18], 1, 1), ConstantWeightCode{3, 4}(Bool[1 1 1 0]) => sparse([2, 4, 1, 4, 1, 2], [1, 1, 2, 2, 4, 4], Rational{Int64}[6//7, 6//7, 6//7, 6//7, 6//7, 6//7], 4, 4), ConstantWeightCode{3, 4}(Bool[0 0 … 1 0; 0 1 … 0 1; 1 0 … 1 1]) => sparse([1], [1], Rational{Int64}[1], 1, 1)))
Solving the SDP
Now we can solve it to a high precision
using Hypatia, JuMP, GenericLinearAlgebra
setprecision(256)
M = buildJuMPModel(m, Dict(), GenericModel{BigFloat}());
set_optimizer(M.model, Hypatia.Optimizer{BigFloat})
optimize!(M.model)
iter p_obj d_obj | abs_gap x_feas z_feas | tau kap mu | dir_res prox step alpha
0 3.4643e+00 1.2498e-01 | 2.60e+01 5.73e-01 8.43e-01 | 1.00e+00 1.00e+00 1.00e+00 |
1 6.5540e-01 1.2115e-01 | 3.95e+00 8.30e-02 1.22e-01 | 1.03e+00 9.81e-02 1.50e-01 | 3.3e-76 6.4e-01 co-a 8.50e-01
2 3.0434e-01 1.1255e-01 | 1.52e+00 3.18e-02 4.68e-02 | 1.08e+00 5.34e-02 5.85e-02 | 7.7e-77 7.4e-01 co-a 6.00e-01
3 1.4436e-01 1.0880e-01 | 3.11e-01 4.95e-03 7.27e-03 | 1.39e+00 2.65e-03 1.17e-02 | 1.3e-76 7.5e-01 co-a 8.00e-01
4 1.2183e-01 1.1351e-01 | 8.79e-02 1.24e-03 1.82e-03 | 1.66e+00 1.79e-03 3.37e-03 | 9.5e-76 5.1e-01 co-a 7.00e-01
5 1.1514e-01 1.1282e-01 | 2.57e-02 3.47e-04 5.11e-04 | 1.78e+00 5.61e-04 9.89e-04 | 8.1e-76 8.7e-01 co-a 7.00e-01
6 1.1233e-01 1.1159e-01 | 7.27e-03 1.13e-04 1.67e-04 | 1.64e+00 1.90e-04 2.81e-04 | 2.2e-75 9.8e-01 co-a 7.00e-01
7 1.1130e-01 1.1119e-01 | 1.07e-03 1.73e-05 2.54e-05 | 1.61e+00 2.61e-05 4.10e-05 | 1.6e-75 8.8e-01 co-a 8.50e-01
8 1.1114e-01 1.1113e-01 | 1.58e-04 2.61e-06 3.84e-06 | 1.60e+00 3.38e-06 6.06e-06 | 2.0e-74 7.6e-01 co-a 8.50e-01
9 1.1111e-01 1.1111e-01 | 1.56e-05 2.66e-07 3.91e-07 | 1.57e+00 3.26e-07 5.96e-07 | 1.8e-73 7.7e-01 co-a 9.00e-01
10 1.1111e-01 1.1111e-01 | 1.52e-06 2.74e-08 4.03e-08 | 1.53e+00 3.10e-08 5.81e-08 | 1.3e-72 8.4e-01 co-a 9.00e-01
11 1.1111e-01 1.1111e-01 | 2.18e-07 4.30e-09 6.32e-09 | 1.46e+00 5.29e-09 8.36e-09 | 1.2e-71 6.3e-01 co-a 8.50e-01
12 1.1111e-01 1.1111e-01 | 3.25e-08 6.48e-10 9.54e-10 | 1.45e+00 7.10e-10 1.24e-09 | 9.7e-71 8.0e-01 co-a 8.50e-01
13 1.1111e-01 1.1111e-01 | 6.19e-09 1.36e-10 2.00e-10 | 1.38e+00 1.66e-10 2.38e-10 | 8.7e-70 6.9e-01 co-a 8.00e-01
14 1.1111e-01 1.1111e-01 | 9.32e-10 2.03e-11 2.99e-11 | 1.39e+00 2.13e-11 3.56e-11 | 1.3e-69 6.3e-01 co-a 8.50e-01
15 1.1111e-01 1.1111e-01 | 1.34e-10 3.19e-12 4.70e-12 | 1.32e+00 3.53e-12 5.12e-12 | 5.0e-68 7.0e-01 co-a 8.50e-01
16 1.1111e-01 1.1111e-01 | 2.61e-11 6.52e-13 9.60e-13 | 1.30e+00 6.99e-13 1.00e-12 | 7.9e-68 8.4e-01 co-a 8.00e-01
17 1.1111e-01 1.1111e-01 | 5.06e-12 1.34e-13 1.98e-13 | 1.26e+00 1.47e-13 1.94e-13 | 6.9e-67 7.4e-01 co-a 8.00e-01
18 1.1111e-01 1.1111e-01 | 7.56e-13 2.03e-14 2.98e-14 | 1.25e+00 1.92e-14 2.89e-14 | 1.3e-66 8.4e-01 co-a 8.50e-01
19 1.1111e-01 1.1111e-01 | 1.43e-13 4.30e-15 6.33e-15 | 1.18e+00 4.59e-15 5.48e-15 | 2.9e-65 7.3e-01 co-a 8.00e-01
20 1.1111e-01 1.1111e-01 | 4.21e-14 1.30e-15 1.92e-15 | 1.17e+00 1.34e-15 1.62e-15 | 4.9e-65 7.6e-01 co-a 7.00e-01
21 1.1111e-01 1.1111e-01 | 6.27e-15 1.97e-16 2.89e-16 | 1.16e+00 1.85e-16 2.40e-16 | 5.1e-64 9.7e-01 co-a 8.50e-01
22 1.1111e-01 1.1111e-01 | 1.21e-15 4.08e-17 6.00e-17 | 1.12e+00 3.85e-17 4.65e-17 | 1.1e-63 9.6e-01 co-a 8.00e-01
23 1.1111e-01 1.1111e-01 | 2.33e-16 8.51e-18 1.25e-17 | 1.07e+00 8.08e-18 8.94e-18 | 2.0e-62 7.5e-01 co-a 8.00e-01
24 1.1111e-01 1.1111e-01 | 4.61e-17 1.72e-18 2.52e-18 | 1.06e+00 1.48e-18 1.77e-18 | 1.6e-62 9.2e-01 co-a 8.00e-01
25 1.1111e-01 1.1111e-01 | 8.81e-18 3.60e-19 5.29e-19 | 1.02e+00 3.26e-19 3.38e-19 | 4.4e-61 7.5e-01 co-a 8.00e-01
26 1.1111e-01 1.1111e-01 | 1.75e-18 7.23e-20 1.06e-19 | 1.01e+00 5.91e-20 6.71e-20 | 2.5e-61 9.0e-01 co-a 8.00e-01
27 1.1111e-01 1.1111e-01 | 3.35e-19 1.51e-20 2.22e-20 | 9.66e-01 1.30e-20 1.29e-20 | 4.5e-60 7.6e-01 co-a 8.00e-01
28 1.1111e-01 1.1111e-01 | 6.65e-20 3.04e-21 4.48e-21 | 9.60e-01 2.37e-21 2.55e-21 | 9.9e-60 9.0e-01 co-a 8.00e-01
29 1.1111e-01 1.1111e-01 | 1.27e-20 6.37e-22 9.37e-22 | 9.18e-01 5.20e-22 4.89e-22 | 4.3e-58 7.6e-01 co-a 8.00e-01
30 1.1111e-01 1.1111e-01 | 2.53e-21 1.28e-22 1.89e-22 | 9.12e-01 9.48e-23 9.68e-23 | 1.0e-58 9.0e-01 co-a 8.00e-01
31 1.1111e-01 1.1111e-01 | 4.83e-22 2.68e-23 3.95e-23 | 8.71e-01 2.08e-23 1.86e-23 | 9.6e-57 7.6e-01 co-a 8.00e-01
32 1.1111e-01 1.1111e-01 | 9.59e-23 5.40e-24 7.94e-24 | 8.66e-01 3.79e-24 3.67e-24 | 4.0e-57 9.0e-01 co-a 8.00e-01
33 1.1111e-01 1.1111e-01 | 1.83e-23 1.13e-24 1.66e-24 | 8.27e-01 8.33e-25 7.05e-25 | 1.1e-55 7.6e-01 co-a 8.00e-01
34 1.1111e-01 1.1111e-01 | 3.64e-24 2.27e-25 3.35e-25 | 8.22e-01 1.52e-25 1.40e-25 | 8.7e-56 9.0e-01 co-a 8.00e-01
35 1.1111e-01 1.1111e-01 | 6.97e-25 4.76e-26 7.00e-26 | 7.86e-01 3.33e-26 2.68e-26 | 3.6e-54 7.6e-01 co-a 8.00e-01
36 1.1111e-01 1.1111e-01 | 1.38e-25 9.58e-27 1.41e-26 | 7.81e-01 6.06e-27 5.30e-27 | 1.6e-54 9.0e-01 co-a 8.00e-01
37 1.1111e-01 1.1111e-01 | 2.65e-26 2.01e-27 2.95e-27 | 7.46e-01 1.33e-27 1.02e-27 | 6.6e-53 7.6e-01 co-a 8.00e-01
38 1.1111e-01 1.1111e-01 | 5.25e-27 4.04e-28 5.94e-28 | 7.41e-01 2.43e-28 2.01e-28 | 4.5e-53 9.0e-01 co-a 8.00e-01
39 1.1111e-01 1.1111e-01 | 1.00e-27 8.45e-29 1.24e-28 | 7.08e-01 5.33e-29 3.86e-29 | 7.9e-52 7.6e-01 co-a 8.00e-01
40 1.1111e-01 1.1111e-01 | 2.00e-28 1.70e-29 2.50e-29 | 7.04e-01 9.70e-30 7.64e-30 | 1.7e-51 9.0e-01 co-a 8.00e-01
41 1.1111e-01 1.1111e-01 | 3.82e-29 3.56e-30 5.24e-30 | 6.72e-01 2.13e-30 1.47e-30 | 1.7e-50 7.6e-01 co-a 8.00e-01
42 1.1111e-01 1.1111e-01 | 7.58e-30 7.17e-31 1.05e-30 | 6.68e-01 3.88e-31 2.90e-31 | 2.6e-50 9.0e-01 co-a 8.00e-01
43 1.1111e-01 1.1111e-01 | 1.45e-30 1.50e-31 2.21e-31 | 6.38e-01 8.53e-32 5.57e-32 | 3.1e-49 7.6e-01 co-a 8.00e-01
44 1.1111e-01 1.1111e-01 | 2.88e-31 3.02e-32 4.44e-32 | 6.34e-01 1.55e-32 1.10e-32 | 5.3e-49 9.0e-01 co-a 8.00e-01
45 1.1111e-01 1.1111e-01 | 5.50e-32 6.32e-33 9.30e-33 | 6.06e-01 3.41e-33 2.11e-33 | 1.3e-47 7.6e-01 co-a 8.00e-01
optimal solution found; terminating
status is Optimal after 45 iterations and 7.676 seconds
termination_status(M.model)
OPTIMAL::TerminationStatusCode = 1
We need to turn the density of the code to its cardinality
objective_value(M.model) * binomial(N, W)
18.33333333333333333333333333334524332277557982701169163744823941703460702722969
This page was generated using Literate.jl.