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 FlagSOSSetting up the model
N = 11 # length
W = 3 # weight
D = 4; # distanceThe 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 WDCodes 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]) => 1We 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 4.87e-01 8.43e-01 | 1.00e+00 1.00e+00 1.00e+00 |
1 6.5540e-01 1.2115e-01 | 3.95e+00 7.06e-02 1.22e-01 | 1.03e+00 9.81e-02 1.50e-01 | 1.6e-76 6.4e-01 co-a 8.50e-01
2 3.0434e-01 1.1255e-01 | 1.52e+00 2.71e-02 4.68e-02 | 1.08e+00 5.34e-02 5.85e-02 | 1.4e-76 7.4e-01 co-a 6.00e-01
3 1.4436e-01 1.0880e-01 | 3.11e-01 4.20e-03 7.27e-03 | 1.39e+00 2.65e-03 1.17e-02 | 2.2e-76 7.5e-01 co-a 8.00e-01
4 1.2183e-01 1.1351e-01 | 8.79e-02 1.05e-03 1.82e-03 | 1.66e+00 1.79e-03 3.37e-03 | 1.0e-74 5.1e-01 co-a 7.00e-01
5 1.1514e-01 1.1282e-01 | 2.57e-02 2.95e-04 5.11e-04 | 1.78e+00 5.61e-04 9.89e-04 | 1.0e-75 8.7e-01 co-a 7.00e-01
6 1.1233e-01 1.1159e-01 | 7.27e-03 9.63e-05 1.67e-04 | 1.64e+00 1.90e-04 2.81e-04 | 5.0e-75 9.8e-01 co-a 7.00e-01
7 1.1130e-01 1.1119e-01 | 1.07e-03 1.47e-05 2.54e-05 | 1.61e+00 2.61e-05 4.10e-05 | 1.8e-75 8.8e-01 co-a 8.50e-01
8 1.1114e-01 1.1113e-01 | 1.58e-04 2.22e-06 3.84e-06 | 1.60e+00 3.38e-06 6.06e-06 | 1.1e-74 7.6e-01 co-a 8.50e-01
9 1.1111e-01 1.1111e-01 | 1.56e-05 2.26e-07 3.91e-07 | 1.57e+00 3.26e-07 5.96e-07 | 1.6e-73 7.7e-01 co-a 9.00e-01
10 1.1111e-01 1.1111e-01 | 1.52e-06 2.33e-08 4.03e-08 | 1.53e+00 3.10e-08 5.81e-08 | 1.8e-72 8.4e-01 co-a 9.00e-01
11 1.1111e-01 1.1111e-01 | 2.18e-07 3.65e-09 6.32e-09 | 1.46e+00 5.29e-09 8.36e-09 | 2.0e-71 6.3e-01 co-a 8.50e-01
12 1.1111e-01 1.1111e-01 | 3.25e-08 5.51e-10 9.54e-10 | 1.45e+00 7.10e-10 1.24e-09 | 8.1e-71 8.0e-01 co-a 8.50e-01
13 1.1111e-01 1.1111e-01 | 6.19e-09 1.16e-10 2.00e-10 | 1.38e+00 1.66e-10 2.38e-10 | 8.9e-70 6.9e-01 co-a 8.00e-01
14 1.1111e-01 1.1111e-01 | 9.32e-10 1.73e-11 2.99e-11 | 1.39e+00 2.13e-11 3.56e-11 | 9.3e-70 6.3e-01 co-a 8.50e-01
15 1.1111e-01 1.1111e-01 | 1.34e-10 2.71e-12 4.70e-12 | 1.32e+00 3.53e-12 5.12e-12 | 9.1e-68 7.0e-01 co-a 8.50e-01
16 1.1111e-01 1.1111e-01 | 2.61e-11 5.55e-13 9.60e-13 | 1.30e+00 6.99e-13 1.00e-12 | 1.2e-67 8.4e-01 co-a 8.00e-01
17 1.1111e-01 1.1111e-01 | 5.06e-12 1.14e-13 1.98e-13 | 1.26e+00 1.47e-13 1.94e-13 | 1.1e-66 7.4e-01 co-a 8.00e-01
18 1.1111e-01 1.1111e-01 | 7.56e-13 1.72e-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 3.66e-15 6.33e-15 | 1.18e+00 4.59e-15 5.48e-15 | 3.1e-65 7.3e-01 co-a 8.00e-01
20 1.1111e-01 1.1111e-01 | 4.21e-14 1.11e-15 1.92e-15 | 1.17e+00 1.34e-15 1.62e-15 | 2.5e-65 7.6e-01 co-a 7.00e-01
21 1.1111e-01 1.1111e-01 | 6.27e-15 1.67e-16 2.89e-16 | 1.16e+00 1.85e-16 2.40e-16 | 3.4e-64 9.7e-01 co-a 8.50e-01
22 1.1111e-01 1.1111e-01 | 1.21e-15 3.47e-17 6.00e-17 | 1.12e+00 3.85e-17 4.65e-17 | 1.6e-63 9.6e-01 co-a 8.00e-01
23 1.1111e-01 1.1111e-01 | 2.33e-16 7.23e-18 1.25e-17 | 1.07e+00 8.08e-18 8.94e-18 | 2.1e-62 7.5e-01 co-a 8.00e-01
24 1.1111e-01 1.1111e-01 | 4.61e-17 1.46e-18 2.52e-18 | 1.06e+00 1.48e-18 1.77e-18 | 1.5e-62 9.2e-01 co-a 8.00e-01
25 1.1111e-01 1.1111e-01 | 8.81e-18 3.06e-19 5.29e-19 | 1.02e+00 3.26e-19 3.38e-19 | 3.3e-61 7.5e-01 co-a 8.00e-01
26 1.1111e-01 1.1111e-01 | 1.75e-18 6.14e-20 1.06e-19 | 1.01e+00 5.91e-20 6.71e-20 | 2.0e-61 9.0e-01 co-a 8.00e-01
27 1.1111e-01 1.1111e-01 | 3.35e-19 1.29e-20 2.22e-20 | 9.66e-01 1.30e-20 1.29e-20 | 1.6e-59 7.6e-01 co-a 8.00e-01
28 1.1111e-01 1.1111e-01 | 6.65e-20 2.59e-21 4.48e-21 | 9.60e-01 2.37e-21 2.55e-21 | 5.7e-60 9.0e-01 co-a 8.00e-01
29 1.1111e-01 1.1111e-01 | 1.27e-20 5.41e-22 9.37e-22 | 9.18e-01 5.20e-22 4.89e-22 | 2.8e-58 7.6e-01 co-a 8.00e-01
30 1.1111e-01 1.1111e-01 | 2.53e-21 1.09e-22 1.89e-22 | 9.12e-01 9.48e-23 9.68e-23 | 1.4e-58 9.0e-01 co-a 8.00e-01
31 1.1111e-01 1.1111e-01 | 4.83e-22 2.28e-23 3.95e-23 | 8.71e-01 2.08e-23 1.86e-23 | 1.2e-56 7.6e-01 co-a 8.00e-01
32 1.1111e-01 1.1111e-01 | 9.59e-23 4.59e-24 7.94e-24 | 8.66e-01 3.79e-24 3.67e-24 | 5.0e-57 9.0e-01 co-a 8.00e-01
33 1.1111e-01 1.1111e-01 | 1.83e-23 9.61e-25 1.66e-24 | 8.27e-01 8.33e-25 7.05e-25 | 1.5e-55 7.6e-01 co-a 8.00e-01
34 1.1111e-01 1.1111e-01 | 3.64e-24 1.93e-25 3.35e-25 | 8.22e-01 1.52e-25 1.40e-25 | 7.2e-56 9.0e-01 co-a 8.00e-01
35 1.1111e-01 1.1111e-01 | 6.97e-25 4.05e-26 7.00e-26 | 7.86e-01 3.33e-26 2.68e-26 | 1.9e-54 7.6e-01 co-a 8.00e-01
36 1.1111e-01 1.1111e-01 | 1.38e-25 8.15e-27 1.41e-26 | 7.81e-01 6.06e-27 5.30e-27 | 2.7e-54 9.0e-01 co-a 8.00e-01
37 1.1111e-01 1.1111e-01 | 2.65e-26 1.71e-27 2.95e-27 | 7.46e-01 1.33e-27 1.02e-27 | 4.2e-53 7.6e-01 co-a 8.00e-01
38 1.1111e-01 1.1111e-01 | 5.25e-27 3.43e-28 5.94e-28 | 7.41e-01 2.43e-28 2.01e-28 | 3.8e-53 9.0e-01 co-a 8.00e-01
39 1.1111e-01 1.1111e-01 | 1.00e-27 7.18e-29 1.24e-28 | 7.08e-01 5.33e-29 3.86e-29 | 7.5e-52 7.6e-01 co-a 8.00e-01
40 1.1111e-01 1.1111e-01 | 2.00e-28 1.45e-29 2.50e-29 | 7.04e-01 9.70e-30 7.64e-30 | 9.6e-52 9.0e-01 co-a 8.00e-01
41 1.1111e-01 1.1111e-01 | 3.82e-29 3.03e-30 5.24e-30 | 6.72e-01 2.13e-30 1.47e-30 | 1.5e-50 7.6e-01 co-a 8.00e-01
42 1.1111e-01 1.1111e-01 | 7.58e-30 6.09e-31 1.05e-30 | 6.68e-01 3.88e-31 2.90e-31 | 2.0e-50 9.0e-01 co-a 8.00e-01
43 1.1111e-01 1.1111e-01 | 1.45e-30 1.28e-31 2.21e-31 | 6.38e-01 8.53e-32 5.57e-32 | 5.1e-49 7.6e-01 co-a 8.00e-01
44 1.1111e-01 1.1111e-01 | 2.88e-31 2.57e-32 4.44e-32 | 6.34e-01 1.55e-32 1.10e-32 | 6.0e-49 9.0e-01 co-a 8.00e-01
45 1.1111e-01 1.1111e-01 | 5.50e-32 5.37e-33 9.30e-33 | 6.06e-01 3.41e-33 2.11e-33 | 1.1e-47 7.6e-01 co-a 8.00e-01
optimal solution found; terminating
status is Optimal after 45 iterations and 7.638 secondstermination_status(M.model)OPTIMAL::TerminationStatusCode = 1We need to turn the density of the code to its cardinality
objective_value(M.model) * binomial(N, W)18.33333333333333333333333333334524332277557982688488519358065744265332493900891This page was generated using Literate.jl.