Submitter | Variables | Constraints | Density | Status | Group | Objective | MPS File |
---|---|---|---|---|---|---|---|

Sascha Kurz | 24575 | 8211 | 4.18664e-02 | hard | 8div | Infeasible | 8div-n59k12.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 | 24575 | 24563 |

Constraints | 8211 | 8199 |

Binaries | 24570 | 24558 |

Integers | 5 | 5 |

Continuous | 0 | 0 |

Implicit Integers | 0 | 0 |

Fixed Variables | 0 | 0 |

Nonzero Density | 0.0418664 | 0.0418260 |

Nonzeroes | 8448020 | 8423430 |

Original | Presolved | |
---|---|---|

Total | 8214 | 8202 |

Empty | 0 | 0 |

Free | 0 | 0 |

Singleton | 12 | 0 |

Aggregations | 0 | 0 |

Precedence | 0 | 0 |

Variable Bound | 0 | 0 |

Set Partitioning | 4095 | 4095 |

Set Packing | 0 | 0 |

Set Covering | 0 | 0 |

Cardinality | 1 | 1 |

Invariant Knapsack | 0 | 0 |

Equation Knapsack | 4095 | 4095 |

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 | 3.519303 | ||||

Constraint % | 0.0121966 | 0.0180458 | 0.0121966 | 19.3194 | |

Variable % | 0.0203459 | 0.0302412 | 0.0203459 | 32.7243 | |

Score | 0.533111 |

No solution available for 8div-n59k12 .

The following instances are most similar to 8div-n59k12 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.

Instance | Status | Variables | Binaries | Integers | Continuous | Constraints | Nonz. | Submitter | Group | Objective | Tags |
---|---|---|---|---|---|---|---|---|---|---|---|

8div-n59k11 | hard | 12287 | 12282 | 5 | 0 | 4114 | 2126860 | Sascha Kurz | 8div | Infeasible | infeasible set_partitioning cardinality equation_knapsack integer_knapsack general_linear |

8div-n59k10 | hard | 6143 | 6138 | 5 | 0 | 2065 | 539151 | Sascha Kurz | 8div | Infeasible | infeasible set_partitioning cardinality equation_knapsack integer_knapsack general_linear |

neos-3045796-mogo | easy | 11016 | 11016 | 0 | 0 | 2226 | 44442 | Jeff Linderoth | neos-pseudoapplication-22 | -175 | binary decomposition set_partitioning set_packing set_covering invariant_knapsack equation_knapsack |

neos-952987 | hard | 31329 | 31329 | 0 | 0 | 354 | 90384 | NEOS Server Submission | neos-pseudoapplication-22 | Infeasible | infeasible binary set_covering equation_knapsack knapsack |

neos-4413714-turia | easy | 190402 | 190201 | 0 | 201 | 2303 | 761756 | Jeff Linderoth | neos-pseudoapplication-67 | 45.3701670199998 | benchmark benchmark_suitable set_partitioning binpacking mixed_binary |

```
@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}
}
```

Last Update Aug 28, 2019 by Gregor Hendel

generated with R Markdown

© 2019 by Konrad-Zuse-Zentrum für Informationstechnik Berlin (ZIB)

Imprint