Submitter | Variables | Constraints | Density | Status | Group | Objective | MPS File |
---|---|---|---|---|---|---|---|
Sascha Kurz | 6143 | 2065 | 4.2502e-02 | hard | 8div | Infeasible | 8div-n59k10.mps.gz |
Projective binary 8-divisible linear block codes A linear block code is called 8-divisible if the weights of its codewords are divisible by 8. It is called projective if there are no duplicate columns in the generator matrix. The possible lengths of 8-divisible linear block codes have been classified except for length n=59, where it is undecided whether such a linear code exists. The possible dimensions satisfy \(10 \le k \le 20\). Instance 8div_n59_kXX contains the corresponding feasibility problem. Projective binary 8-divisible linear block codes occur as hole configurations of so-called partial solid spreads in finite geometry. Binary 4-divisible linear block codes have applications in physics.
Detailed explanation of the following tables can be found here.
Original | Presolved | |
---|---|---|
Variables | 6143 | 6133 |
Constraints | 2065 | 2055 |
Binaries | 6138 | 6128 |
Integers | 5 | 5 |
Continuous | 0 | 0 |
Implicit Integers | 0 | 0 |
Fixed Variables | 0 | 0 |
Nonzero Density | 0.0425020 | 0.0423715 |
Nonzeroes | 539151 | 534021 |
Original | Presolved | |
---|---|---|
Total | 2068 | 2058 |
Empty | 0 | 0 |
Free | 0 | 0 |
Singleton | 10 | 0 |
Aggregations | 0 | 0 |
Precedence | 0 | 0 |
Variable Bound | 0 | 0 |
Set Partitioning | 1023 | 1023 |
Set Packing | 0 | 0 |
Set Covering | 0 | 0 |
Cardinality | 1 | 1 |
Invariant Knapsack | 0 | 0 |
Equation Knapsack | 1023 | 1023 |
Bin Packing | 0 | 0 |
Knapsack | 0 | 0 |
Integer Knapsack | 3 | 3 |
Mixed Binary | 0 | 0 |
General Linear | 8 | 8 |
Indicator | 0 | 0 |
Available nonzero structure and decomposition information. Further information can be found here.
Decomposed structure of original problem (dec-file)
Decomposed structure after trivial presolving (dec-file)
value | min | median | mean | max | |
---|---|---|---|---|---|
Components | 2.91169 | ||||
Constraint % | 0.0486618 | 0.0737988 | 0.0486618 | 20.4380 | |
Variable % | 0.0813935 | 0.1225000 | 0.0813935 | 33.5829 | |
Score | 0.53250 |
No solution available for 8div-n59k10 .
The following instances are most similar to 8div-n59k10 in the collection. This similarity analysis is based on 100 scaled instance features describing properties of the variables, objective function, bounds, constraints, and right hand sides.
@incollection{ubt_eref40887,
author = {Daniel Heinlein and Thomas Honold and Michael Kiermaier and Sascha Kurz and Alfred Wassermann},
booktitle = {The Tenth International Workshop on Coding and Cryptography 2017 : WCC Proceedings},
address = {Saint-Petersburg},
month = {September},
title = {Projective divisible binary codes},
year = {2017},
url = {https://eref.uni-bayreuth.de/40887/},
keywords = {divisible codes; projective codes; partial spreads}
}
@article{heinlein2017classifying,
title = {Classifying optimal binary subspace codes of length 8, constant dimension 4 and minimum distance 6},
author = {Heinlein, Daniel and Honold, Thomas and Kiermaier, Michael and Kurz, Sascha and Wassermann, Alfred},
journal = {Designs, Codes and Cryptography},
note = {arXiv preprint arXiv:1711.06624},
year = {to appear},
doi = {10.1007/s10623-018-0544-8}
}