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

Last Update Aug 13, 2020 by Gabriel Kressin

generated with R Markdown

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

Imprint