8div-n59k12

infeasible set_partitioning cardinality equation_knapsack integer_knapsack general_linear

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.

Location of instance in collection

Instance Statistics

Detailed explanation of the following tables can be found here.

Size Related Properties
	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

Constraint Classification Properties
	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

Structure

Available nonzero structure and decomposition information. Further information can be found here.

Nonzero entries of original problem

Nonzero entries after trivial presolving

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

Best Known Solution(s)

No solution available for 8div-n59k12 .

Similar instances in collection

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

Reference

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