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

Michael Bastubbe | 283648 | 1050112 | 1.23263e-05 | open | graphs | 0* | graph40-80-1rand.mps.gz |

Packing Cuts in Undirected Graphs. Instances are described in 4.1.

Detailed explanation of the following tables can be found here.

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

Variables | 283648 | 283136 |

Constraints | 1050112 | 1025024 |

Binaries | 283648 | 283136 |

Integers | 0 | 0 |

Continuous | 0 | 0 |

Implicit Integers | 0 | 0 |

Fixed Variables | 0 | 0 |

Nonzero Density | 1.23263e-05 | 1.23104e-05 |

Nonzeroes | 3671550 | 3572740 |

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

Total | 1050112 | 1025024 |

Empty | 0 | 0 |

Free | 0 | 0 |

Singleton | 512 | 0 |

Aggregations | 0 | 0 |

Precedence | 0 | 24576 |

Variable Bound | 0 | 0 |

Set Partitioning | 512 | 512 |

Set Packing | 0 | 0 |

Set Covering | 524288 | 0 |

Cardinality | 0 | 0 |

Invariant Knapsack | 524800 | 999936 |

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

Constraint % | |||||

Variable % | |||||

Score |

No solution available for graph40-80-1rand .

The following instances are most similar to graph40-80-1rand 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 |
---|---|---|---|---|---|---|---|---|---|---|---|

graph40-40-1rand | open | 102600 | 102600 | 0 | 0 | 360900 | 1260900 | Michael Bastubbe | graphs | -9* | binary precedence set_partitioning invariant_knapsack |

graph40-20-1rand | open | 31243 | 31243 | 0 | 0 | 99067 | 345557 | Michael Bastubbe | graphs | -14* | binary decomposition precedence set_partitioning invariant_knapsack |

graph20-80-1rand | open | 16263 | 16263 | 0 | 0 | 55107 | 191997 | Michael Bastubbe | graphs | -6* | binary decomposition precedence set_partitioning invariant_knapsack |

neos-3555904-turama | easy | 37461 | 37461 | 0 | 0 | 146493 | 793605 | Hans Mittelmann | neos-pseudoapplication-81 | -34.7 | benchmark binary benchmark_suitable aggregations precedence variable_bound set_partitioning set_packing cardinality invariant_knapsack |

graph20-20-1rand | easy | 2183 | 2183 | 0 | 0 | 5587 | 19277 | Michael Bastubbe | graphs | -9 | benchmark binary decomposition benchmark_suitable precedence set_partitioning invariant_knapsack |

```
@article{or:BergnerLuebbeckeWitt:16,
Author = {
M. Bergner and M.E. L\"{u}bbecke and J.T. Witt},
Title = {A Branch-Price-and-Cut Algorithm for Packing Cuts in Undirected Graphs},
Journal = {Journal of Experimental Algorithmics (JEA)},
Year = {2016},
Volume = {21 },
Number = {2016--},
Pages = {Article No. 1.2},
Month = {Jan},
Publisher = {ACM New York, NY, USA},
DOI = {10.1145/2851492}
}
```

Last Update Jul 31, 2019 by Gregor Hendel

generated with R Markdown

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

Imprint