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

Falk Hueffner | 2883 | 4408 | 1.04058e-03 | easy | huefner | 610 | toll-like.mps.gz |

The NP-hard Balanced Subgraph problem (variant of MaxCut) encoded as ILPs. Real-world instances from two applications from bioinformatics, finding monotone subsystems in gene regulatory networks (http://dx.doi.org/10.1007/s10878-009-9212-2) and finding optimal layouts of tanglegrams (http://dx.doi.org/10.1007/978-3-642-11269-0). Solved by Gurobi 4.6 (8 threads) in about four days after a variable transformation reducing symmetry.

Imported from MIPLIB2010.

Detailed explanation of the following tables can be found here.

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

Variables | 2883 | 2883 |

Constraints | 4408 | 4408 |

Binaries | 2883 | 2883 |

Integers | 0 | 0 |

Continuous | 0 | 0 |

Implicit Integers | 0 | 0 |

Fixed Variables | 0 | 0 |

Nonzero Density | 0.00104058 | 0.00104058 |

Nonzeroes | 13224 | 13224 |

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

Total | 4408 | 4408 |

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

Set Covering | 3253 | 1155 |

Cardinality | 0 | 0 |

Invariant Knapsack | 1155 | 3253 |

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

Constraint % | 0.022686 | 0.397005 | 0.0453721 | 10.8212 | |

Variable % | 0.104058 | 0.862948 | 0.1387440 | 24.6965 | |

Score | 0.221200 |

No solution available for toll-like .

The following instances are most similar to toll-like 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 |
---|---|---|---|---|---|---|---|---|---|---|---|

tanglegram6 | easy | 9182 | 9182 | 0 | 0 | 17712 | 53136 | Falk Hueffner | huefner | 1224 | binary benchmark_suitable set_covering invariant_knapsack |

tanglegram4 | easy | 56048 | 56048 | 0 | 0 | 110404 | 331212 | Falk Hueffner | huefner | 10696 | binary benchmark_suitable set_covering invariant_knapsack |

neos18 | easy | 3312 | 3312 | 0 | 0 | 11402 | 24614 | NEOS Server Submission | neos-pseudoapplication-49 | 16 | binary decomposition benchmark_suitable precedence variable_bound set_covering invariant_knapsack |

vpphard2 | easy | 199999 | 199999 | 0 | 0 | 198450 | 648340 | C. Cardonha | – | 81 | binary decomposition benchmark_suitable set_partitioning cardinality invariant_knapsack |

p0201 | easy | 201 | 201 | 0 | 0 | 133 | 1923 | MIPLIB submission pool | pfour | 7615 | binary set_packing set_covering invariant_knapsack knapsack mixed_binary |

```
@incollection{BockerHuffnerTrussWahlstorm2009,
author = {B{\"o}cker, Sebastian and H{\"u}ffner, Falk and Truss, Anke and
Wahlstr{\"o}m, Magnus},
booktitle = {Parameterized and Exact Computation},
editor = {Chen, Jianer and Fomin, Fedor},
pages = {38-49},
publisher = {Springer},
series = {Lecture Notes in Computer Science},
title = {A Faster Fixed-Parameter Approach to Drawing Binary Tanglegrams},
volume = {5917},
year = {2009}
}
@article{HerrRehnSchuermann2012,
adsurl = {http://adsabs.harvard.edu/abs/2012arXiv1202.0435H},
archiveprefix = {arXiv},
author = {{Herr}, K. and {Rehn}, T. and {Sch{\"u}rmann}, A.},
eprint = {1202.0435},
journal = {ArXiv e-prints},
primaryclass = {math.OC},
title = {Exploiting Symmetry in Integer Convex Optimization using Core Points},
year = {2012}
}
@article{HuffnerBetzlerNiedermeier2010,
author = {H{\"u}ffner, Falk and Betzler, Nadja and Niedermeier, Rolf},
issn = {1382-6905},
issue = {4},
journal = {Journal of Combinatorial Optimization},
keyword = {Mathematics and Statistics},
pages = {335-360},
publisher = {Springer Netherlands},
title = {Separator-based data reduction for signed graph balancing},
volume = {20},
year = {2010}
}
```

Last Update Aug 13, 2020 by Gabriel Kressin

generated with R Markdown

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

Imprint