Submitter | Variables | Constraints | Density | Status | Group | Objective | MPS File |
---|---|---|---|---|---|---|---|
Sascha Kurz | 11811 | 14478 | 1.51955e-03 | open | -- | -289.0* | cdc7-4-3-2.mps.gz |
Codes for Networkcoding A constant dimension code with parameters n, k, d and q is a collection of k-dimensional subspaces of the n-dimensional vector space \(GF(q)^n\) over a finite field with q elements, called codewords, such that the dimension of the intersection of each pair of different k-dimensional subspaces is at most \(k-d/2\). Let \(A_q(n,d;k)\) denote the maximum number of codewords. For instance cdc6-4-3-2 \(A_2(6,4;3)=77\) is known , while \(333 \le A_2(7,4;3) \le 381\) for instance cdc7-4-3-2 are the tightest known bounds, see e.g. . A code of size 381 would correspond to a putative binary q-analog of the Fano plane (finite projective plane of order 2 with 7 points and lines). More bounds are available at http://subspacecodes.uni-bayreuth.de.
Detailed explanation of the following tables can be found here.
Original | Presolved | |
---|---|---|
Variables | 11811 | 11811 |
Constraints | 14478 | 14478 |
Binaries | 11811 | 11811 |
Integers | 0 | 0 |
Continuous | 0 | 0 |
Implicit Integers | 0 | 0 |
Fixed Variables | 0 | 0 |
Nonzero Density | 0.00151955 | 0.00151955 |
Nonzeroes | 259842 | 259842 |
Original | Presolved | |
---|---|---|
Total | 14478 | 14478 |
Empty | 0 | 0 |
Free | 0 | 0 |
Singleton | 0 | 0 |
Aggregations | 0 | 0 |
Precedence | 0 | 0 |
Variable Bound | 0 | 0 |
Set Partitioning | 0 | 0 |
Set Packing | 14478 | 14478 |
Set Covering | 0 | 0 |
Cardinality | 0 | 0 |
Invariant Knapsack | 0 | 0 |
Equation Knapsack | 0 | 0 |
Bin Packing | 0 | 0 |
Knapsack | 0 | 0 |
Integer Knapsack | 0 | 0 |
Mixed Binary | 0 | 0 |
General Linear | 0 | 0 |
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 | 0.30103 | ||||
Constraint % | 100 | 100 | 100 | 100 | |
Variable % | 100 | 100 | 100 | 100 | |
Score | 0.00000 |
Find solutions below. Download the archive containing all solutions from the Download page.
ID | Objective | Exact | Int. Viol | Cons. Viol | Obj. Viol | Submitter | Date | Description | |
---|---|---|---|---|---|---|---|---|---|
4 | 7 | -289 | -289 | 0 | 0 | 0 | Yuji Koguma | 2020-06-24 | Obtained with a Tabu Search algorithm based on the paper, Koji Nonobe, Toshihide Ibaraki: "An Improved Tabu Search Method For The Weighted Constraint Satisfaction Problem," INFOR, Vol.39, No.2, pp.131-151, 2001 |
5 | 6 | -288 | -288 | 0 | 0 | 0 | Shunsuke Kamiya | 2020-05-17 | Computed with weighting local search with exploiting variable associations (WLS) ([1]) [1] Umetani, Shunji. "Exploiting variable associations to configure efficient local search algorithms in large-scale binary integer programs." European Journal of Operational Research 263.1 (2017): 72-81. |
2 | 5 | -285 | -285 | 0 | 0 | 0 | Edward Rothberg | 2020-04-22 | Obtained with Gurobi 9.0 using the solution improvement heuristic |
6 | 4 | -282 | -282 | 0 | 0 | 0 | Frederic Didier | 2020-01-22 | Obtained with Google OR-tools using 8 Threads through generating subproblems by fixing part of the current solution and trying to solve them with a sub CP-SAT solver |
1 | 3 | -279 | 0 | 0 | 0 | Edward Rothberg | 2019-12-13 | Obtained with Gurobi 9.0 | |
7 | 2 | -275 | 0 | 0 | 0 | Robert Ashford and Alkis Vazacopoulus | 2019-12-18 | Found using ODH|CPlex | |
3 | 1 | -260 | -260 | 0 | 0 | 0 | - | 2018-10-13 | Solution found during MIPLIB2017 problem selection. |
The following instances are most similar to cdc7-4-3-2 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 |
---|---|---|---|---|---|---|---|---|---|---|---|
cod105 | easy | 1024 | 1024 | 0 | 0 | 1024 | 57344 | MIPLIB submission pool | -- | -12 | benchmark binary benchmark_suitable set_packing |
a2864-99blp | open | 200787 | 200787 | 0 | 0 | 22117 | 20078700 | Daniel Heinlein | selofsubspaces | -257* | binary set_packing invariant_knapsack |
sorrell8 | easy | 2046 | 2046 | 0 | 0 | 18944 | 37888 | Toni Sorrell | independentset | -350 | binary decomposition variable_bound |
sorrell7 | open | 2048 | 2048 | 0 | 0 | 78848 | 157696 | Toni Sorrell | independentset | -196.0* | binary variable_bound |
z26 | open | 17937 | 17937 | 0 | 0 | 850513 | 1715610 | Daniel Bienstock | -- | -1187.0* | binary variable_bound set_packing |
@article{honold2015optimal,
title={Optimal binary subspace codes of length 6, constant dimension 3 and minimum subspace distance 4},
author={Honold, Thomas and Kiermaier, Michael and Kurz, Sascha},
journal={Contemporary Mathematics},
volume={632},
pages={157--172},
year={2015},
}
@incollection{kohnert2008construction,
title={Construction of large constant dimension codes with a prescribed minimum distance},
author={Kohnert, Axel and Kurz, Sascha},
booktitle={Mathematical Methods in Computer Science},
volume={5393},
pages={31--42},
year={2008},
publisher={Springer}
}