toll-like

binary benchmark_suitable set_covering invariant_knapsack

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 (https://dx.doi.org/10.1007/s10878-009-9212-2) and finding optimal layouts of tanglegrams (https://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.

Location of instance in collection

Instance Statistics

Detailed explanation of the following tables can be found here.

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

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

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	1.826075
Constraint %		0.022686	0.397005	0.0453721	10.8212
Variable %		0.104058	0.862948	0.1387440	24.6965
Score	0.221200

Best Known Solution(s)

No solution available for toll-like .

Similar instances in collection

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	Constraints	Nonz.	Submitter	Group	Objective	Tags
tanglegram6	easy	9182	9182	17712	53136	Falk Hueffner	huefner	1224	binary benchmark_suitable set_covering invariant_knapsack
tanglegram4	easy	56048	56048	110404	331212	Falk Hueffner	huefner	10696	binary benchmark_suitable set_covering invariant_knapsack
neos18	easy	3312	3312	11402	24614	NEOS Server Submission	neos-pseudoapplication-49	16	binary decomposition benchmark_suitable precedence variable_bound set_covering invariant_knapsack
vpphard2	easy	199999	199999	198450	648340	C. Cardonha	–	81	binary decomposition benchmark_suitable set_partitioning cardinality invariant_knapsack
p0201	easy	201	201	133	1923	MIPLIB submission pool	pfour	7614.999999999997	binary set_packing set_covering invariant_knapsack knapsack mixed_binary

Reference

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