tw-myciel4

aggregations precedence variable_bound invariant_knapsack general_linear

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 Status Variables Binaries Integers Continuous Constraints Nonz. Submitter Group Objective Tags
neos-950242 easy 5760 5520 240 0 34224 104160 NEOS Server Submission neos-pseudoapplication-72 4 benchmark benchmark_suitable aggregations precedence variable_bound set_partitioning set_covering invariant_knapsack general_linear
supportcase10 hard 14770 14770 0 0 165684 555082 Michael Winkler 7 benchmark binary benchmark_suitable aggregations precedence variable_bound set_covering invariant_knapsack
genus-sym-grafo5708-48 open 3379 3377 1 1 20538 72579 Stephan Beyer genus -21* precedence set_partitioning set_covering cardinality invariant_knapsack knapsack general_linear
supportcase21i easy 27 24 3 0 7540 95325 Michael Winkler 20 indicator numerics set_covering invariant_knapsack general_linear
genus-sym-g62-2 open 12912 12910 1 1 78472 275855 Stephan Beyer genus -34.0* precedence set_partitioning set_covering cardinality invariant_knapsack knapsack general_linear

Reference

No bibliographic information available

Last Update Mar 04, 2024 by Julian Manns
generated with R Markdown
© 2023 by Zuse Institute Berlin (ZIB)
Imprint