Submitter Variables Constraints Density Status Group Objective MPS File
Arie Koster 760 8146 4.51642e-03 hard 10 tw-myciel4.mps.gz

Model to compute the treewidth of the Mycielski-4 instance from the DIMACS graph coloring database. Solved in June 2013 by CPLEX 12.5.1 (12 threads) in about 66 hours. The solving was performed in two steps: first solving with 50 GB tree memory limit (took 11307.42 seconds), after that, setting the tree memory limit to 80 GB and switching to depth first search (took 226152.14 seconds).

Imported from MIPLIB2010.

Instance Statistics

Detailed explanation of the following tables can be found here.

Size Related Properties
Original Presolved
Variables 760 760
Constraints 8146 8146
Binaries 759 759
Integers 1 1
Continuous 0 0
Implicit Integers 0 0
Fixed Variables 0 0
Nonzero Density 0.00451642 0.00451642
Nonzeroes 27961 27961
Constraint Classification Properties
Original Presolved
Total 8146 8146
Empty 0 0
Free 0 0
Singleton 0 0
Aggregations 71 71
Precedence 253 253
Variable Bound 435 435
Set Partitioning 0 0
Set Packing 0 0
Set Covering 1771 0
Cardinality 0 0
Invariant Knapsack 5593 7364
Equation Knapsack 0 0
Bin Packing 0 0
Knapsack 0 0
Integer Knapsack 0 0
Mixed Binary 0 0
General Linear 23 23
Indicator 0 0

Structure

Available nonzero structure and decomposition information. Further information can be found here.

value min median mean max
Components 0.4771212
Constraint % 43.4815 45.7771 45.7771 48.0727
Variable % 33.2895 50.0000 50.0000 66.7105
Score 0.4500990

Best Known Solution(s)

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
2 10 10 0 0 0 - 2018-10-29 Solution found during MIPLIB2017 problem selection.
1 10 10 0 0 0 - 2018-10-12 Solution imported from MIPLIB2010.

Similar instances in collection

The following instances are most similar to tw-myciel4 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 Variables Binaries Integers Continuous Constraints Nonz. Submitter Group Status Objective
neos-950242 5760 5520 240 0 34224 104160 NEOS Server Submission neos-pseudoapplication-72 easy 4
supportcase10 14770 14770 0 0 165684 555082 Michael Winkler hard 7
genus-sym-grafo5708-48 3379 3377 1 1 20538 72579 Stephan Beyer genus open -15*
supportcase21i 27 24 3 0 7540 95325 Michael Winkler easy 20
genus-sym-g62-2 12912 12910 1 1 78472 275855 Stephan Beyer genus open -20*

Reference

No bibliographic information available

Last Update Nov 09, 2018 by Gregor Hendel
generated with R Markdown
© 2018 by Konrad-Zuse-Zentrum für Informationstechnik Berlin (ZIB)
Imprint